'C print first million Fibonacci numbers
I am trying to write C code which will print the first 1million Fibonacci numbers.
The actual problem is I want to get the last 10 digits of F(1,000,000)
I understand how the sequence works and how to write the code to achieve that however as F(1,000,000) is very large I am struggling to find a way to represent it.
This is code I am using:
#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;
}
I am using long long to try and make sure there are enough bits to store the number.
This is the output for the first 100 numbers:
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
...
Truncated the output but you can see the problem, I believe the size of the number generated is causing the value to overflow to negative. I don't understand how to stop it in all honesty.
Can anybody point me in the right direction to how to actually handle numbers of this size?
I haven't tried to print the first million because if it fails on printing F(100) there isn't much hope of it printing F(1,000,000).
Solution 1:[1]
You want the last 10 digits of Fib(1000000). Read much more about Fibonacci numbers (and read twice).
Without thinking much, you could use some bignum library like GMPlib. You would loop to compute Fib(1000000) using a few mpz_t bigint variables (you certainly don't need an array of a million mpz_t, but less mpz_t variables than you have fingers in your hand). Of course, you won't print all the fibonacci numbers, only the last 1000000th one (so a cheap laptop today has enough memory, and would spit that number in less than an hour). As John Coleman answered it has about 200K digits (i.e. 2500 lines of 80 digits each).
(BTW, when thinking of a program producing some big output, you'll better guess-estimate the typical size of that output and the typical time to get it; if it does not fit in your desktop room -or your desktop computer-, you have a problem, perhaps an economical one: you need to buy more computing resources)
Notice that efficient bignum arithmetic is a hard subject. Clever algorithms exist for bignum arithmetic which are much more efficient than the naive one you would imagine.
Actually, you don't need any bigints. Read some math textbook about modular arithmetic. The modulus of a sum (or a product) is congruent to the sum (resp. the product) of the modulus. Use that property. A 10 digits integer fits in a 64 bits int64_t so with some thinking you don't need any bignum library.
(I guess that with slightly more thinking, you don't need any computer or any C program to compute that. A cheap calculator, a pencil and a paper should be enough, and probably the calculator is not needed at all.)
The lesson to learn when programming (or when solving math exercises) is to think about the problem and try to reformulate the question before starting coding. J.Pitrat (an Artificial Intelligence pioneer in France, now retired, but still working on his computer) has several interesting blog entries related to that: Is it possible to define a problem?, When Donald and Gerald meet Robert, etc.
Understanding and thinking about the problem (and sub-problems too!) is an interesting part of software development. If you work on software developement, you'll be first asked to solve real-world problems (e.g. make a selling website, or an autonomous vacuum cleaner) and you'll need to think to transform that problem into something which is codable on a computer. Be patient, you'll need ten years to learn programming.
Solution 2:[2]
To "get the last 10 digits of F(1,000,000)", simply apply the remainder function % when calculating next and use the correct format specifier: "%llu".
There is no need to sum digits more significant than the 10 least significant digits.
// 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);
My output (x'ed the last 5 digits to not give-away the final answer)
66843xxxxx
Solution 3:[3]
By Binet's Formula the nth Fibonacci Number is approximately the golden ratio (roughly 1.618) raised to the power n and then divided by the square root of 5. A simple use of logarithms shows that the millionth Fibonacci number thus has over 200,000 digits. The average length of one of the first million Fibonacci numbers is thus over 100,000 = 10^5. You are thus trying to print 10^11 = 100 billion digits. I think that you will need more than a big int library to do that.
On the other hand -- if you want to simply compute the millionth number, you can do so -- though it would be better to use a method which doesn't compute all of the intermediate numbers (as simply computing rather than printing them all would still be infeasible for large enough n). It is well known (see this) that the nth Fibonacci number is one of the 4 entries of the nth power of the matrix [[1,1],[1,0]]. If you use exponentiation by squaring (which works for matrix powers as well since matrix multiplication is associative) together with a good big int library -- it becomes perfectly feasible to compute the millionth Fibonacci number.
[On Further Edit]: Here is a Python program to compute very large Fibonacci numbers, modified to now accept an optional modulus. Under the hood it is using a good C bignum library.
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))
Output (with added whitespace):
208988
6684390626
3239047153240982923932796604356740872797698500591032259930505954326207529447856359183788299560546875
Note that what you call the millionth Fibonacci number, I call the 999,999th -- since it is more standard to start with 1 as the first Fibonacci number (and call 0 the 0th if you want to count it as a Fibonacci number). The first output number confirms that there are over 200,000 digits in the number and the second gives the last 10 digits (which is no longer a mystery). The final number is the last 100 digits of the googolth Fibonacci number -- computed in a small fraction of a second. I haven't been able to do a googolplex yet :)
Solution 4:[4]
This question comes without doubt from some programming competition, and you have to read these questions carefully.
The 1 millionth Fibonacci number is HUGE. Probably about 200,000 digits or so. Printing the first 1,000,000 Fibonacci number will kill a whole forest of trees. But read carefully: Nobody asks you for the 1 millionth Fibonacci number. You are asked for the last ten digits of that number.
So if you have the last 10 digits of Fib(n-2) and of Fib(n-1), how can you find the last 10 digits of Fib(n)? How do you calculate the last ten digits of a Fibonacci number without calculating the number itself?
PS. You can't print long long numbers with %d. Use %lld.
Solution 5:[5]
Your algorithm is actually correct. Since you're using unsigned long long, you have enough digits to capture the last 10 digits and the nature of unsigned overflow functions as modulo arithmetic, so you'll get the correct results for at least the last 10 digits.
The problem is in the format specifier you're using for the output:
printf("%d\n",next);
The %d format specifier expects an int, but you're passing an unsigned long long. Using the wrong format specifier invokes undefined behavior.
What's most likely happening in this particular case is that printf is picking up the low-order 4 bytes of next (as your system seems to be little endian) and interpreting them as a signed int. This ends up displaying the correct values for roughly the first 60 numbers or so, but incorrect ones after that.
Use the correct format specifier, and you'll get the correct results:
printf("%llu\n",next);
You also need to do the same when reading / printing n:
scanf("%llu",&n);
printf("First %llu terms of Fibonacci series are :-\n",n);
Here's the output of numbers 45-60:
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025
20365011074
32951280099
53316291173
86267571272
139583862445
225851433717
365435296162
591286729879
956722026041
Solution 6:[6]
You can print Fibonacci(1,000,000) in C, it takes about 50 lines, a minute and no library :
Some headers are required :
#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];
};
Some functions too :
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;
}
A base converter is used to format the output in 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;
}
Example usage :
#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);
}
Example output :
The 1000000th Fibonacci number is :
19532821287077577316320149475 ... 03368468430171989341156899652
took 30s including 15s of base 2^55 to base 10 conversion.
Also it's using a nice but slow base converter.
Thank You.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Unihedron |
| Solution 2 | |
| Solution 3 | |
| Solution 4 | |
| Solution 5 | dbush |
| Solution 6 |