I'm currently using matrix multiplication formulas to create algorithms for Fibonacci sequences.
I made my JavaScript code based on the following python code. However, it was confirmed that another value was output [case fib(150)]. I think the % mod is wrong, but how can I solve this problem?
javascript code
const n = parseInt(prompt("Number"));
const mod = 1000000007;
const fib = () => {
const zero = [
[1, 1],
[1, 0],
];
const base = [
[1],
[1]
];
const power = (a, num) => {
if (num === 1) return a;
else if (num % 2 != 0) return multi(power(a, num - 1), a);
else return power(multi(a, a), parseInt(num / 2));
};
const multi = (a, b) => {
const temp = Array.from(Array(2), () => Array(b[0].length).fill(0));
for (let i = 0; i < 2; i++) {
for (let j = 0; j < b[0].length; j++) {
let sum_num = 0;
for (let k = 0; k < 2; k++) {
sum_num += a[i][k] * b[k][j];
}
temp[i][j] = sum_num % mod;
}
}
return temp;
};
return multi(power(zero, n - 2), base)[0][0];
};
if (n === 0) {
console.log(0);
} else if (n < 3) {
console.log(1);
} else {
console.log(fib());
}python code
import sys
input = sys.stdin.readline
MOD = 1000000007
adj=[[1,1],[1,0]]
start=[[1],[1]]
N = int(input())
def power(adj,n):
if n == 1:
return adj
elif n % 2:
return multi(power(adj,n-1), adj)
else:
return power(multi(adj,adj), n//2)
def multi(a,b):
temp=[[0]*len(b[0]) for _ in range(2)]
for i in range(2):
for j in range(len(b[0])):
sum_n = 0
for k in range(2):
sum_n += a[i][k]*b[k][j]
temp[i][j]= sum_n % MOD
return temp
if N < 3:
print(1)
else:
print(multi(power(adj,N-2),start)[0][0])
I solved it using bigint. Thank you for your help. (mplungjan, Kelly Bundy)
const n = BigInt(prompt('Number'));
const mod = 1000000007n;
const fib = () => {
const zero = [
[1n, 1n],
[1n, 0n],
];
const base = [[1n], [1n]];
const power = (a, num) => {
if (num === 1n) return a;
else if (num % 2n != 0) return multi(power(a, num - 1n), a);
else return power(multi(a, a), BigInt(num / 2n));
};
const multi = (a, b) => {
const temp = Array.from(Array(2), () => Array(b[0].length).fill(0));
for (let i = 0; i < 2; i++) {
for (let j = 0; j < b[0].length; j++) {
let sum_num = 0n;
for (let k = 0; k < 2; k++) {
sum_num += a[i][k] * b[k][j];
}
temp[i][j] = sum_num % mod;
}
}
return temp;
};
return multi(power(zero, n - 2n), base)[0][0];
};
if (n === 0) {
console.log(0);
} else if (n < 3) {
console.log(1);
} else {
console.log(parseInt(fib()));
}