I am trying to solve the Fibonacci algorithm using matrices. My target time complexity is an o(logn) instead of an o(n). The return output of the program is not the number for the series but the sixth significant digits. Its why I am returning the remainder of the solution divided by a million.
I have written the code and it runs well but I noticed that for extremely large inputs, I get a NAN(not a number) instead of an output
const fib = (n) => {
let fibMatrix = [[1,1], [1,0]]
if(n == 0){
return 0;
}
raiseToPower(fibMatrix, n - 1);
return Math.floor(fibMatrix[0][0] % 1000000)
}
const raiseToPower = (matrix, n) => {
if(n == 0 || n == 1){
return;
}
let newMatrix = [[1,1], [1,0]]
raiseToPower(matrix, Math.floor(n / 2))
multiplyMatrices(matrix, matrix)
if(n % 2 !== 0){
multiplyMatrices(matrix, newMatrix)
}
}
const multiplyMatrices = (matrix, newMatrix) => {
let x = matrix[0][0]*newMatrix[0][0] + matrix[0][1]*newMatrix[1][0];
let y = matrix[0][0]*newMatrix[0][1] + matrix[0][1]*newMatrix[1][1];
let z = matrix[1][0]*newMatrix[0][0] + matrix[1][1]*newMatrix[1][0];
let w = matrix[1][0]*newMatrix[0][1] + matrix[1][1]*newMatrix[1][1];
matrix[0][0] = x;
matrix[0][1] = y;
matrix[1][0] = z;
matrix[1][1] = w;
}
console.log(fib(2000))
Thats my code above. Is there anything I could change to actually make this much more performant?
I actually found the error. My numbers were getting larger than the maximum value.
I changed this by instead returning the remainder of my value divided by a million to the matrix and then returning the value from the matrix instead of returning the value and then dividing by a million. The former is efficient and works for any sized inputs.
const fib = (n) => {
let fibMatrix = [[1,1], [1,0]]
if(n == 0){
return 0;
}
raiseToPower(fibMatrix, n - 1);
return (fibMatrix[0][0])
}
const raiseToPower = (matrix, n) => {
if(n == 0 || n == 1){
return;
}
let newMatrix = [[1,1], [1,0]]
raiseToPower(matrix, Math.floor(n / 2))
multiplyMatrices(matrix, matrix)
if(n % 2 !== 0){
multiplyMatrices(matrix, newMatrix)
}
}
const multiplyMatrices = (matrix, newMatrix) => {
let x = (matrix[0][0]*newMatrix[0][0] + matrix[0][1]*newMatrix[1][0]);
let y = (matrix[0][0]*newMatrix[0][1] + matrix[0][1]*newMatrix[1][1]);
let z = (matrix[1][0]*newMatrix[0][0] + matrix[1][1]*newMatrix[1][0]);
let w = (matrix[1][0]*newMatrix[0][1] + matrix[1][1]*newMatrix[1][1]);
matrix[0][0] = x % 1000000;
matrix[0][1] = y % 1000000;
matrix[1][0] = z % 1000000;
matrix[1][1] = w % 1000000;
}
console.log(fib(10000))