Applying Fibonacci, working with large numbers

Question

I am trying to successfully complete this challenge on the Rosalind page. The challenge is:

Given: Positive integers n≤40 and k≤5.

Return: The total number of rabbit pairs that will be present after n months if we begin with 1 pair and in each generation, every pair of reproduction-age rabbits produces a litter of k rabbit pairs (instead of only 1 pair).

The exercise gives a text file of two numbers, the n and k mentioned above.

My code, which attempts to implement Fibonacci, works as expected for lower numbers of months. However, the result begins to become extremely large for higher numbers of months, and in each case I am given, my answer is Infinity.

Is my formula applied incorrectly? Or is Javascript a bad choice of language to use for such an exercise?

My code:

function fibonacciRabbits(months, pairs){
    
    var months = months;
    var numberOfPairs = pairs;
    var result = 0;
    
    // Declare parent & child arrays with constants
    var parentArr = [1, numberOfPairs + 1]
    var childArr = [numberOfPairs, numberOfPairs]
    
    var total = []
    
    // Loop from the point after constants set above
    for(var i = 2; i < months - 2 ; i++){
        parentArr.push(parentArr[i-1] + childArr[i-1])
        childArr.push(parentArr[i-1] * childArr[i-2])    
        total.push(parentArr[i-1] + childArr[i-1])
    }
    
    result = childArr[childArr.length - 1] + parentArr[parentArr.length - 1]
    
    console.log(months + ' months and ' + numberOfPairs + ' pairs:\n')
    console.log('parentArr:\n', parentArr)
    console.log('childArr:\n', childArr)
    console.log('total\n', total)
    console.log('result:', result)
    console.log('\n\n\n')
}

fibonacciRabbits(5, 3)
fibonacciRabbits(11, 3)
fibonacciRabbits(21, 3)
fibonacciRabbits(31, 2)

And here is a REPL

As soon as any number gets larger than approximately 1.79E+308 it fails: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_VALUE — davejagoda, Dec 21 '15 at 17:27
I'm not sure I understand your problem, so no opinion about your algorithm ; but if your problem is dealing with big numbers, you might want to have a look here : https://stackoverflow.com/questions/3072307/what-is-the-standard-solution-in-javascript-for-handling-big-numbers-bignum (JS is indeed limited in this area, but pretty much every language will be : https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_VALUE ) — phtrivier, Dec 21 '15 at 17:32
Both python [https://www.python.org/dev/peps/pep-0237/] and ruby [http://patshaughnessy.net/2014/1/9/how-big-is-a-bignum] can handle this particular case without worry about reaching some maximum integer. — davejagoda, Dec 21 '15 at 18:09
@davejagoda So can JavaScript. The problem is that OP's algorithm is wrong, producing numbers which are **way** to big. — user229044, Dec 21 '15 at 19:36
The problem is that you're multiplying two previous terms together into `childArr`. There is no reason to do that; the `k` factor in this problem defines a constant scaling factor, while you've made it an exponential scaling factor. — user229044, Dec 21 '15 at 19:38

spozun · Accepted Answer · 2015-12-21T19:27:11.813

Here is a more brief solution that doesn't produce such large numbers, and handles the maximum case without hitting infinity in Javascript. I think your solution was getting too big too fast.

function fibonacciRabbits(months, reproAmount){

    var existingAdults = 0;
    var adultPairs = 0;
    var childPairs = 1;

    for(var i = 2; i <= months; i++){
        adultPairs = childPairs;       //children mature
        childPairs = (existingAdults * reproAmount);  //last month's adults reproduce
        existingAdults += adultPairs;  //new adults added to the reproduction pool
    }

    console.log(existingAdults + childPairs);
}

To make sure you are on the right track, test your function with:

fibonacciRabbits(1, 1);
fibonacciRabbits(2, 1);

Which from the website says: f(1)=f(2)=1. So these should both produce "1" no matter what. Your code produces "3" for both of these.

Applying Fibonacci, working with large numbers

1 Answers1