Chris Edwards
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).
Juan Coleman
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 🙂
-
Probablemente sea mejor no declarar una matriz de pila, entonces … 🙂
– Martín James
16 de noviembre de 2015 a las 11:06
-
@BasileStarynkevitch correcto, solo me importan los últimos 10 dígitos de
F(1,000,000)– Chris Edwards
16 de noviembre de 2015 a las 11:20
-
@ChrisEdwards: entonces podría hacer algo de matemáticas (módulo de cálculo 10 ^ 10) primero, pero debería haberlo dicho en su pregunta, que se convierte en muy diferente: ‘¿cómo calcular los últimos 10 dígitos de F(1000000)?’
– Basile Starynkevitch
16 de noviembre de 2015 a las 11:23
-
@chqrlie El enfoque iterativo simple funciona hasta cierto punto. Acabo de probarlo por 1.000.000 y tardó unos 8 segundos en mi máquina (a diferencia de menos de un segundo con el enfoque basado en matriz, que podría hacerse aún más eficiente). Por 10,000,000 mi acercamiento toma menos de 10 segundos. He tenido el enfoque iterativo funcionando durante más de 5 minutos ahora por 10,000,000 y es probable que elimine el proceso cuando termine con este comentario. Mi intuición era que chocaría contra la pared antes de un millón, pero tienes razón en que un millón en sí mismo no es irrazonable. Gracias por señalar eso.
– John Coleman
16 de noviembre de 2015 a las 21:19
-
En caso de duda, prueba la fuerza bruta… O mejor: primero prueba la fuerza bruta 😉
– chqrlie
16 de noviembre de 2015 a las 21:24
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
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
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.
consulte este tema: stackoverflow.com/questions/4827538/big-integer-in-c-or-c
– Mathieu Bordere
16 de noviembre de 2015 a las 10:52
¡Un largo tiempo no será suficiente!
– John Coleman
16 de noviembre de 2015 a las 10:52
UN
long longdebería ir por encima1836311903al menos– Zorgatone
16 de noviembre de 2015 a las 10:53
@BasileStarynkevitch Creo que estás siendo innecesariamente duro. Es posible que un estudiante principiante no tenga suficiente experiencia con la aritmética modular para darse cuenta de que todo el cálculo se puede realizar mod 10^10. Las cosas que son obvias para un programador no siempre lo son para un estudiante.
– John Coleman
16 de noviembre de 2015 a las 11:51
Utilizar el
%lldespecificador de formato en lugar de%d, pero eso solo lo llevará un poco más lejos. Pero de todos modos, las respuestas a continuación son bastante completas.– Jabberwocky
16 de noviembre de 2015 a las 14:25