Monthly Archives: September 2009

Importing MySQL 1.4 Amarok data into Amarok 2.2 Nightly

I was having a bunch of trouble today importing my old MySQL amarok database into the new nightly version of amarok I installed.  The Amarok Wiki had a great section on how to convert a MySQL Amarok collection into an SQLlite one.  This was the key to importing my old 1.4 collection into the new 2.2 nightly version of Amarok.

How to make Chrome bearable in Ubuntu Jaunty 9.04

So, there I was, watching Firefox 3 thrash my CPU and IO, when I decided that I needed a replacement.  Something elegant, fast, preferably threaded… oh!  Google Chrome!  So, I finally found a link to download the unstable version of the browser based on the latest revisions, of which I got version

Now, I’ve used Chrome in Linux before, and a few things about Firefox kept me hooked.  Today, though, I was on a mission to change all that.  I wanted basically all the functionality I got from Firefox in my Chrome experience as well.  This article should help others do the same.

Continue reading

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 (!!):

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