fork(6) download
copy 
  1. import java.math.BigInteger;
  2.  
  3. public class Main {
  4. 	// матричное умножение двух матриц размера 2 на 2
  5. 	public static BigInteger[][] matrixMultiplication(BigInteger[][] a, BigInteger[][] b) {
  6. 		// [a00 * b00 + a01 * b10, a00 * b01 + a01 * b11]
  7. 		// [a10 * b00 + a11 * b10, a10 * b01 + a11 * b11]
  8. 		return new BigInteger[][]{
  9. 				{
  10. 						a[0][0].multiply(b[0][0]).add(a[0][1].multiply(b[1][0])),
  11. 						a[0][0].multiply(b[0][1]).add(a[0][1].multiply(b[1][1]))
  12. 				},
  13. 				{
  14. 						a[1][0].multiply(b[0][0]).add(a[1][1].multiply(b[1][0])),
  15. 						a[1][0].multiply(b[0][1]).add(a[1][1].multiply(b[1][1]))
  16. 				},
  17. 		};
  18. 	}
  19.  
  20. 	// возведение матрицы размера 2 на 2 в степень n
  21. 	public static BigInteger[][] matrixPowerFast(BigInteger[][] a, int n) {
  22. 		if (n == 0) {
  23. 			// любая матрица в нулевой степени равна единичной матрице
  24. 			return new BigInteger[][]{
  25. 					{BigInteger.ONE, BigInteger.ZERO},
  26. 					{BigInteger.ZERO, BigInteger.ONE}
  27. 			};
  28. 		} else if (n % 2 == 0) {
  29. 			// a ^ (2k) = (a ^ 2) ^ k
  30. 			return matrixPowerFast(matrixMultiplication(a, a), n / 2);
  31. 		} else {
  32. 			// a ^ (2k + 1) = (a) * (a ^ 2k)
  33. 			return matrixMultiplication(matrixPowerFast(a, n - 1), a);
  34. 		}
  35. 	}
  36.  
  37. 	// функция, возвращающая n-ое число Фибоначчи
  38. 	public static BigInteger fibonacci(int n) {
  39. 		if (n == 0) {
  40. 			return BigInteger.ZERO;
  41. 		}
  42.  
  43. 		BigInteger[][] a = {
  44. 				{BigInteger.ONE, BigInteger.ONE},
  45. 				{BigInteger.ONE, BigInteger.ZERO}
  46. 		};
  47. 		BigInteger[][] powerOfA = matrixPowerFast(a, n - 1);
  48. 		// nthFibonacci = powerOfA[0][0] * F_1 + powerOfA[0][0] * F_0 = powerOfA[0][0] * 1 + powerOfA[0][0] * 0
  49. 		BigInteger nthFibonacci = powerOfA[0][0];
  50. 		return nthFibonacci;
  51. 	}
  52.  
  53. 	public static void main(String[] args) {
  54. 		System.out.println(fibonacci(1024));
  55. 	}
  56. }
Success #stdin #stdout 0.05s 4575232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4506699633677819813104383235728886049367860596218604830803023149600030645708721396248792609141030396244873266580345011219530209367425581019871067646094200262285202346655868899711089246778413354004103631553925405243
https://ideone.com/O08Sqk
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!