Обнаружение n-го числа фибоначчи для очень больших «n»

Мне было интересно, как можно найти n-й член последовательности фибоначчи для очень большого значения n, например, 1000000. Используя уравнение рекуррентной школы fib(n)=fib(n-1)+fib(n-2) , требуется 50 минут, чтобы найти 50-й срок!

После googling я узнал о формуле Бине, но это не подходит для значений n> 79, как сказано здесь

Есть ли алгоритм для этого, как и для нахождения простых чисел?

Вы можете использовать метод экспоненциальной матрицы (метод линейной рекурсии). Вы можете найти подробное объяснение и процедуру в этом блоге. Время выполнения – O (log n ).

Я не думаю, что есть лучший способ сделать это.

Вы можете сэкономить много времени, используя memoization . Например, сравните следующие две версии (в JavaScript):

Версия 1 : нормальная recursion

 var fib = function(n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }; 

Версия 2 : memoization

A. использовать библиотеку подчёркивания

 var fib2 = _.memoize(function(n) { return n < 2 ? n : fib2(n - 1) + fib2(n - 2); }); 

Б. без библиотеки

 var fib3 = (function(){ var memo = {}; return function(n) { if (memo[n]) {return memo[n];} return memo[n] = (n <= 2) ? 1 : fib3(n-2) + fib3(n-1); }; })(); 

Первая версия занимает более 3 минут для n = 50 (в Chrome), а вторая занимает меньше 5 мс! Вы можете проверить это в jsFiddle .

Не удивительно, если мы знаем, что временная сложность версии 1 экспоненциальна ( O (2 N / 2 )), а версия 2 - линейна ( O ( N )).

Версия 3 : матричное умножение

Кроме того, мы можем даже сократить временную сложность до O (log ( N )), вычислив умножение N матриц.

матрица

где F n обозначает n- й член последовательности Фибоначчи.

Используйте повторяющиеся идентификаторы http://en.wikipedia.org/wiki/Fibonacci_number#Other_identities, чтобы найти n число в шагах log(n) . Для этого вам придется использовать произвольные целые числа точности. Или вы можете рассчитать точный ответ по модулю некоторого фактора, используя модульную арифметику на каждом шаге.

рекуррентная формула 1

повторная формула 2

повторная формула 3

Заметив, что 3n+3 == 3(n+1) , мы можем разработать однорекурсивную функцию, которая вычисляет два последовательных числа Фибоначчи на каждом шаге, делящем n на 3 и выбирая соответствующую формулу в соответствии с остаточным значением. IOW он вычисляет пару @(3n+r,3n+r+1), r=0,1,2 из пары @(n,n+1) за один шаг, поэтому нет двойной рекурсии, и никакая memoization не нужна ,

Здесь находится код Haskell.

Обновить:

 F(2n-1) = F(n-1)^2 + F(n)^2 === a' = a^2 + b^2 F(2n) = 2 F(n-1) F(n) + F(n)^2 === b' = 2ab + b^2 

похоже, приводит к более быстрому коду. Использование «идентичности последовательности Лукаса» может быть самым быстрым ( это связано с пользователем: primo , который цитирует эту реализацию ).

Большинство людей уже дали вам ссылку, объясняющую обнаружение номера N-го Фибоначчи, кстати, алгоритм Power работает одинаково с незначительными изменениями.

