una suma sucesion serie secuencia programacion programa para numeros hacer ejercicios como codigo algoritmo algorithm math fibonacci

algorithm - suma - Encontrar el n-ésimo número de fibonacci para una gran ''n''



sucesion de fibonacci ejercicios (22)

Aquí hay una versión de Python para calcular el n. ° número de Fibonacci en 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]

Me preguntaba cómo se puede encontrar el enésimo término de la secuencia de fibonacci para un valor muy grande de, digamos, 1000000. Utilizando la ecuación de recurrencia de la escuela primaria fib(n)=fib(n-1)+fib(n-2) , ¡toma de 2 a 3 minutos encontrar el 50º término!

Después de buscar en Google, llegué a conocer la fórmula de Binet, pero no es apropiada para valores de n> 79, como se dice here

¿Hay un algoritmo para hacerlo así como tenemos para encontrar números primos?

Cálculo de números de Fibonacci (usando Haskell):

Versión 1 : traducción directa de la definición a código (versión muy lenta):

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

Versión 2 : Usando el trabajo que hemos hecho para calcular F_ {n - 1} y F_ {n - 2} (la versión rápida):

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

¡Puedes obtener el n. ° 3 de fibonacci simplemente haciendo fibs !! n fibs !! n donde n es el índice.

Versión 3 : Uso de la técnica de multiplicación de matriz. (la versión aún más rápida):

-- 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)

Escribí una implementación en C , que admite cualquier escala de número de entrada con GNU gmp .

El tiempo para calcular fib para un solo número es O(n) , y el espacio para el caché es O(1) , (en realidad se calculó todo fib para 0 ~ n) .

Código

fib_cached_gmp.c:

// fibonacci - cached algorithm - any scale of input with GMP, #include <gmp.h> #include <stdio.h> #include <stdlib.h> // 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; }

Instalar gmp primero:

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

Compilar:

gcc fib_cached_gmp.c -lgmp

Ejecutar:

./a.out

Ejemplo de salida:

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): 400805695072240470970514993214065752192289440772063392234116121035966330621821050108284603033716632771086638046166577665205834362327397885009536790892524821512145173749742393351263429067658996935575930135482780507243981402150702461932551227590433713277255705297537428017957026536279252053237729028633507123483103210846617774763936154673522664591736081039709294423865668046925492747583953758325850613548914282578320544573036249175099094644435323970587790740267131607004023987409385716162460955707793257532112771932704816713519196128834470721836094265012918046427449156654067195071358955104097973710150920536847877434256779886729555691213282504703193401739340461924048504866698176130757935914248753973087073009601101912877383634628929467608983980664185363370286731771712542583041365328648124549323878806758395652340861186334027392307091079257180835672989798524084534677252369585918458720952520972332496025465803523315515681084895362126005441170936820059518262349022456888758938672920855739736423917065122816343192172271301981007636070751378441363091187289522144227851382197807194256392294919912037019476582418451273767976783751999133072126657949249799858935787018952232743400610036315564885371356712960608966755186612620425868892621106627825137425386831657368826398245606147944273998498356443362170133234924531673939303668042878258282104212769625245680321344034442698232414181912301904509531018692483863038992377680591406376081935756597411807864832452421993121459549055042253305545594009110753730302061881025182053074077930494574304284381890534053065639084253641881363463311184024281835265103884539012874542416238100890688593076189105555658375552988619203325356676814545718066196038345684671830102920209857682912971565838896011294918349088792184108318689299230788355618638040186790724351073650210514429114905535411044888774713860041341593318365792673354888566799196442017231870631867558530906286613228902689695061557951752309687806567573290910909535395758148994377158637050112347651517847188123790794231572729345617619677555583207012253101701328971768827861922408064379891201972881554890367344239218306050355964382953279316318309272212482218232309006973312977359562553184608144571713073802285675503209229581312057259729362382786183100343961484090866057560474044189870633912200595478051573769889968342203512550302655117491740823696686983281784153050366346823513213598551985596176977626982962058849363351794302206703907577970065793839511591930741441079234179943480206539767561244271325923343752071038968002157889912694947204003637791271084190929058369801531787887444598295425899927970

