Geek asks and answers

About the number of bits needed for the Fibonacci number

I am reading a book of algorithms by S. DasGupta. Below is a fragment of text from text on the number of bits required for the nth Fibonacci number.

It makes sense to consider the add-on as one computer step if numbers are added, 32-bit numbers say. But the n-th Fibonacci number is about 0.694n bits, and this can significantly exceed 32 as n grows. arithmetic operations on arbitrarily large numbers cannot be performed in a single, constant step.

My question, for example, is for the Fibonacci number F1 = 1, F2 = 1, F3 = 2, etc. then substituting "n" in the above formula, i.e. 0.694 n for F1 is approximately 1, F2 is approximately 2 bits, but for F3, etc. The above formula fails. I think I did not understand what the author means here, can someone help me in understanding this?

thank

+3
source share
7 answers

Well,

n              3    4     5     6     7     8
0.694n         2.08 2.78  3.47  4.16  4.86  5.55
F(n)           2    3     5     8     13    21
bits           2    2     3     4     4     5
log(F(n))      1    1.58  2.32  3     3.7   4.39

The required bits are a base with base 2, rounded up, so for me it is pretty close.

0.694 , F(n) ​​(& phi; n)/& radic; 5. , log(F(n)) - n * log(phi) - log(sqrt(5)), log(phi) - 0,694. n , log(sqrt(5)) .

+7

, about , the nth Fibonacci number is about 0.694n bits long. -, , , n->infinity. :)

+1
private static int nobFib(int n)  // number of bits Fib(n)  
{
    return n < 6 ? ++n/2 : (int)(0.69424191363061738 * n - 0.1609640474436813);
}

n 0 500.000, n = 500.000.000, n = 1.000.000.000
.
: .
.: http://bigintegers.blogspot.com/2012/09/fibonacci-sequence-binary-plot-edd-peg.html

+1

...

number of bits = Math.ceil(Math.max(0.694*n,32));

n > 32 32 n < 32

32- ,

0

, , , ( > 32 ) , CPU.

? F3 = 2 2 (3 * 0,694 = 2,082) F50 = 12586269025, 33 (50 * 0,694 = 35), .

0
N    F(N)      0.694*N
1      0         1       
2      1         1
3      1         1
4      2         2
5      3         2
6      5         3
7      8         4
8     13         4

... . , f (47) = 1,836,311,903, 32 .

0
source

Basically, the author describes how large numbers affect the performance of an algorithm. To be overly simple, the processor can add register numbers very quickly, if the numbers are larger than the register size, lower-level processor instructions must be followed.

0
source

More articles:


All Articles