Вычисление числа Фибоначчи точно в C++?

Question

Я действительно смущен. Я пытаюсь рассчитать числа Фибоначчи, но по мере того, как они становятся все большими и большими, цифры начинают ошибаться. и я не знаю почему.

Как вы вычисляете точные числа Фибоначчи с помощью формулы Бине, я понимаю, что это всегда должно возвращать целое число?

Вот что я пытался с этим работать.

http://ideone.com/e6t6h

См, как число растет. это все странно?

здесь Я распечатываю его с помощью cout.precision (15);

http://ideone.com/XREh2

здесь я распечатать его с соиЬ < < < < фиксированной бла-бла;

Здесь я использовал процедурный цикл, чтобы вычислить его, идя через итерации.

Этот вариант является более точным, чем тот, который использует формулу Бине.

В любом случае. у кого есть какой-нибудь код, на который я могу посмотреть, который может вычислить F (n) с необходимостью итерации, хотя каждый уровень (n), используя формулу Бине?

Answer 1

Для точного расчета чисел Фибоначчи, используя формулу Бине, вам нужна точная интерпретация √ 5. Так как √ 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 могут быть точно представлены как double (плюс несколько более крупных, делящихся на достаточно высокие степени 2). Последний номер Фибоначчи, меньший, чем 2 - F (77), но F (78) делится на 8, поэтому также точно представляется в виде double с 53 битами точности.Однако приведенное выше дает правильные результаты только для n <= 70 здесь, с 71 по, ошибка округления слишком велика (кстати, результат формулы Бине с использованием doubles здесь всегда слишком велик, поэтому использование floor вместо round приведет к правильному результату также для 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 }; 

подстановок Для получения точных результатов необходимо лечить √ 5 (и/или φ) в качестве символической константы и оценивать формулу, используя это. Это равносильно оценке формулы в кольце

ℤ[φ] = { a + b*φ : a, b ∈ ℤ } 

алгебраических чисел в ℚ(√5), используя тот факт, что φ² = 1 + φ. Эквивалент формулы Бине является

φ^n = F(n-1) + φ*F(n) 

, которые могут быть использованы для эффективного вычисления чисел Фибоначчи путем повторного возведения в квадрат в O (журнал N) шагов (но обратите внимание, что Р (п) имеет Θ (N) бит, так что число разрядные операции не могут быть ниже O (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, что позволяет быстрое вычисление больших чисел Фибоначчи. Но, конечно, библиотеки произвольной точности часто снабжаются своими оптимизированными функциями Фибоначчи, поэтому для их реализации это довольно разумно.

Answer 2

Вы пробовали в том числе <cmath>, а не <math.h>, math.h, возможно, не перегруженную версию SQRT как для C

Answer 3

В общем, поплавки и двойники не предназначены для представления чисел точно. Их цель - представлять действительные числа в широком диапазоне. Если вы хотите бесконечной точности, вы можете попробовать, глядя в http://gmplib.org/