В любом случае это мое решение O (log N).

 public class algFibonacci { // author Orel Eraki // Fibonacci algorithm // O(log2 n) public static int Fibonacci(int n) { int num = Math.abs(n); if (num == 0) { return 0; } else if (num <= 2) { return 1; } int[][] number = { { 1, 1 }, { 1, 0 } }; int[][] result = { { 1, 1 }, { 1, 0 } }; while (num > 0) { if (num%2 == 1) result = MultiplyMatrix(result, number); number = MultiplyMatrix(number, number); num/= 2; } return result[1][1]*((n < 0) ? -1:1); } public static int[][] MultiplyMatrix(int[][] mat1, int[][] mat2) { return new int[][] { { mat1[0][0]*mat2[0][0] + mat1[0][1]*mat2[1][0], mat1[0][0]*mat2[0][1] + mat1[0][1]*mat2[1][1] }, { mat1[1][0]*mat2[0][0] + mat1[1][1]*mat2[1][0], mat1[1][0]*mat2[0][1] + mat1[1][1]*mat2[1][1] } }; } public static void main(String[] args) { System.out.println(Fibonacci(-8)); } } 

Для вычисления чисел Фибоначчи рекурсивный алгоритм является одним из худших способов. Простое добавление двух предыдущих чисел в цикл for (называемый итерационным методом) не займет 2-3 минуты, чтобы вычислить 50-й элемент.

Для вычисления произвольно больших элементов последовательности Фибоначчи вам нужно будет использовать решение закрытой формы – формулу Бине и использовать математику с произвольной точностью, чтобы обеспечить достаточную точность для вычисления ответа.

Однако, используя отношение рекуррентности, не требуется 2-3 минуты для вычисления 50-го термина – вы должны иметь возможность вычислять сроки в миллиарды в течение нескольких секунд на любой современной машине. Похоже, вы используете полностью рекурсивную формулу, что приводит к комбинаторному взрыву рекурсивных вычислений. Простая итеративная формула намного быстрее.

Речь идет о рекурсивном решении:

 int fib(int n) { if (n < 2) return 1; return fib(n-1) + fib(n-2) } 

... и откиньтесь назад и наблюдайте переполнение стека.

Итеративным решением является:

 int fib(int n) { if (n < 2) return 1; int n_1 = 1, n_2 = 1; for (int i = 2; i <= n; i += 1) { int n_new = n_1 + n_2; n_1 = n_2; n_2 = n_new; } return n_2; } 

Обратите внимание, как мы по существу вычисляем следующий член n_new с предыдущих членов n_1 и n_2 , затем «перетасовку» всех членов вниз для следующей итерации. При длительности работы, линейной по значению n , это займет несколько секунд для n в миллиардах (после переполнения целых чисел для ваших промежуточных переменных) на современной гигагерцевой машине.

Я согласен с ответом Уэйна Руни, что оптимальное решение будет завершено в шагах O (log n) , однако общая сложность во время выполнения будет зависеть от сложности используемого алгоритма умножения. Например, с помощью утилиты Karatsuba Multiplication общая сложность во время выполнения была бы O (n log 2 3 ) ≈ O (n 1.585 ) . 1

Тем не менее, усиление матрицы не обязательно является лучшим способом для этого. Как отметил разработчик проекта Nayuki, при экспонировании матрицы выполняются избыточные вычисления, которые можно удалить. Из описания автора:

Учитывая F k и F k + 1 , мы можем вычислить их:


Обратите внимание, что для этого требуется только 3 умножения BigInt-to-BigInt для каждого расщепления, а не 8, поскольку будет показано, что степень экспоненциальности матрицы будет.

Тем не менее, мы можем сделать немного лучше этого. Одна из самых элегантных идентификаторов Фибоначчи связана с номерами Lucas:

где L nn- й номер Lucas . Это тождество можно далее обобщить как:

Существует несколько более или менее эквивалентных способов перехода рекурсивно, но наиболее логично, по-видимому, на F n и L n . Другие идентификаторы, используемые в реализации ниже, могут быть найдены или получены из идентификаторов, перечисленных для последовательностей Lucas :

Для этого требуется только два умножения BigInt-to-BigInt для каждого раскола и только один для конечного результата. Это примерно на 20% быстрее, чем код, предоставленный Project Nayuki ( тестовый скрипт ). Примечание: исходный источник был слегка изменен (улучшен), чтобы обеспечить справедливое сравнение.

 def fibonacci(n): def fib_inner(n): '''Returns F[n] and L[n]''' if n == 0: return 0, 2 u, v = fib_inner(n >> 1) q = (n & 2) - 1 u, v = u * v, v * v + 2*q if (n & 1): u1 = (u + v) >> 1 return u1, 2*u + u1 return u, v u, v = fib_inner(n >> 1) if (n & 1): q = (n & 2) - 1 u1 = (u + v) >> 1 return v * u1 + q return u * v 

Обновить

Грейборд указывает , что вышеупомянутый результат уже был улучшен Такахаши (2000) 2 , отметив, что возведение BigInt обычно (и, в частности, для алгоритма Шенхаге-Штрассена) менее затратно вычислительно дорого, чем умножение BigInt. Автор предлагает итерацию, расщепляющуюся на F n и L n , используя следующие тождества:

Итерации таким образом потребуют два квадрата BigInt для каждого расщепления, а не квадрат BigInt и умножение BigInt, как указано выше. Как и ожидалось, время выполнения заметно выше, чем вышеприведенная реализация, при очень большом n , но несколько медленнее для небольших значений ( n <25000 ).

Тем не менее, это можно улучшить и слегка. Автор утверждает, что: «Известно, что в алгоритме Product Lucas Numbers используется наименьшее количество битовых операций для вычисления числа Фибоначчи F n ». Затем автор решает адаптировать Алгоритм Продукции Алгоритма Лукаса, который в то время был самым быстрым, расщепляющим на F n и L n . Заметим, однако, что L n используется только при вычислении F n + 1 . Это кажется несколько расточительным, если учесть следующие тождества:

где первый берется непосредственно из Такахаши, второй – результат метода экспоненциальной матрицы (также отмеченный Найюки), а третий – результат добавления двух предыдущих. Это позволяет сделать очевидный раскол на F n и F n + 1 . В результате требуется еще одно дополнение BigInt, и, что важно, одно меньшее деление на 2 для четного n ; для нечетного n выигрыш удваивается. На практике это значительно быстрее, чем метод, предложенный Такахаси для небольших n (на 10-15% быстрее) и немного быстрее для очень большого n ( тестовый скрипт ).

 def fibonacci(n): def fib_inner(n): '''Returns F[n] and F[n+1]''' if n == 0: return 0, 1 u, v = fib_inner(n >> 1) q = (n & 2) - 1 u *= u v *= v if (n & 1): return u + v, 3*v - 2*(u - q) return 2*(v + q) - 3*u, u + v u, v = fib_inner(n >> 1) # L[m] l = 2*v - u if (n & 1): q = (n & 2) - 1 return v * l + q return u * l 

1 Можно видеть, что число цифр (или бит) F n ~ O (n) как:

Сложность выполнения с использованием умножения Карацубы может быть затем рассчитана как:


2 Takahashi, D. (2000), «Быстрый алгоритм для вычисления больших чисел Фибоначчи» (PDF), Письма по обработке информации 75 , стр. 243-246.

Во-первых, вы можете сформировать представление о самом высоком члене от самого большого известного термина Фибоначчи . также см. прохождение рекурсивного представления функции Фибоначчи . Интересный подход к этому вопросу приведен в этой статье . Кроме того, попробуйте прочитать об этом в худшем алгоритме в мире? ,

У меня есть исходный код в c для вычисления даже 3500-го числа фибоначчи: – для более подробной информации посетите

http://codingloverlavi.blogspot.in/2013/04/fibonacci-series.html

исходный код в C: –

 #include #include #define max 2000 int arr1[max],arr2[max],arr3[max]; void fun(void); int main() { int num,i,j,tag=0; clrscr(); for(i=0;i0;i--) { if(arr3[i]>9) { temp=arr3[i]; arr3[i]%=10; arr3[i-1]+=(temp/10); } } } 

Я решил проблемы с UVA: 495 – Замораживание Фибоначчи

Он генерирует все числа Фибоначчи до 5000 и выводит выходные данные для заданных входов (диапазон 1-5000).

Он принимается во время работы 00.00 сек.

Число Фибоначчи для 5000:

3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

 #include #include #define LIMIT 5001 #define MAX 1050 char num[LIMIT][MAX]; char result[MAX]; char temp[MAX]; char* sum(char str1[], char str2[]) { int len1 = strlen(str1); int len2 = strlen(str2); int minLen, maxLen; int i, j, k; if (len1 > len2) minLen = len2, maxLen = len1; else minLen = len1, maxLen = len2; int carry = 0; for (k = 0, i = len1 - 1, j = len2 - 1; k 0) { result[maxLen] = carry + '0'; maxLen++; result[maxLen] = '\0'; } else { result[maxLen] = '\0'; } i = 0; while (result[--maxLen]) { temp[i++] = result[maxLen]; } temp[i] = '\0'; return temp; } void generateFibonacci() { int i; num[0][0] = '0'; num[0][1] = '\0'; num[1][0] = '1'; num[1][1] = '\0'; for (i = 2; i <= LIMIT; i++) { strcpy(num[i], sum(num[i - 1], num[i - 2])); } } int main() { //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int N; generateFibonacci(); while (scanf("%d", &N) == 1) { printf("The Fibonacci number for %d is %s\n", N, num[N]); } return 0; } 

Вот версия python для вычисления n-го числа Фибоначчи в O (log (n))

 def fib(n): if n == 0: return 0 if n == 1: return 1 def matmul(M1, M2): a11 = M1[0][0]*M2[0][0] + M1[0][1]*M2[1][0] a12 = M1[0][0]*M2[0][1] + M1[0][1]*M2[1][1] a21 = M1[1][0]*M2[0][0] + M1[1][1]*M2[1][0] a22 = M1[1][0]*M2[0][1] + M1[1][1]*M2[1][1] return [[a11, a12], [a21, a22]] def matPower(mat, p): if p == 1: return mat m2 = matPower(mat, p//2) if p % 2 == 0: return matmul(m2, m2) else: return matmul(matmul(m2, m2),mat) Q = [[1,1],[1,0]] q_final = matPower(Q, n-1) return q_final[0][0] 

Я написал реализацию C , которая поддерживает любую шкалу ввода номера с GNU gmp .

Время фибринга для одного числа – O(n) , а для кеша – O(1) , (фактически он вычислял все фиды для 0 ~ n) .


Код

fib_cached_gmp.c:

 // fibonacci - cached algorithm - any scale of input with GMP, #include  #include  #include  // a single step, void fib_gmp_next(mpz_t *cache) { mpz_add(cache[2], cache[0], cache[1]); mpz_set(cache[0], cache[1]); mpz_set(cache[1], cache[2]); } // figure fib for a single number, in O(n), mpz_t *fib_gmp(int n, mpz_t *result) { // init cache, mpz_t cache[3]; // number: [fib(n-2), fib(n-1), fib(n)], mpz_init(cache[0]); mpz_init(cache[1]); mpz_init(cache[2]); mpz_set_si(cache[0], 0); mpz_set_si(cache[1], 1); while (n >= 2) { fib_gmp_next(cache); n--; } mpz_set(*result, cache[n]); return result; } // test - print fib from 0 to n, tip: cache won't be reused betwwen any 2 input numbers, void test_seq(int n) { mpz_t result; mpz_init(result); for (int i = 0; i <= n; i++) { gmp_printf("fib(%2d): %Zd\n", i, fib_gmp(i, &result)); } } // test - print fib for a single num, void test_single(int x) { mpz_t result; mpz_init(result); gmp_printf("fib(%d): %Zd\n", x, fib_gmp(x, &result)); } int main() { // test sequence, test_seq(100); // test single, test_single(12345); return 0; } , // fibonacci - cached algorithm - any scale of input with GMP, #include  #include  #include  // a single step, void fib_gmp_next(mpz_t *cache) { mpz_add(cache[2], cache[0], cache[1]); mpz_set(cache[0], cache[1]); mpz_set(cache[1], cache[2]); } // figure fib for a single number, in O(n), mpz_t *fib_gmp(int n, mpz_t *result) { // init cache, mpz_t cache[3]; // number: [fib(n-2), fib(n-1), fib(n)], mpz_init(cache[0]); mpz_init(cache[1]); mpz_init(cache[2]); mpz_set_si(cache[0], 0); mpz_set_si(cache[1], 1); while (n >= 2) { fib_gmp_next(cache); n--; } mpz_set(*result, cache[n]); return result; } // test - print fib from 0 to n, tip: cache won't be reused betwwen any 2 input numbers, void test_seq(int n) { mpz_t result; mpz_init(result); for (int i = 0; i <= n; i++) { gmp_printf("fib(%2d): %Zd\n", i, fib_gmp(i, &result)); } } // test - print fib for a single num, void test_single(int x) { mpz_t result; mpz_init(result); gmp_printf("fib(%d): %Zd\n", x, fib_gmp(x, &result)); } int main() { // test sequence, test_seq(100); // test single, test_single(12345); return 0; } 

Сначала установите gmp:

 // for Ubuntu, sudo apt-get install libgmp3-dev 

Обобщение:

 gcc fib_cached_gmp.c -lgmp 

Выполнение:

 ./a.out 

Пример вывода:

 fib( 0): 0 fib( 1): 1 fib( 2): 1 fib( 3): 2 fib( 4): 3 fib( 5): 5 fib( 6): 8 fib( 7): 13 fib( 8): 21 fib( 9): 34 fib(10): 55 fib(11): 89 fib(12): 144 fib(13): 233 fib(14): 377 fib(15): 610 fib(16): 987 fib(17): 1597 fib(18): 2584 fib(19): 4181 fib(20): 6765 fib(21): 10946 fib(22): 17711 fib(23): 28657 fib(24): 46368 fib(25): 75025 fib(26): 121393 fib(27): 196418 fib(28): 317811 fib(29): 514229 fib(30): 832040 fib(31): 1346269 fib(32): 2178309 fib(33): 3524578 fib(34): 5702887 fib(35): 9227465 fib(36): 14930352 fib(37): 24157817 fib(38): 39088169 fib(39): 63245986 fib(40): 102334155 fib(41): 165580141 fib(42): 267914296 fib(43): 433494437 fib(44): 701408733 fib(45): 1134903170 fib(46): 1836311903 fib(47): 2971215073 fib(48): 4807526976 fib(49): 7778742049 fib(50): 12586269025 fib(51): 20365011074 fib(52): 32951280099 fib(53): 53316291173 fib(54): 86267571272 fib(55): 139583862445 fib(56): 225851433717 fib(57): 365435296162 fib(58): 591286729879 fib(59): 956722026041 fib(60): 1548008755920 fib(61): 2504730781961 fib(62): 4052739537881 fib(63): 6557470319842 fib(64): 10610209857723 fib(65): 17167680177565 fib(66): 27777890035288 fib(67): 44945570212853 fib(68): 72723460248141 fib(69): 117669030460994 fib(70): 190392490709135 fib(71): 308061521170129 fib(72): 498454011879264 fib(73): 806515533049393 fib(74): 1304969544928657 fib(75): 2111485077978050 fib(76): 3416454622906707 fib(77): 5527939700884757 fib(78): 8944394323791464 fib(79): 14472334024676221 fib(80): 23416728348467685 fib(81): 37889062373143906 fib(82): 61305790721611591 fib(83): 99194853094755497 fib(84): 160500643816367088 fib(85): 259695496911122585 fib(86): 420196140727489673 fib(87): 679891637638612258 fib(88): 1100087778366101931 fib(89): 1779979416004714189 fib(90): 2880067194370816120 fib(91): 4660046610375530309 fib(92): 7540113804746346429 fib(93): 12200160415121876738 fib(94): 19740274219868223167 fib(95): 31940434634990099905 fib(96): 51680708854858323072 fib(97): 83621143489848422977 fib(98): 135301852344706746049 fib(99): 218922995834555169026 fib(100): 354224848179261915075 fib(12345): 

Советы:

  • test_seq() не очень умный, он не использовал кеш между двумя номерами ввода.
    Хотя на самом деле одного вызова fib_gmp() было бы достаточно, если вы добавите gmp_printf() в fib_gmp_next() и предоставьте i на fib_gmp_next() на каждом шаге.
    Во всяком случае, это просто для демонстрации.

вот короткий код на Python, хорошо работает до 7 цифр. Просто требуется массив из 3 элементов

 def fibo(n): i=3 l=[0,1,1] if n>2: while i<=n: l[i%3]= l[(i-1) % 3] + l[(i-2) % 3] i+=1 return l[n%3] 

Если вы используете C #, взгляните на Lync и BigInteger. Я пробовал это с 1000000 (фактически 1000001, поскольку я пропускаю первый 1000000) и был ниже 2 минут (00: 01: 19.5765).

 public static IEnumerable Fibonacci() { BigInteger i = 0; BigInteger j = 1; while (true) { BigInteger fib = i + j; i = j; j = fib; yield return fib; } } public static string BiggerFib() { BigInteger fib = Fibonacci().Skip(1000000).First(); return fib.ToString(); } 

Более элегантное решение в python

 def fib(n): if n == 0: return 0 a, b = 0, 1 for i in range(2, n+1): a, b = b, a+b return b 
 #include  #define MOD 1000000007 using namespace std; const long long int MAX = 10000000; // Create an array for memoization long long int f[MAX] = {0}; // Returns n'th fuibonacci number using table f[] long long int fib(int n) { // Base cases if (n == 0) return 0; if (n == 1 || n == 2) return (f[n] = 1); if (f[n]) return f[n]; long long int k = (n & 1)? (n+1)/2 : n/2; f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1)) %MOD : ((2*fib(k-1) + fib(k))*fib(k))%MOD; return f[n]; } int main() { long long int n = 1000000; printf("%lld ", fib(n)); return 0; } 

Сложность времени: O (Log n), когда мы делим проблему на половину в каждом рекурсивном вызове.

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

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


 public class FabSeries { private static Map memo = new TreeMap<>(); public static BigInteger fabMemorizingTech(BigInteger n) { BigInteger ret; if (memo.containsKey(n)) return memo.get(n); else { if (n.compareTo(BigInteger.valueOf(2)) <= 0) ret = BigInteger.valueOf(1); else ret = fabMemorizingTech(n.subtract(BigInteger.valueOf(1))).add( fabMemorizingTech(n.subtract(BigInteger.valueOf(2)))); memo.put(n, ret); return ret; } } public static BigInteger fabWithoutMemorizingTech(BigInteger n) { BigInteger ret; if (n.compareTo(BigInteger.valueOf(2)) <= 0) ret = BigInteger.valueOf(1); else ret = fabWithoutMemorizingTech(n.subtract(BigInteger.valueOf(1))).add( fabWithoutMemorizingTech(n.subtract(BigInteger.valueOf(2)))); return ret; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println("Enter Number"); BigInteger num = scanner.nextBigInteger(); // Try with memorizing technique Long preTime = new Date().getTime(); System.out.println("Stats with memorizing technique "); System.out.println("Fibonacci Value : " + fabMemorizingTech(num) + " "); System.out.println("Time Taken : " + (new Date().getTime() - preTime)); System.out.println("Memory Map: " + memo); // Try without memorizing technique.. This is not responsive for large // value .. can 50 or so.. preTime = new Date().getTime(); System.out.println("Stats with memorizing technique "); System.out.println("Fibonacci Value : " + fabWithoutMemorizingTech(num) + " "); System.out.println("Time Taken : " + (new Date().getTime() - preTime)); } } 

Введите номер

40

Статистика с техникой запоминания

Значение Фибоначчи: 102334155

Время: 5

Карта памяти: {1 = 1, 2 = 1, 3 = 2, 4 = 3, 5 = 5, 6 = 8, 7 = 13, 8 = 21, 9 = 34, 10 = 55, 11 = 89, 12 = 144, 13 = 233, 14 = 377, 15 = 610, 16 = 987, 17 = 1597, 18 = 2584, 19 = 4181, 20 = 6765, 21 = 10946, 22 = 17711, 23 = 28657, 24 = 46368, 25 = 75025, 26 = 121393, 27 = 196418, 28 = 317811, 29 = 514229, 30 = 832040, 31 = 1346269, 32 = 2178309, 33 = 3524578, 34 = 5702887, 35 = 9227465, 36 = 14930352, 37 = 24157817, 38 = 39088169, 39 = 63245986, 40 = 102334155}

Статистика без запоминания техники

Значение Фибоначчи: 102334155

Время съемки: 11558

Вычисление чисел фибоначчи (с использованием Haskell):

Версия 1 : Прямой перевод определения в код (очень медленная версия):

 fib :: Integer -> Integer fib 0 = 1 fib 1 = 1 fib n = fib (n - 1) + fib (n - 2) 

Версия 2 : Используя выполненную нами работу для вычисления F_ {n – 1} и F_ {n – 2} (быстрая версия):

 fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 

Вы можете получить n-й фибоначчи, просто делая fibs !! n где n – индекс.

Версия 3 : Использование метода матричной мультипликации. (еще более быстрая версия):

 -- declaring a matrix data Matrix = Matrix ( (Integer, Integer) , (Integer, Integer) ) deriving (Show, Eq) -- creating it an instance of Num -- so that if we implement (*) we get (^) for free instance Num Matrix where (*) = mMult -- don't need these (+) = undefined negate = undefined fromInteger = undefined abs = undefined signum = undefined -- 2-d matrix multiplication mMult :: Matrix -> Matrix -> Matrix mMult (Matrix ((a11, a12), (a21, a22))) (Matrix ((b11, b12), (b21, b22))) = Matrix ( (a11 * b11 + a12 * b21, a11 * b12 + a12 * b22) , (a21 * b11 + a22 * b21, a21 * b12 + a22 * b22) ) -- base matrix for generating fibonacci fibBase :: Matrix fibBase = Matrix ((1,1), (1,0)) -- get the large fibonacci numbers fastFib :: Int -> Integer fastFib n = let getNth (Matrix ((_, a12), _)) = a12 in getNth (fibBase ^ n) 

Я сделал программу. Это не займет много времени, чтобы рассчитать значения, но максимальный срок, который может быть отображен, – 1477-й (из-за максимального диапазона для двойного). Результаты появляются почти мгновенно. Серия начинается с 0. Если есть какие-либо улучшения, пожалуйста, не стесняйтесь их редактировать.

 #include using namespace std; void fibseries(long int n) { long double x=0; double y=1; for (long int i=1;i<=n;i++) { if(i%2==1) { if(i==n) { cout<>n; fibseries(n); return 0; } 

Простейшая реализация Pythonic может быть представлена ​​следующим образом

 def Fib(n): if (n < 0) : return -1 elif (n == 0 ): return 0 else: a = 1 b = 1 for i in range(2,n+1): a,b = b, a+b return a 

Эта реализация JavaScript обрабатывает nthFibonacci (1200) без проблем:

 var nthFibonacci = function(n) { var arr = [0, 1]; for (; n > 1; n--) { arr.push(arr.shift() + arr[0]) } return arr.pop(); }; console.log(nthFibonacci(1200)); // 2.7269884455406272e+250 

Имея некоторые знания о дискретной математике, вы можете найти любое число Фибоначчи в постоянное время O (1). There is something called Linear Homogeneous Recurrence Relation .

Fibonacci sequence is an famous example.

To find the nth Fibonacci number we need to find that

е

Мы знаем это

f1

где

f2

Then, the Characteristic equation is

f3

After finding the roots of the characteristic equation and substituting in the first equation

f4

Finally, we need to find the value of both alpha 1 & alpha 2

Ф.Ф.

Now, you can use this equation to find any Fibonacci number in O(1).

Давайте будем гением компьютера.