1,000,000th Fibonacci Number One-Liner in C

This is possibly the best one-liner I’ve ever written:

gcc -x c -o /tmp/out - -lgmp <<< '#include <stdlib.h> 
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <gmp.h>
void omg_i_love_leonardo_of_pisa(uint32_t num, mpz_t * result) { mpz_t retval, last, tmp; mpz_init(retval);
 mpz_init(last); mpz_init(tmp); uint32_t i = 1; if(num == 0) return; mpz_set_ui(retval, 1U); 
mpz_set_ui(last, 0U); for(; i < num; i++) { mpz_set(tmp, retval); mpz_add(retval, retval, last); 
mpz_set(last, tmp); } mpz_set(*result, retval); } int main() { uint32_t num; mpz_t fibo; mpz_init(fibo);
omg_i_love_leonardo_of_pisa(1000001, &fibo); mpz_out_str(stdout, 10, fibo); printf("\n"); return 1; }
' && time /tmp/out

It compiles a C program given from STDIN, puts it in /tmp/out, and runs it with time to find the time it takes to run. It generates the 1,000,000th Fibonacci number. Try it!

Update May 21, 2011

I changed the algorithm to do a matrix multiplication trick. The only problem is it goes over the number you ask for currently. I'm going to fix this with memoization soon.

gcc -x c -o /tmp/out - -lgmp <<< '#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#include <gmp.h>
void print_state(mpz_t* fm2, mpz_t* fm1, mpz_t* f, uint32_t n){gmp_printf("fib(%d) = %Zd\n", n, f);}
#define NEXT_FIB() mpz_set(oldfm1, fm1);mpz_set(oldf, f);mpz_mul(f, f, f);mpz_mul(tmp, fm1, fm1);\
mpz_add(f, f, tmp);mpz_mul(fm1, oldf, fm1);mpz_mul(tmp, oldfm1, fm2);mpz_add(fm1, fm1, tmp); \
mpz_set(tmp, fm2);mpz_mul(fm2, oldfm1, oldfm1);mpz_mul(tmp, tmp, tmp);mpz_add(fm2, fm2, tmp);\
n += i;i *= 2;
int main(){mpz_t fm2, fm1, f;uint32_t n = 2;uint32_t i = 1;mpz_inits(fm2, fm1, f, NULL);mpz_set_si(fm2,
0);mpz_set_si(fm1, 1);mpz_set_si(f, 1);mpz_t oldf, oldfm1, tmp;mpz_inits(oldf, oldfm1, tmp, NULL);
uint32_t g = 1000000;while(n<g){NEXT_FIB();}print_state(&fm2, &fm1, &f, n);return 0;}' && time /tmp/out

This outputs almost immediately on my Intel Atom:


fib(1048577) = 19202837189514814.................

real	0m0.840s
user	0m0.280s
sys	0m0.010s

The code is here. Feel free to fork and improve!

Update August 30, 2013

I ended up looking at this again, and I improved it immensely. Apparently, gmp has built-in fibo functions (!!):

#include 
#include 
#include 
#include 
int main()
{
  int n = 1000000;
  mpz_t fm2;
  mpz_inits(fm2, NULL);
  mpz_fib_ui(fm2, n);
  gmp_printf("fib(%d) = %Zd\n", n, fm2);
  return 1;
}

This produces a number MUCH faster than the above implementation. It also makes a nicer oneliner:

gcc -x c -o /tmp/out - -lgmp <<< '#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#include <gmp.h>
int main() { int n = 1000000; mpz_t fm2; mpz_inits(fm2, NULL); mpz_fib_ui(fm2, n); gmp_printf(\"fib(%d) = %Zd\n\", n, fm2); return 1; }" && time /tmp/out

real    0m0.057s
user    0m0.040s
sys     0m0.008s


7 thoughts on “1,000,000th Fibonacci Number One-Liner in C

  1. Robert Ottignon

    Python code for generating 1000,000th number in the Fibonacci sequence (or any number, the attribute of c):

    # Fibonacci in Python 3.0
    i=0
    c=1000000
    # Sets number you want program to stop at.
    x=0
    y=1
    while i< =c:
    	print ("  ")
    	print ("  ")
    	print ("Fibonacci number ",i," = ",x)
    	y=y+x
    	i=i+1
    	if i<=c:
    		print ("  ")
    		print ("  ")
    		print ("Fibonacci number ",i," = ",y)
    		x=x+y
    		i=i+1
    	else:
    		break
    
  2. Erik Post author

    Robert:

    Thanks for the comment. That isn’t a bad way to generate the number, and if I slightly modify it, it does:

    
    # Fibonacci in Python 3.0
    i=0
    c=1000000
    # Sets number you want program to stop at.
    x=0
    y=1
    while i<=c:
      y=y+x
      i=i+1
      if i<=c:
        x=x+y
        i=i+1
      else:
        break
    
    print ("  ")
    print ("  ")
    print ("Fibonacci number ",i," = ",y)
    

    Yet, it takes over 3 times as long as my example

    Your script: 0m59.591s
    My program: 0m17.435s

  3. Ekharion

    Prolog:

    %fib(IN,OUT,P).
    fib(0,0,0).
    fib(1,1,0).
    fib(IN,OUT,P) :- IN2 is IN -1, fib(IN2,P,P2), OUT is P + P2.

    :mrgreen: :wink:

  4. Erik Post author

    Yeah, you can do that. I recently found a huge optimization and I need to update the code here. Cheers.

  5. Reuben Willson

    def fib(n):
    a,b=1,0
    for x in range(n):
    a,b=a+b,a
    # the following comments make it easy to track where it’s at
    #r,t = divmod(x+1,10)
    #if t==0:
    #print(x+1,a)
    return(a)

Leave a Reply

Your email address will not be published. Required fields are marked *