Consejos:

  • test_seq() no es muy inteligente, no reutilizó el caché entre 2 números de entrada.
    Si bien en realidad fib_gmp() una sola llamada a fib_gmp() , si agrega un gmp_printf() a fib_gmp_next() y proporciona el i a fib_gmp_next() en cada paso.
    De todos modos, es solo para demostración.

Estoy de acuerdo con share que la solución óptima se completará en pasos O (log n) ; sin embargo, la complejidad general del tiempo de ejecución dependerá de la complejidad del algoritmo de multiplicación utilizado. Usando Karatsuba Multiplication , por ejemplo, la complejidad general del tiempo de ejecución sería O (n log 2 3 ) ≈ O (n 1.585 ) . 1

Sin embargo, la exponenciación de la matriz no es necesariamente la mejor manera de hacerlo. Como notó un desarrollador en nayuki.io/page/fast-fibonacci-algorithms , la exponenciación de la matriz conlleva cálculos redundantes, que pueden eliminarse. De la descripción del autor:

Dados F k y F k + 1 , podemos calcular estos:


Tenga en cuenta que esto requiere solo 3 multiplicaciones de BigInt a BigInt por división, en lugar de 8 como lo haría la exponenciación de la matriz.

Sin embargo, aún podemos hacerlo un poco mejor que esto. Una de las identidades de Fibonacci más elegantes está relacionada con los números de Lucas:

donde L n es el n ° Lucas Number . Esta identidad se puede generalizar aún más como:

Hay algunas formas más o menos equivalentes de proceder recursivamente, pero la más lógica parece estar en F n y L n . Otras identidades utilizadas en la implementación a continuación pueden ser encontradas o derivadas de las identidades listadas para Lucas Sequences :

Proceder de esta manera requiere solo dos multiplicaciones de BigInt a BigInt por división, y solo una para el resultado final. Esto es aproximadamente un 20% más rápido que el código proporcionado por Project Nayuki ( script de prueba ). Nota: la fuente original ha sido modificada (mejorada) ligeramente para permitir una comparación justa.

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

Actualizar

Una barba gris señala , el resultado anterior ya ha sido mejorado por Takahashi (2000) 2 , al señalar que la cuadratura de BigInt es generalmente (y específicamente para el algoritmo de Schönhage-Strassen) menos costosa computacionalmente que la multiplicación BigInt. El autor sugiere una iteración, dividiendo en F n y L n , usando las siguientes identidades:

Para iterar de esta forma, se necesitarán dos cuadrados BigInt por división, en lugar de un cuadrado BigInt y una multiplicación BigInt como se indicó anteriormente. Como se esperaba, el tiempo de ejecución es considerablemente más rápido que la implementación anterior para n muy grande, pero es algo más lento para valores pequeños ( n <25000 ).

Sin embargo, esto también se puede mejorar ligeramente. El autor afirma que "se sabe que el algoritmo Producto de Lucas Numbers utiliza la menor cantidad de operaciones de bits para calcular el número de Fibonacci F n ". El autor elige adaptar el algoritmo Producto de Lucas Números, que en ese momento era el más conocido, dividiendo en F n y L n . Sin embargo, tenga en cuenta que L n solo se usa en el cálculo de F n + 1 . Esto parece un tanto derrochador si se tienen en cuenta las siguientes identidades:

donde el primero se toma directamente de Takahashi, el segundo es el resultado del método de exponenciación de la matriz (también notado por Nayuki), y el tercero es el resultado de agregar los dos anteriores. Esto permite una división obvia en F n y F n + 1 . El resultado requiere una adición BigInt menos, y, lo que es más importante, una división menos por 2 para incluso n ; para impar n el beneficio se duplica. En la práctica, esto es significativamente más rápido que el método propuesto por Takahashi para n pequeño (10-15% más rápido) y marginalmente más rápido para n muy grande ( script de prueba ).

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 Se puede ver que la cantidad de dígitos (o bits) de F n ~ O (n) como:

La complejidad del tiempo de ejecución usando Karatsuba Multiplication se puede calcular como:

2 Takahashi, D. (2000), "Un algoritmo rápido para calcular grandes números de Fibonacci" (PDF), Information Processing Letters 75 , págs. 243-246.

He escrito un pequeño código para calcular Fibonacci para un número grande que es más rápido que la forma de recursión conversacional.

Estoy usando la técnica de memorización para obtener el último número de Fibonacci en lugar de volver a calcularlo.

public class FabSeries { private static Map<BigInteger, BigInteger> 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)); } }

Ingresar número

40

Estadísticas con la técnica de memorización

Valor de Fibonacci: 102334155

Tiempo tomado: 5

Mapa de memoria: {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}

Estadísticas sin técnica de memorización

Valor de Fibonacci: 102334155

Tiempo tomado: 11558

He hecho un programa. No tarda mucho en calcular los valores, pero el plazo máximo que se puede mostrar es el 1477º (debido al rango máximo para el doble). Los resultados aparecen casi al instante. La serie comienza desde 0. Si necesita alguna mejora, siéntase libre de editarla.

#include<iostream> 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<<x<<" "; } x=x+y; } else { if(i==n) { cout<<x<<" "; } y=x+y; } } } main() { long int n=0; cout<<"The number of terms "; cin>>n; fibseries(n); return 0; }

La mayoría de las personas ya le dieron un enlace que explica el hallazgo del número N de Fibonacci, por cierto el algoritmo de Power funciona igual con cambios menores.

De todos modos esta es mi solución 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)); } }

Para calcular elementos arbitrariamente grandes de la secuencia de Fibonacci, tendrá que usar la solución de forma cerrada, la fórmula de Binet, y usar la matemática de precisión arbitraria para proporcionar la precisión suficiente para calcular la respuesta.

Sin embargo, el simple hecho de utilizar la relación de recurrencia no debería requerir de 2 a 3 minutos para calcular el 50º término. Debería poder calcular los términos en miles de millones en cualquier máquina moderna. Parece que está utilizando la fórmula totalmente recursiva, que conduce a una explosión combinatoria de cálculos recursivos. La fórmula iterativa simple es mucho más rápida.

A saber: la solución recursiva es:

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

... y sentarse y ver el desbordamiento de la pila.

La solución iterativa es:

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; }

Observe que básicamente estamos calculando el siguiente término n_new de los términos anteriores n_1 y n_2 , y luego " n_2 " todos los términos para la próxima iteración. Con un tiempo de ejecución lineal sobre el valor de n , es cuestión de unos pocos segundos para n en los miles de millones (bien después del desbordamiento del entero para sus variables intermedias) en una máquina de gigahercios moderna.

Para calcular los números de Fibonacci, el algoritmo recursivo es uno de los peores. Simplemente agregando los dos números anteriores en un ciclo for (llamado método iterativo) no tomará 2-3 minutos, para calcular el 50º elemento.

Puede ahorrar mucho tiempo mediante el uso de la memoization . Por ejemplo, compare las siguientes dos versiones (en JavaScript):

Versión 1 : recursión normal

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

Versión 2 : memorización

A. tomar el uso de la biblioteca de underscore

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

B. Libre de biblioteca

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); }; })();

La primera versión toma más de 3 minutos para n = 50 (en Chrome), mientras que la segunda solo toma menos de 5 ms. Puede verificar esto en jsFiddle .

No es sorprendente si sabemos que la complejidad del tiempo de la versión 1 es exponencial ( O (2 N / 2 )), mientras que la versión 2 es lineal ( O ( N )).

Versión 3 : multiplicación de matrices

Además, incluso podemos reducir la complejidad de tiempo a O (log ( N )) calculando la multiplicación de N matrices.

donde F n denota el enésimo término de la secuencia de Fibonacci.

