Время вычисления Фибоначчи

Question

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

Написано в C

рекурсивной решение:

int main(int argc, const char * argv[]) { 
    int n, i = 0, c; 
    printf("Please enter an integer:\n"); 
    scanf("%d", &n); 
    for (c = 1 ; c <= n ; c++) 
    { 
     printf("%lu ", fibonacci(i)); 
     i++; 
    } 
    return 0; 
    } 

long fibonacci(long n) 
{ 
    if (n == 0) 
     return 0; 
    else if (n == 1) 
     return 1; 
    else 
     return (fibonacci(n-1) + fibonacci(n-2)); 
}; 

для цикла решения:

int main(int argc, const char * argv[]) { 
int n, first = 0, second = 1, next, c; 
    printf("Please enter an integer:\n"); 
    scanf("%d", &n); 
    for (c = 0 ; c < n ; c++) 
    { 
     if (c <= 1) 
      next = c; 
     else 
     { 
      next = first + second; 
      first = second; 
      second = next; 
     } 
     printf("%d ",next); 
    } 
    return 0; 
}; 

Answer 1

Обычный метод рекурсии чрезвычайно медленный по сравнению с хвостовыми рекурсивными и итеративными версиями. В приведенном ниже примере для версии итерации используется развернутый цикл вместе с Duff's Device для ввода цикла. Для 32-битных целых чисел без знака предел равен fib (47), для 64-битных целых чисел без знака предел равен fib (93).

Сроки были выполнены с Intel 2600K 3.4ghz, XP X64, 64-разрядным режимом. Частота счетчика XP или XP X64 - это то же самое, что и часы процессора, 3.4ghz, но накладные расходы операционной системы (например, прерывания) влияют на время, если продолжительность мала.

тайминги для FIB (40):

fibr() # of microseconds 485468.8 
fibt() # of microseconds   0.2 
fibi() # of microseconds   0.2 

синхронизации в течение 94 циклов, п = 0 до 93:

fibt() # of microseconds   7 
fibi() # of microseconds   5 

Пример кода:

typedef unsigned long long UI64; 

UI64 fibr(UI64 n) 
{ 
    if(n < 2) 
     return n; 
    return fibr(n-1) + fibr(n-2); 
} 

// call with fibt(n, 0, 1) 
UI64 fibt(UI64 n, UI64 res, UI64 next) 
{ 
    if (n == 0) 
     return res; 
    return fibt(n - 1, next, res + next); 
} 

UI64 fibi(UI64 n) 
{ 
UI64 f0, f1, i; 
    if(n < 2) 
     return n; 
    n -= 2; 
    f1 = f0 = 1; 
    i = 0; 
    switch(n%8){ 
     do{ 
      f1 += f0; 
      case 7: 
      f0 += f1; 
      case 6: 
      f1 += f0; 
      case 5: 
      f0 += f1; 
      case 4: 
      f1 += f0; 
      case 3: 
      f0 += f1; 
      case 2: 
      f1 += f0; 
      case 1: 
      f0 += f1; 
      case 0: 
      continue; 
     }while(n >= (i += 8)); 
    } 
    return f0; 
} 

Альтернативный вариант Фиби(), без проверки n < 2. Что f0 и f1 представляют изменения в цикле, предназначенные для конечной суммы в f0, поэтому начальное состояние того, что f0 и f1 представляют, зависит от того, является ли n четным или нечетным. Если n четно, f0 = fib (0) = 0, f1 = fib (-1) = 1, если n нечетно, f1 = fib (0) = 0, f0 = fib (-1) = 1. (Если вам интересно, fib (-1) = 1, fib (-2) = -1, fib (-3) = 2, fib (-4) = -3, fib (-5) = 5, fib (-6) = -8, ...).

Для объяснения логики здесь для n четного случая fib (-1) = f1 = 1, fib (0) = f0 = 0, то fib (1) = (f1 + = f0), fib (2) = (f0 + = f1), fib (3) = (f1 + = f0), fib (4) = (f0 + = f1), ....

UI64 fibi(UI64 n) 
{ 
UI64 f0, f1, i; 
    f0 = n & 1;   // if n even, f0=0, f1=1 
    f1 = 1 - f0;  // else  f1=0, f0=1 
    i = 0; 
    switch(n%8){ 
     do{ 
      f1 += f0; 
      case 7: 
      f0 += f1; 
      case 6: 
      f1 += f0; 
      case 5: 
      f0 += f1; 
      case 4: 
      f1 += f0; 
      case 3: 
      f0 += f1; 
      case 2: 
      f1 += f0; 
      case 1: 
      f0 += f1; 
      case 0: 
      continue; 
     }while(n >= (i += 8)); 
    } 
    return f0; 
} 

Answer 2

для цикла решения быстрее. Причины:

1. нет вызовов функций (при условии, что вызовы функций являются дорогостоящими)
2. вычисления n-е использует n дополнения (итерации цикла n раза), в то время как рекурсивное решение использует добавление каждого вызова функции, которая подводит до O(1.6n) звонки, следовательно O(1.6n) добавление. Стоимость исходила от двойных рекурсивных вызовов - когда рекурсивная функция запрашивала n-й элемент, ей нужно было снова вычислить n-1-й и n-2-й элементы с самого начала, но не помню их.

Answer 3

Для петли это не обязательно быстрее. В обычных языках, таких как Java, C и Python, рекурсия довольно дорога по сравнению с итерацией, потому что для этого требуется выделение нового фрейма стека.

В C/C++ можно исключить возможность оптимизации компилятора для выполнения хвостовой рекурсии, которая преобразует определенные типы рекурсии (фактически, определенные типы хвостовых вызовов) в переходы вместо вызовов функций. Чтобы компилятор выполнял эту оптимизацию, необходимо, чтобы последнее, что функция делает перед тем, как она вернется, вызывает другую функцию (в этом случае сама).

Примером функции Фибоначчи может быть, как это:

int fib_tail(int n, int res, int next) 
{ 
    if (n == 0) { 
    return res; 
    } 
    return fib_tail(n - 1, next, res + next); 
} 

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

Я недавно написал об этом article.

Надеюсь, это поможет.

Answer 4

Как вы измерили разницу в скорости?

Наивная рекурсивная реализация функции Фибоначчи занимает около 100 миллионов вызовов функций для вычисления f (40). На современном компьютере, который будет достаточно быстрым, чтобы вы не могли на это смотреть с секундомером.

Расчет f (50) занимает около 10 миллиардов вызовов функций, что будет заметной задержкой. f (60) принимает триллион вызовов функций или около часа. f (70) принимает около 200 триллионов вызовов функций или несколько дней. f (80) принимает около 20 квадриллионов вызовов функций или около года.

Я бы не назвал эту разницу академической.