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

Question 1

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 el ú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 long para tratar de asegurarse de que haya suficientes bits para almacenar el número.

Esta es la salida de la primera 100 nú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 probado a imprimir el primer millón porque si falla al imprimir F(100) no hay muchas esperanzas de que se imprima F(1,000,000).

Question 2

Por Fórmula de Binet el enésimo número de Fibonacci es aproximadamente la proporción áurea (aproximadamente 1,618) elevado a la potencia n y luego dividido por la raíz cuadrada de 5. Un simple uso de logaritmos muestra que el millonésimo número de Fibonacci tiene más de 200.000 dígitos. La longitud media de uno de los primeros millones de números de Fibonacci es, por tanto, superior a 100.000 = 10^5. Por lo tanto, está tratando de imprimir 10 ^ 11 = 100 mil millones de dígitos. Creo que necesitará más que una gran biblioteca int para hacer eso.

Por otro lado, si desea simplemente calcular el número millonésimo, puede hacerlo, aunque sería mejor usar un método que no calcule todos los números intermedios (simplemente calculando en lugar de imprimirlos todos). todavía sería inviable para n lo suficientemente grande). Es bien sabido (ver este) que el n-ésimo número de Fibonacci es una de las 4 entradas de la n-ésima potencia de la matriz [[1,1],[1,0]]. Si utiliza exponenciación al cuadrado (que también funciona para potencias de matrices, ya que la multiplicación de matrices es asociativa) junto con una buena biblioteca de int grande: se vuelve perfectamente factible calcular el millonésimo número de Fibonacci.

[On Further Edit]: Aquí hay un programa de Python para calcular números de Fibonacci muy grandes, modificado para aceptar ahora un módulo opcional. Debajo del capó está usando una buena biblioteca C bignum.

def mmult(A,B,m = False):
    #assumes A,B are 2x2 matrices
    #m is an optional modulus
    a = A[0][0]*B[0][0] + A[0][1]*B[1][0]
    b = A[0][0]*B[0][1] + A[0][1]*B[1][1]
    c = A[1][0]*B[0][0] + A[1][1]*B[1][0]
    d = A[1][0]*B[0][1] + A[1][1]*B[1][1]
    if m:
        return [[a%m,b%m],[c%m,d%m]]
    else:
        return [[a,b],[c,d]] 

def mpow(A,n,m = False):
    #assumes A is 2x2
    if n == 0:
        return [[1,0],[0,1]]
    elif n == 1: return [row[:] for row in A] #copy A
    else:
        d,r = divmod(n,2)
        B = mpow(A,d,m)
        B = mmult(B,B,m)
        if r > 0:
            B = mmult(B,A,m)
        return B

def Fib(n,m = False):
    Q = [[1,1],[1,0]]
    return mpow(Q,n,m)[0][1]

n = Fib(999999)
print(len(str(n)))
print(n % 10**10)
googol = 10**100
print(Fib(googol, googol))

Salida (con espacios en blanco agregados):

208988

6684390626

3239047153240982923932796604356740872797698500591032259930505954326207529447856359183788299560546875

Tenga en cuenta que lo que llama el millonésimo número de Fibonacci, yo lo llamo el 999,999, ya que es más estándar comenzar con 1 como el primer número de Fibonacci (y llamar 0 el 0 si desea contarlo como un número de Fibonacci). El primer número de salida confirma que hay más de 200.000 dígitos en el número y el segundo da los últimos 10 dígitos (que ya no es un misterio). El número final son los últimos 100 dígitos del número googolth de Fibonacci, calculado en una pequeña fracción de segundo. Todavía no he podido hacer un googolplex 🙂

Question 3

Su algoritmo es realmente correcto. Ya que estás usando unsigned long longtiene suficientes dígitos para capturar los últimos 10 dígitos y la naturaleza de las funciones de desbordamiento sin signo como aritmética de módulo, por lo que obtendrá los resultados correctos para al menos los últimos 10 dígitos.

El problema está en el especificador de formato que está utilizando para la salida:

printf("%d\n",next);

Él %d especificador de formato espera un intpero estás pasando un unsigned long long. Usar el especificador de formato incorrecto invoca comportamiento indefinido.

Lo más probable que suceda en este caso particular es que printf está recogiendo los 4 bytes de orden bajo de next (ya que su sistema parece ser little endian) e interpretarlos como un signo int. Esto termina mostrando los valores correctos para aproximadamente los primeros 60 números, pero los incorrectos después de eso.