Puede usar el método de exponenciación de la matriz (método de recurrencia lineal). Puedes encontrar explicaciones y procedimientos detallados en this blog. El tiempo de ejecución es O (log n ).

No creo que haya una mejor manera de hacer esto.

Resolví un problema de UVA: 495 - Congelación de Fibonacci

Genera todos los números de Fibonacci hasta 5000th e imprime salidas para entradas dadas (rango 1 - 5000).

Se acepta con tiempo de ejecución de 00.00 segundos.

El número de Fibonacci para 5000 es:

3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

#include<stdio.h> #include<string.h> #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<minLen; k++, i--, j--) { int val = (str1[i] - ''0'') + (str2[j] - ''0'') + carry; result[k] = (val % 10) + ''0''; carry = val / 10; } while (k < len1) { int val = str1[i] - ''0'' + carry; result[k] = (val % 10) + ''0''; carry = val / 10; k++; i--; } while (k < len2) { int val = str2[j] - ''0'' + carry; result[k] = (val % 10) + ''0''; carry = val / 10; k++; j--; } if (carry > 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; }

Si está usando C # eche un vistazo a Lync y BigInteger. Intenté esto con 1000000 (en realidad 1000001 cuando omito los primeros 1000000) y estaba por debajo de 2 minutos (00: 01: 19.5765).

public static IEnumerable<BigInteger> 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(); }

Tengo un código fuente en c para calcular incluso el número 3500th de Fibonacci: para más información, visite

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

código fuente en C: -

#include<stdio.h> #include<conio.h> #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;i<max;i++) arr1[i]=arr2[i]=arr3[i]=0; arr2[max-1]=1; printf("ENTER THE TERM : "); scanf("%d",&num); for(i=0;i<num;i++) { fun(); if(i==num-3) break; for(j=0;j<max;j++) arr1[j]=arr2[j]; for(j=0;j<max;j++) arr2[j]=arr3[j]; } for(i=0;i<max;i++) { if(tag||arr3[i]) { tag=1; printf("%d",arr3[i]); } } getch(); return 1; } void fun(void) { int i,temp; for(i=0;i<max;i++) arr3[i]=arr1[i]+arr2[i]; for(i=max-1;i>0;i--) { if(arr3[i]>9) { temp=arr3[i]; arr3[i]%=10; arr3[i-1]+=(temp/10); } } }

Una solución más elegante en 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

Use las identidades de recurrencia http://en.wikipedia.org/wiki/Fibonacci_number#Other_identities para encontrar el n -ésimo número en los pasos de log(n) . Deberá usar enteros de precisión arbitrarios para eso. O puede calcular el módulo de respuesta precisa algún factor mediante el uso de aritmética modular en cada paso.

Al 3n+3 == 3(n+1) cuenta de que 3n+3 == 3(n+1) , podemos diseñar una función recursiva única que calcula dos números secuenciales de Fibonacci en cada paso dividiendo la n entre 3 y eligiendo la fórmula adecuada de acuerdo con el valor restante. IOW calcula un par @(3n+r,3n+r+1), r=0,1,2 desde un par @(n,n+1) en un solo paso, por lo que no hay recursión doble y no es necesario memorizar .

Un código Haskell está here .

update:

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

parece conducir a un código más rápido. El uso de "identidades de secuencia de Lucas" podría ser el más rápido ( esto se debe al usuario: primo , que cita esta implementación ).

aquí hay un código de python corto, funciona bien hasta 7 dígitos. Solo requiere una matriz de 3 elementos

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]

The Simplest Pythonic Implementation can be given as follows

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

This JavaScript implementation handles nthFibonacci(1200) no problemo:

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

With some knowledge of discrete mathematics, you can find any Fibonacci number in constant time 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

We know that

dónde

Then, the Characteristic equation is

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

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).

#include <bits/stdc++.h> #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; }

Complejidad del tiempo: O (Log n) a medida que dividimos el problema a la mitad en cada llamada recursiva.