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

回答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 1000000^th 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.

回答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

回答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 :)

回答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.

回答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