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);

Annulation

See if this helps #4289321 – Stealthy

I mixed things... Bignum library is probably what OP needs. – Stealthy

@thefourtheye: What do you mean, there are no floating points here? All numbers in JavaScript are floating point, it doesn't even have an integral type. – Rawdan

@Rawdan I was referring to the current question. – Lullaby

@thefourtheye: I still don't understand. The current question is about numbers in JavaScript. All numbers in JavaScript are floats. Therefore, there are floats here. What am I missing? – Rawdan

Hmmm, interesting... I'll try my best to solve it without a library :-) Thanks a ton! – Annulation

you don't need BigNum or any of that to solve this problem. This is all you need: ``` function fiblength(n) { return Math.floor((n>1)?n*.2089+.65051:1); } ``` – Begonia

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

Costa

Or you could just get the 10-base logarithm. Math.floor(Math.log(n) / Math.log(10)) + 1 should suffice. – Rawdan

Here we go. This is a pretty elegant way to make that work... beautiful :-) Not 100% what I needed, but great springboard to work off of :-) Thanks! – Annulation

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.

Begonia

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;
};

Lullaby

Dividing by 10 in a loop and adding a counter to track how many times it does so tends to do the trick. However, much appreciation on minimalizing my code :-) – Annulation

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!!!

Annulation

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) );

Attah

I love the approach of avoiding built in Math functions to tweak it. One final note, you need to do return length-1; to return a correct value ;-) – Annulation