Estoy tratando de resolver el algoritmo de Fibonacci usando matrices. Mi complejidad de tiempo objetivo es un o (logn) en lugar de un o (n). La salida de retorno del programa no es el número de la serie sino los sextos dígitos significativos. Es por eso que devuelvo el resto de la solución dividido por un millón.
Escribí el código y funciona bien, pero noté que para entradas extremadamente grandes, obtengo un NAN (no un número) en lugar de una salida
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))Ese es mi código de arriba. ¿Hay algo que pueda cambiar para que sea mucho más eficaz?
De hecho, encontré el error. Mis números eran cada vez más grandes que el valor máximo.
Cambié esto devolviendo el resto de mi valor dividido por un millón a la matriz y luego devolviendo el valor de la matriz en lugar de devolver el valor y luego dividir por un millón. El primero es eficiente y funciona para entradas de cualquier tamaño.
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))