Чтобы точно рассчитать числа Фибоначчи по формуле Бине, вам нужна точная интерпретация & radic; 5. Поскольку & radic; 5 иррационально, его нельзя точно представить, используя double или float, поэтому формула Бине не работает с этими типами (однако округление в вычислениях приводит к точным результатам для некоторых небольших входных данных). Так как числа Фибоначчи являются целыми числами, вы можете получить точные результаты по формуле Бине, используя double или float для большего количества аргументов, округлив впоследствии,
double binet(unsigned int n)
{
static const double phi = (1 + sqrt(5))*0.5;
double fib = (pow(phi,n) - pow(1-phi,n))/sqrt(5);
return round(fib);
}
Это вернет правильный результат для почти всех n достаточно малых, чтобы результат мог быть точно представлен как double. Это не много, однако. A double обычно имеет точность только 53 бита, поэтому только числа Фибоначчи, меньшие 2 53 , могут быть точно представлены как double (плюс несколько больших, делимых на достаточно большие степени 2). Последнее число Фибоначчи, меньшее 2 53 , равно F (77), но F (78) делится на 8, поэтому также может быть точно представлено как double с точностью 53 бита. Однако приведенное выше дает правильные результаты только для n <= 70, здесь, начиная с 71, ошибка округления слишком велика (кстати, результат формулы Бине, использующей doubles, здесь всегда слишком велик, поэтому вместо * используется floor 1020 * даст правильный результат также для F (71), но не дальше).
При стандартных типах данных не так уж много представляемых чисел Фибоначчи, последний из 64-битных типов (без знака) - F (93); для 128 бит последний F (186). Для столь малых индексов практически ничего нельзя получить по сравнению с простым итеративным алгоритмом
unsigned long long fibonacci(unsigned int n)
{
unsigned long long a = 0, b = 1;
for(; n > 0; --n)
{
b += a;
a = b-a;
}
return a;
}
, если вы не используете справочную таблицу
static const unsigned long long fibs[94] = { 0, 1, 1, 2, ... , 12200160415121876738ull };
Для получения точных результатов нужно рассматривать & radic; 5 (и / или & phi;) как символическую константу и оценивать формулу, используя ее. Это равносильно оценке формулы в кольце
ℤ[φ] = { a + b*φ : a, b ∈ ℤ }
алгебраических целых чисел в ℚ(√5), используя тот факт, что φ² = 1 + φ. Эквивалент Бине формулы
φ^n = F(n-1) + φ*F(n)
, который можно использовать для эффективного вычисления чисел Фибоначчи путем многократного возведения в квадрат с O (log n) шагами (но учтите, что F (n) имеет & Theta; (n) битов, поэтому число битовых операций не может быть меньше, чем На)). Немного более эффективная версия, чем ванильный повторный квадрат
φ^(2n) = (φ^n)² = (F(n-1) + φ*F(n))² = F(n-1)² + φ*2*F(n-1)*F(n) + φ²*F(n)²
= (F(n-1)² + F(n)²) + φ*(2*F(n-1)*F(n) + F(n)²)
найти F(2n) = 2*F(n)*F(n-1) + F(n)² = 2*F(n)*F(n+1) - F(n)² = F(n)*(F(n+1) + F(n-1)) и F(2n+1) = F(n)² + F(n+1)², используя φ² = 1 + φ. Эти формулы позволяют вычислять F (2n), F (2n + 1) и F (2n + 2) из F (n) и F (n + 1) с не более чем двумя умножениями и двумя сложениями / вычитаниями на число, что дает Алгоритм для вычисления пары (F(n),F(n+1)) в O (log n) шагах только с двумя числами в качестве состояния (повторное возведение в квадрат ванили использует четыре числа в качестве состояния и требует еще нескольких умножений).
Итерационный алгоритм слева направо равен
unsigned long long fib(unsigned int n){
if (n == 0) return 0;
unsigned int h = n/2, mask = 1;
// find highest set bit in n, can be done better
while(mask <= h) mask <<= 1;
mask >>= 1;
unsigned long long a = 1, b = 1, c; // a = F(k), b = F(k+1), k = 1 initially
while(mask)
{
c = a*a+b*b; // F(2k+1)
if (n&mask)
{
b = b*(b+2*a); // F(2k+2)
a = c; // F(2k+1)
} else {
a = a*(2*b-a); // F(2k)
b = c; // F(2k+1)
}
mask >>= 1;
}
return a;
}
С произвольным типом точности вместо unsigned long long, что позволяет быстро вычислять большие числа Фибоначчи. Но, разумеется, библиотеки произвольной точности часто поставляются с собственными оптимизированными функциями Фибоначчи, так что это своего рода самореализация для реализации самостоятельно.