Fibonacci Sequence - Find the number of digits - JavaScript - Stack Overflow

admin管理员组

文章数量:1289582

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

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

• javascript
• fibonacci
• notation
• scientific-notation

Share Improve this question Follow asked Dec 22, 2013 at 5:33 Nicholas HazelNicholas Hazel 3,74011 gold badge2424 silver badges3636 bronze badges 7

• See if this helps stackoverflow./questions/4288821/… – elclanrs Commented Dec 22, 2013 at 5:36
• 1 I mixed things... Bignum library is probably what OP needs. – elclanrs Commented Dec 22, 2013 at 5:39
• @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. – Amadan Commented Dec 22, 2013 at 5:40
• @Amadan I was referring to the current question. – thefourtheye Commented Dec 22, 2013 at 5:42
• @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? – Amadan Commented Dec 22, 2013 at 5:44

 |  Show 2 more ments

5 Answers 5

Sorted by: Reset to default 8

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

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.

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

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

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

本文标签： Fibonacci SequenceFind the number of digitsJavaScriptStack Overflow