Use a Better Algorithm and Beat Haskell Today!

Posted on November 29, 2007
Filed Under Computer Science, Programming |

Note: This refers to the article “Use those extra cores and beat C today! (Parallel Haskell redux)”, and should be viewed as a good-natured ribbing!

I’ll see your sensational headline and raise you a better algorithm!

The Code:

#include "gmpxx.h"
#include <iostream>
#include <sys/time.h>
 
using namespace std;
 
mpz_class fib(unsigned int num)
{
  mpz_class a(1), b(1);
  mpz_class temp;
 
  while(num-- > 1)
  {
    temp = a;
    a = a + b;
    b = temp;
  }
  return a;
}
 
#define NUM 200000
 
int main()
{
  cout<<"Fibonacci test for Fib("<<NUM<<")"<<endl;
  timeval before, after;
  gettimeofday(&before, NULL);
 
  mpz_class a;
 
  a = fib(NUM);
 
  gettimeofday(&after, NULL);
 
  double duration = (after.tv_sec-before.tv_sec) 
    + (after.tv_usec - before.tv_usec) / 1000000.;
 
  cout<<"Time: "<<duration<<" seconds"<<endl;
 
  return 0;
}

Build With:

g++ fib.cpp -O2 -lgmp -lgmpxx

The Result: (On a Toshiba Laptop w/ Core 2 Duo @ 1.6GHz)

  Fibonacci test for Fib(200000)
  Time: 2.44233 seconds

That’s a lot better than what we can get in Haskell using the detailed multicore approach. 32 seconds to calculate fib(45)? Please!

The Lesson:

  1. There’s more than one way to get a speedup in your code, and you should carefully weigh your options when writing. This algorithm can be bettered if you have phi calculated to many digits, or if you use a better recurrence, so I’m not claiming “optimal” results here!
  2. Throwing more cores at a problem does not always solve it best
  3. I found out that writing sensational headlines is actually pretty fun.

Popularity: 19% [?]

Comments

5 Responses to “Use a Better Algorithm and Beat Haskell Today!”

  1. dons on November 29th, 2007 5:29 pm

    I’ll see your linear C++, and raise you some linear Haskell:

    main = print (fib 200000)

    fib :: Int -> Integer
    fib n = go n 1 1
    where
    go 1 a _ = a
    go n a b = go (n-1) (a + b) a

    On my machine, your code:

    $ g++ fib.cpp -O2 -lgmp -lgmpxx -o fib
    $ time ./fib
    Fibonacci test for Fib(200000)
    Time: 1.34055 seconds
    ./fib 1.32s user 0.02s system 98% cpu 1.360 total

    And the Haskell translation:

    $ ghc-6.8.1 -O2 -optc-O2 A.hs -o A
    $ time ./A
    2440914874035154859992549871532124086962886075690…
    …622248628614359062
    ./A 0.48s user 0.01s system 98% cpu 0.504 total

    Maybe you need more cores! (Or did I do something wrong?)

  2. Joel Parish on November 29th, 2007 6:06 pm

    The Parallel haskell post you referenced specifically stated that they were using the *naive* algorithm in order to test ease of parallelization rather than that specific algorithm. Binet’s Formula, the Matrix Multiplication method will yield faster results than iteration for larger n. If you want an apples to apples comparison to your iterative method consider:

    xor ax, ax
    push ax
    mov ax, 1
    push ax
    mov cx, 0x24 ; number of loops, in hex

    crunch:

    pop ax
    pop bx
    add sp, 4
    add ax, bx
    push ax
    loop crunch

    ret

    from http://patrickyeon.blogspot.com/2007/11/holy-cannoli-here-comes-assembly.html

  3. magnus on November 29th, 2007 6:27 pm

    If I define the equivalent program:

    > fibs = 1:1:(zipWith (+) fibs (tail fibs))
    >
    > main = do let x = fibs !! 200000 in print “done”

    and compile it,

    % ghc tmp.hs
    % time ./a.out
    “done”
    ./a.out 0.00s user 0.00s system 84% cpu 0.003 total

    0 seconds!!

    anyway if I shove a seq in there to force evaluation I get,
    8.73s user 0.04s system 99% cpu 8.773 total

  4. Jake on November 29th, 2007 6:38 pm

    @dons:

    You didn’t do anything wrong, but I had used the C++ interface instead of the C interface for legibility reasons. (there is some overhead involved)

      mpz_class fib(unsigned int num)
  {
    mpz_t a, b;
 
    mpz_init(a);
    mpz_init(b);
 
    mpz_set_ui(a, 1);
    mpz_set_ui(b, 1);
 
    while(num-- > 1)
    {
      mpz_swap(a, b);
      mpz_add(a, a, b);
    }
    cout<<mpz_class(a)<<endl;
  }
    Time: 1.85574 seconds
  5. Ungraspiness on November 29th, 2007 10:59 pm

    Lisp !

    http://jng.imagine27.com/articles/2007/11/29/dude-your-quad-cores-have-been-smoking-way-too-much-haskell

Leave a Reply