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

sucesion de fibonacci ejercicios

Question

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?

Answer 1

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]

Answer 2

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)

Answer 3

En primer lugar, puede formarse una idea del término más alto del término Fibonacci conocido más grande . también vemos pasar a través de la presentación recursiva de la función de Fibonacci . Un acercamiento interesado sobre este tema está en este artículo . Además, intenta leer sobre él en el peor algoritmo del mundo? .

Answer 4

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.

Answer 5

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 ₂ 3} ) ≈ O (n ^1.585 ) . ¹

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

¹ 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:

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

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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.

Answer 10

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.

Answer 11

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.

Answer 12

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.

Answer 13

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

Answer 14

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

Answer 15

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

Answer 16

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

Answer 17

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

Answer 18

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]

Answer 19

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

Answer 20

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

Answer 21

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

Answer 22

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