Utilice el especificador de formato correcto y obtendrá los resultados correctos:

printf("%llu\n",next);

También debe hacer lo mismo al leer/imprimir n:

scanf("%llu",&n);

printf("First %llu terms of Fibonacci series are :-\n",n);

Aquí está la salida de los números 45-60:

701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025
20365011074
32951280099
53316291173
86267571272
139583862445
225851433717
365435296162
591286729879
956722026041

Question 4

Para “obtener los últimos 10 dígitos de F(1,000,000)”, simplemente aplique la función de resto % al calcular next y use el especificador de formato correcto: "%llu".

No es necesario sumar dígitos más significativos que los 10 dígitos menos significativos.

  // scanf("%d",&n);
  scanf("%llu",&n);
  ...
  {
     // next = first + second;
     next = (first + second) % 10000000000;
     first = second;
     second = next;
  }
  // printf("%d\n",next);
  printf("%010llu\n",next);

Mi salida (ha hecho una cruz en los últimos 5 dígitos para no revelar la respuesta final)

 66843xxxxx

Question 5

Puede imprimir Fibonacci (1,000,000) en C, toma alrededor de 50 líneas, un minuto y sin biblioteca:

Algunos encabezados son requeridos :

#include <stdio.h>
#include <stdlib.h>

#define BUFFER_SIZE (16 * 3 * 263)
#define BUFFERED_BASE (1LL << 55)

struct buffer {
    size_t index;
    long long int data[BUFFER_SIZE];
};

Algunos funciones también :

void init_buffer(struct buffer * buffer, long long int n){
    buffer->index = BUFFER_SIZE ;
    for(;n; buffer->data[--buffer->index] = n % BUFFERED_BASE, n /= BUFFERED_BASE);
}

void fly_add_buffer(struct buffer *buffer, const struct buffer *client) {
    long long int a = 0;
    size_t i = (BUFFER_SIZE - 1);
    for (; i >= client->index; --i)
        (a = (buffer->data[i] = (buffer->data[i] + client->data[i] + a)) > (BUFFERED_BASE - 1)) && (buffer->data[i] -= BUFFERED_BASE);
    for (; a; buffer->data[i] = (buffer->data[i] + a), (a = buffer->data[i] > (BUFFERED_BASE - 1)) ? buffer->data[i] -= BUFFERED_BASE : 0, --i);
    if (++i < buffer->index) buffer->index = i;
}

UN convertidor base se utiliza para formatear la salida en base 10:

#include "string.h"

// you must free the returned string after usage
static char *to_string_buffer(const struct buffer * buffer, const int base_out) {
    static const char *alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    size_t a, b, c = 1, d;
    char *s = malloc(c + 1);
    strcpy(s, "0");
    for (size_t i = buffer->index; i < BUFFER_SIZE; ++i) {
        for (a = buffer->data[i], b = c; b;) {
            d = ((char *) memchr(alphabet, s[--b], base_out) - alphabet) * BUFFERED_BASE + a;
            s[b] = alphabet[d % base_out];
            a = d / base_out;
        }
        while (a) {
            s = realloc(s, ++c + 1);
            memmove(s + 1, s, c);
            *s = alphabet[a % base_out];
            a /= base_out;
        }
    }
    return s;
}

Ejemplo de uso:

#include <sys/time.h>

double microtime() {
    struct timeval time;
    gettimeofday(&time, 0);
    return (double) time.tv_sec + (double) time.tv_usec / 1e6;
}

int main(void){
    double a = microtime();
    // memory for the 3 numbers is allocated on the stack.
    struct buffer number_1 = {0}, number_2 = {0}, number_3 = {0};
    init_buffer(&number_1, 0);
    init_buffer(&number_2, 1);
    for (int i = 0; i < 1000000; ++i) {
        number_3 = number_1;
        fly_add_buffer(&number_1, &number_2);
        number_2 = number_3;
    }
    char * str = to_string_buffer(&number_1, 10); // output in base 10
    puts(str);
    free(str);
    printf("took %gs\n", microtime() - a);
}

Salida de ejemplo:

The 1000000th Fibonacci number is :
19532821287077577316320149475 ... 03368468430171989341156899652
took 30s including 15s of base 2^55 to base 10 conversion.

También está usando un convertidor base agradable pero lento.

Gracias.

¿Ha sido útil esta solución?