Fibonacci Sequence - Find the number of digits - JavaScript

Question

So, I have successfully written the Fibonacci sequence to create an array with the sequence of numbers, but I need to know the length (how many digits) the 500th number has.

I've tried the below code, but its finding the length of the scientific notation (22 digits), not the proper 105 it should be returning.

Any ideas how to convert a scientific notation number into an actual integer?

var fiblength = function fiblength(nth) {
    var temparr = [0,1];
    for(var i = 2; i<=nth; i++){
        var prev = temparr[temparr.length-2],
            cur = temparr[temparr.length-1],
            next = prev + cur;
            temparr.push(next);
    }
    var final = temparr[temparr.length-1].toString().length;
    console.log(temparr[temparr.length-1]);
    return final;
};
a = fiblength(500);
console.log(a);

Answer 1

Why not use the simple procedure of dividing the number by 10 until the number is less than 1.

Something as simple as this should work (a recursive def obv works as well)

function getDigits(n) {
   var digits = 0;
   while(n >= 1) {
      n/=10;
      digits += 1;
   }
   return digits;
}

getDigits(200);//3
getDigits(3.2 * 10e20);//=>22

Answer 2

Here's a solution in constant time:

function fiblength(n) { 
   return Math.floor((n>1)?n*.2089+.65051:1); 
}

Let's explain how I arrived to it.

All previous solutions will probably not work for N>300 unless you have a BigNumber library in place. Also they're pretty inneficient.

There is a formula to get any Fibonacci number, which uses PHI (golden ratio number), it's very simple:

F(n) = ABS((PHI^n)/sqrt(5))

Where PHI=1.61803399 (golden ratio, found all over the fibonacci sequence)

If you want to know how many digits a number has, you calculate the log base 10 and add 1 to that. Let's call that function D(n) = log10(n) + 1

So what you want fiblength to be is in just the following function

fiblength(n) = D(F(n)) // number of digits of a fibonacci number...

Let's work it out, so you see what the one liner code will be like once you use math.

Substitute F(n)

fiblength(n) = D(ABS((PHI^n)/sqrt(5)))

Now apply D(n) on that:

fiblength(n) = log10(ABS((PHI^n)/sqrt(5))) + 1

So, since log(a/b) = log(a) - log(b)

fiblength(n) = log10(ABS((PHI^n))) - log10(sqrt(5))) + 1

and since log(a^n) = n * log(a)

fiblength(n) = n*log10(PHI) - log10(sqrt(5))) + 1

Then we evaluate those logarithms since they're all on constants and add the special cases of n=0 and n=1 to return 1

function fiblength(n) { 
   return Math.floor((n>1)?n*.2089+.65051:1); 
}

Enjoy :)

fiblength(500) => 105 //no iterations necessary.

Answer 3

Most of the javascript implementations, internally use 64 bit numbers. So, if the number we are trying to represent is very big, it uses scientific notation to represent those numbers. So, there is no pure "javascript numbers" based solution for this. You may have to look for other BigNum libraries.

As far as your code is concerned, you want only the 500th number, so you don't have to store the entire array of numbers in memory, just previous and current numbers are enough.

function fiblength(nth) {
    var previous = 0, current = 1, temp;
    for(var i = 2; i<=nth; i++){
        temp = current;
        current = previous + current;
        previous = temp;
    }
    return current;
};

Answer 4

My Final Solution

function fiblength(nth) {
    var a = 0, b = 1, c;
    for(var i=2;i<=nth;i++){
        c=b;
        b=a+b;
        a=c;
    }
    return Math.floor(Math.log(b)/Math.log(10))+1;
}
console.log(fiblength(500));

Thanks for the help!!!

Answer 5

The problem is because the resulting number was converted into a string before any meaningful calculations could be made. Here's how it could have been solved in the original code:

var fiblength = function fiblength(nth) {
    var temparr = [0,1];
    for(var i = 2; i<=nth; i++){
        var prev = temparr[temparr.length-2],
            cur = temparr[temparr.length-1],
            next = prev + cur;
            temparr.push(next);
    }
    var x = temparr[temparr.length-1];
    console.log(x);
    var length = 1;
    while (x > 1) {
        length = length + 1;
        x = x/10;
    }
    return length;
};

console.log ( fiblength(500) );