C imprime el primer millón de números de Fibonacci

Estoy tratando de escribir un código C que imprimirá los primeros 1 millón de números de Fibonacci.

El problema real es que quiero obtener los últimos 10 dígitos de F(1,000,000)

Entiendo cómo funciona la secuencia y cómo escribir el código para lograrlo, sin embargo, como F(1,000,000)es muy grande, estoy luchando por encontrar una manera de representarlo.

Este es el código que estoy usando:

#include<stdio.h>
 
int main()
{
 unsigned long long n, first = 0, second = 1, next, c;
 
 printf("Enter the number of terms\n");
 scanf("%d",&n);
 
 printf("First %d terms of Fibonacci series are:-\n",n);
 
 for ( c = 0; c < n; c++ )
 {
 if ( c <= 1 )
 next = c;
 else
 {
 next = first + second;
 first = second;
 second = next;
 }
 printf("%d\n",next);
 }
 
 return 0;
}

Estoy usando long longpara tratar de asegurarme de que haya suficientes bits para almacenar el número.

Esta es la salida para los primeros 100números:

First 100 terms of Fibonacci series are:-         
 0           
 1           
 1           
 2           
 3           
 5           
 8           
 13           
 21           
 34           
 55           
 89           
 144           
 233           
 377           
 610           
 987           
 1597           
 2584           
 4181           
 6765           
 10946           
 17711           
 28657           
 46368           
 75025           
 121393           
 196418           
 317811           
 514229           
 832040           
 1346269           
 2178309           
 3524578           
 5702887           
 9227465           
 14930352           
 24157817           
 39088169           
 63245986
 102334155           
 165580141           
 267914296           
 433494437           
 701408733           
 1134903170           
 1836311903           
 -1323752223           
 512559680           
 -811192543           
 -298632863           
 -1109825406           
 -1408458269
...

Truncó la salida pero puede ver el problema, creo que el tamaño del número generado está causando que el valor se desborde a negativo. No entiendo cómo detenerlo con toda honestidad.

¿Alguien puede indicarme la dirección correcta sobre cómo manejar números de este tamaño?

No he intentado imprimir el primer millón porque si falla en la impresión F(100), no hay muchas esperanzas de que se imprima F(1,000,000).

Solución del problema

Quiere los últimos 10 dígitos de Fib(1000000). Lea mucho más sobre los números de Fibonacci (y lea dos veces ).

Sin pensarlo mucho, podría usar alguna biblioteca bignum como GMPlib. Haría un bucle para calcular Fib (1000000) usando algunas mpz_t variables bigint (ciertamente no necesita una matriz de un millón mpz_t, pero menos mpz_tvariables de las que tiene los dedos en la mano). Por supuesto, no imprimirá todos los números de Fibonacci, solo el último número 1000000 ( por lo que una computadora portátil barata hoy en día tiene suficiente memoria y arrojaría ese número en menos de una hora). Como respondió John Coleman, tiene alrededor de 200K dígitos (es decir, 2500 líneas de 80 dígitos cada una).

(Por cierto, cuando piense en un programa que produce un gran resultado, será mejor que adivine-estime el tamaño típico de ese resultado y el tiempo típico para obtenerlo; si no cabe en su sala de escritorio -o en su computadora de escritorio-, tienes un problema, quizás económico: necesitas comprar más recursos informáticos)

Tenga en cuenta que la aritmética bignum eficiente es un tema difícil. Existen algoritmos inteligentes para la aritmética bignum que son mucho más eficientes que el ingenuo que te imaginas.

En realidad, no necesitas ningún bigints. Lea algún libro de texto de matemáticas sobre aritmética modular. El módulo de una suma (o un producto) es congruente con la suma (resp. el producto) del módulo. Usa esa propiedad. Un entero de 10 dígitos cabe en 64 bits int64_t, por lo que, pensando un poco, no necesita ninguna biblioteca bignum.

(Supongo que con un poco más de pensamiento, no necesita ninguna computadora ni ningún programa C para calcular eso. Una calculadora barata, un lápiz y un papel deberían ser suficientes, y probablemente la calculadora no sea necesaria en absoluto).

La lección a aprender al programar (o al resolver ejercicios de matemáticas) es pensar en el problema y tratar de reformular la pregunta antes de comenzar a codificar. J.Pitrat (un pionero de la Inteligencia Artificial en Francia, ahora jubilado, pero todavía trabajando en su computadora) tiene varias entradas de blog interesantes relacionadas con eso: ¿Es posible definir un problema?, cuando Donald y Gerald conocen a Robert, etc.

Comprender y pensar en el problema (¡y también en los subproblemas!) es una parte interesante del desarrollo de software. Si trabaja en el desarrollo de software, primero se le pedirá que resuelva problemas del mundo real (por ejemplo, crear un sitio web de venta o una aspiradora autónoma) y deberá pensar en transformar ese problema en algo que sea codificable en un ordenador. Ten paciencia, necesitarás diez años para aprender a programar.