# algorithms matter

By Hal Canary, 2010-03-11 18:48:25 (link)
#computer-science;#computers-code

This example of why the right algorithm matters comes directly from my textbook. Here's the C implementation:

```#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));
}
}```

(back)