9

I'm working on the Rosalind problem Mortal Fibonacci Rabbits and the website keeps telling me my answer is wrong when I use my algorithm written JavaScript. When I use the same algorithm in Python I get a different (and correct) answer.

The inconsistency only happens when the result gets large. For example fibd(90, 19) returns 2870048561233730600 in JavaScript but in Python I get 2870048561233731259.

Is there something about numbers in JavaScript that give me a different answer or am making a subtle mistake in my JavaScript code?

The JavaScript solution:

function fibd(n, m) {
    // Create an array of length m and set all elements to 0
    var rp = new Array(m);
    rp = rp.map(function(e) { return 0; });
    rp[0] = 1;

    for (var i = 1; i < n; i++) {
        // prepend the sum of all elements from 1 to the end of the array
        rp.splice(0, 0, rp.reduce(function (e, s) { return s + e; }) - rp[0]);
        // Remove the final element
        rp.pop();
    }

    // Sum up all the elements
    return rp.reduce(function (e, s) { return s + e; });
}

The Python solution:

def fibd(n, m):
    # Create an array of length m and set all elements to 0
    rp = [0] * m
    rp[0] = 1

    for i in range(n-1):
        # The sum of all elements from 1 the end and dropping the final element
        rp = [sum(rp[1:])] + rp[:-1]

    return sum(rp)
Colonel Panic
  • 132,665
  • 89
  • 401
  • 465
Cristian
  • 42,563
  • 25
  • 88
  • 99
  • Can you give an example? I run your code and it gives same result for input (10,10). However I can see a typo "rp.splice(0, 0, rp.reduce(function (e, s) { return s + e; }) - rP[0]);". Could it be that? If not, is there a point of divergence? – Simone Zandara Dec 10 '15 at 09:03
  • Good point. I added an example. It happens on larger inputs. Good catch on the typo. Thanks, but that's not the problem. That was just me trying to make the variable names the same in question and me just missing one variable to update. The typo is fixed now – Cristian Dec 10 '15 at 09:08

2 Answers2

13

I think Javascript only has a "Number" datatype, and this actually an IEEE double under the hood. 2,870,048,561,233,730,600 is too large to hold precisely in IEEE double, so it is approximated. (Notice the trailing "00" - 17 decimal places is about right for double.)

Python on the other hand has bignum support, and will quite cheerfully deal with 4096 bit integers (for those that play around with cryptographic algorithms, this is a huge boon).

You might will be able to find a Javascript bignum library if you search - for example http://silentmatt.com/biginteger/

Martin Bonner supports Monica
  • 28,528
  • 3
  • 51
  • 88
7

Just doing a bit of research, this article seems interesting. Javascript only supports 53bits integers.

The result given by Python is indeed out of the maximum safe range for JS. If you try to do 

parseInt('2870048561233731259')

It will indeed return 

2870048561233731000
Simone Zandara
  • 9,401
  • 2
  • 19
  • 26