о количестве битов, необходимых для числа Фибоначчи

Question

Я читаю книгу алгоритмов С.ДасГупта.Ниже приведен фрагмент текста из числа, касающегося количества бит, требуемого для n-го числа Фибоначчи.

Целесообразно рассматривать сложение как один шаг компьютера, если добавляются небольшие числа, говорят 32-битные числа.Но n-е число Фибоначчи имеет длину около 0,694n бит, и оно может значительно превышать 32 с ростом n.Арифметические операции с произвольно большими числами невозможно выполнить за один шаг с постоянным временем.

Мой вопрос, например, для числа Фибоначчи F1 = 1, F2 = 1, F3 = 2 искоро.затем подстановка «n» в вышеприведенной формуле, т. е. 0,694n для F1 составляет приблизительно 1, F2 составляет приблизительно 2 бита, но для F3 и так далее приведенная выше формула не выполняется.Мне кажется, я не совсем понял, что здесь имеет в виду автор. Может ли кто-нибудь помочь мне понять это?

Спасибо

Answer 1

Ну

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

Требуются биты, округляется бревно базы-2, так что для меня этого достаточно.

Значение 0,694 исходит из того факта, что F(n) является ближайшим целым числом к ​​(& phi; ⁿ ) / & radic; 5. Так что log(F(n)) равно n * log(phi) - log(sqrt(5)), а log(phi) равно 0,694. Когда n становится больше, log(sqrt(5)) и округление быстро становятся незначительными.

Answer 2

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

Answer 3

Прежде всего, слово about очень важно, как и в the nth Fibonacci number is about 0.694n bits long. Во-вторых, я думаю, что автор имеет в виду, когда n->infinity. Попробуйте большой номер и проверьте:)

Answer 4

Автор в основном описывает, как большие числа влияют на производительность алгоритма. Чтобы быть чрезмерно простым, процессор может очень быстро добавлять числа с размером регистра, если числа превышают размер регистра, необходимо выполнить инструкции процессора более низкого уровня.

Answer 5

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 бита.

Answer 6

Я думаю, что он просто использует числа Фибоначчи, чтобы проиллюстрировать его точку зрения, что для больших чисел (> 32 бит) сложение нельзя больше считать постоянным, потому что оно включает в себя больше, чем отдельная инструкция на процессоре.

Почему формула не работает? Для F3 = 2 двоичному представлению требуется 2 бита (3 * 0,694 = 2,082). Возьмем F50 = 12586269025, который можно представить с использованием 33 бит (50 * 0,694 = 35), который все еще достаточно близок к истинному значению.

Answer 7

Вы не можете сказать, что полубита ... количество бит должно быть округлено

, так что это означает

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

, поэтому округляется в большую сторону для n> 32 и 32 для n<32 </p>

для 32-битных систем, что составляет

, и число может быть неточным