algorithms matter
This example of why the right algorithm matters comes directly from my textbook. Here's the C implementation:
Bad:
#include <stdio.h> #include <stdlib.h> long int fib(long int n) { if (n==0) return 1; if (n==1) return 1; return fib(n-1) + fib(n-2); } int main(int argc, char *argv[]) { if (argc <= 1) { fprintf(stderr, "argument?\n\n"); exit(1); } long int n = atol(argv[1]); printf("f(%li) = %li\n",n,fib(n)); return 0; }
Good:
#include <stdio.h> #include <stdlib.h> long int fib(long int n) { long a=1, b=1, c; int i; for (i = 1;i < n; i++){ c = a + b; a = b; b = c; } return b; } int main(int argc, char *argv[]) { if (argc <= 1) { fprintf(stderr, "argument?\n\n"); exit(1); } long int n = atol(argv[1]); printf("f(%li) = %li\n",n,fib(n)); return 0; }
Output:
$ time ./fib2 38 ; time ./fib1 38 f(38) = 63245986 real 0m0.002s user 0m0.000s sys 0m0.004s f(38) = 63245986 real 0m1.492s user 0m1.428s sys 0m0.004s
And you can show how nicely the good algorithm scales up by pulling out a bigint library, like Java's BigInteger:
public class fib3 { public static String fib(int n) { java.math.BigInteger a,b,c; int i; a = b = java.math.BigInteger.ONE; for (i = 1;i < n; i++) { c = a.add(b); a = b; b = c; } return b.toString(); } public static void main(String[] args) { if (args.length < 1) { System.err.println("argument?"); System.exit(1); } int n = Integer.parseInt(args[0]); System.out.print("f(" + Integer.toString(n) + ") = "); System.out.println(fib(n)); } }