javascript - How to find remainder of a really big integer

Question

I find out the n th number of the fibonacci sequence by doing this:

function add(a, b) {
while (a.length < b.length) a.unshift(0);
while (a.length > b.length) b.unshift(0);
var carry = 0, sum = []
for (var i = a.length - 1; i >= 0; i--) {
    var s = a[i] + b[i] + carry;
    if (s >= 10) {
        s = s - 10;
        carry = 1;
    } else {
        carry = 0;
    }
    sum.unshift(s);
}
if (carry)
    sum.unshift(carry);
return sum;
}
function fib(n) {
var f1 = [0];
var f2 = [1];

while (n--) {
    var f3 = add(f1, f2)
    f1 = f2;
    f2 = f3;
}
return f1.join("");
}

Say, I want to find the remainder when the 1995th fibonacci number is divided by 8. Doing this,

fib(1995) % 8

returns, however, NaN. Here's a fiddle with output to console.log.

So how do I find the remainder of the 1995th fibonacci number divided by 8?

Okay - it's not possible because `Infinity` is the result of `fib(1995) / 8` — Jurik, Apr 09 '14 at 07:11
It seems that you exceed the maximum int size in Javascript. Check out: http://stackoverflow.com/questions/4288821/how-to-deal-with-big-numbers-in-javascript and try out a big number library. — Alex van den Hoogen, Apr 09 '14 at 07:12
If it's just about calculating fibonacci number module some number just take modulo when you do calculations, i.e f(n) % m = (f(n - 1) + f(n - 2)) % m, this way you don't overflow. — Aleksandr Nikiforov, Apr 09 '14 at 07:40

Ja͢ck · Accepted Answer · 2014-04-11T05:52:29.317

3

What you have described there is a very particular application of number theory known as the Pisano period:

In number theory, the nth Pisano period, written π(n), is the period with which the sequence of Fibonacci numbers, modulo n repeats. For example, the Fibonacci numbers modulo 3 are 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, etc., with the first eight numbers repeating, so π(3) = 8.

The Pisano period for n = 8 is 12, so you're looking for the (1995 % 12)'th element of the repeating sequence, so:

0 1 1 2 3 5 0 5 5 2 7 1
      ^

Update

As mentioned in the comments, at every pair addition you can apply the modulo to keep the numbers manageable:

function fib(n, mod)
{
    if (n == 0) {
        return 0;
    } else if (n <= 2) {
        return 1;
    }

    var current = 1,
    tmp,
    prev = 1;

    while (n > 2) {
        tmp = current;

        current = (current + prev) % mod;
        prev = tmp;

        --n;
    }

    return current;
}

fib(1995, 8); // 2

edited Apr 11 '14 at 05:52

answered Apr 09 '14 at 07:54

Ja͢ck

170,779
38
263
309

This answer has nothing to do with Javascript, but good effort there. – chris97ong Apr 09 '14 at 08:03
Without Pisano you can argue: The remainder of dividing fn by 8 is equal to: the remainder of dividing the sum of the remainders of fn-1 and fn-2 This is exactly what Aleksandr Nikiforov commented. – Walter A Apr 09 '14 at 08:11
@chris97ong I've added an example of continuous application of modulo to find the answer. – Ja͢ck Apr 09 '14 at 08:35

Justus Romijn · Answer 2 · 2014-04-09T08:51:23.803

I've faced this problem when trying to validate IBAN numbers (European bank account standard). It makes use of a control number to avoid transactions to mistyped accounts (with a modulo 97 result which always should be 1).

I've found a gist (IBAN javascript validator gist), which is also capable of doing what you need. This is the useful part (note: the divident parameter must be a STRING):

modulo = function (divident, divisor) {
    var cDivident = '';
    var cRest = '';

    for (var i in divident ) {
         var cChar = divident[i];
         var cOperator = cRest + '' + cDivident + '' + cChar;

         if ( cOperator < parseInt(divisor) ) {
             cDivident += '' + cChar;
         } else {
             cRest = cOperator % divisor;
             if ( cRest == 0 ) {
                cRest = '';
             }
             cDivident = '';
        }

    }
    cRest += '' + cDivident;
    if (cRest == '') {
        cRest = 0;
    }
    return cRest;
};

Basically, it chops the big number into smaller amounts which can be handled by javascript. Here's a working fiddle:

jsFiddle example of modulo with big integers in javascript

Could you post a fiddle? Thx. – chris97ong Apr 09 '14 at 07:53 — chris97ong, Apr 09 '14 at 07:53

Vitaly Dyatlov · Answer 3 · 2014-04-09T09:00:18.877

0

var cache = {};
var result = 0;
function fib_mod(number, mod) {
    if( cache[number] ) return cache[number];

    if( number < 3 ) result = 1 % mod; // 1st is 1, 2nd is 1 too
    else result = (fib_mod(number-2, mod) + fib_mod(number-1, mod)) % mod;

    cache[number] = result;

    return result;
}

fib_mod(1995,8); // output is 2

JsFiddle is here: http://jsfiddle.net/y5B7q/

edited Apr 09 '14 at 09:00

answered Apr 09 '14 at 08:53

Vitaly Dyatlov

1,872
14
24

javascript - How to find remainder of a really big integer

3 Answers3

Update