Front page | perl.fwp | Postings from November 2001

## Re: Feel good benchmarks

From:
Ariel Scolnicov
Date:
November 20, 2001 23:52
Subject:
Re: Feel good benchmarks
Message ID:
yzqwv0klfy3.fsf@compugen.co.il
```Michael G Schwern <schwern@pobox.com> writes:

[...]

> Of course, if I wanted this to be a fair test (which I don't), I'd do:

[... snipped code for linear-time Fibonacci ...]

> 139423224561697698330489613862193018947914545343780323868775030943672596190605867771863846635039486902272
> real    0m0.051s
> user    0m0.000s
> sys     0m0.020s

[...]

For mission-critical enterprise-level high-throughput Fibonacci
generation, you want to logarithmic-time algorithm.  Since I already
have the C code, I'll not write the Perl...

/*
* fib-fast -- Demonstrate fast Fibonacci numbers
*/

#include <stdlib.h>
#include <stdio.h>

struct sym22 {
/* matrix is [[a b] [b c]] */
double a,b,c;
};

struct sym22 fib_helper(int n)
{
struct sym22 ret, val;
if (n == 1) {
ret.a = 1;
ret.b = 1;
ret.c = 0;
}
else if (n % 2 == 0) {
val = fib_helper(n/2);
ret.a = val.a*val.a + val.b*val.b;
ret.b = val.b * (val.a+val.c);
ret.c = val.b*val.b + val.c*val.c;
}
else {
val = fib_helper(n-1);
ret.a = val.a + val.b;
ret.b = val.a;
ret.c = val.b;
}
return ret;
}

double fib(int n)
{
struct sym22 val;

if (n == 0)
return 0;
else if (n == 1)
return 1;
else {
val = fib_helper(n-1);
return val.a;
}
}

int main(int ac, char *av[])
{
int n;

if (ac < 2) {
fprintf(stderr, "Usage: %s n1 [n2 ...]\n", av[0]);
return EXIT_FAILURE;
}

while (--ac) {
n = atoi(*++av);
printf("%.0f\n", fib(n));
}
return EXIT_SUCCESS;
}

<hal2 92 [9:50] ~/Tests >/usr/bin/time ./fib-fast 500
139423224561697873388268830107091057642465893024716039229340111610069135233925734164006795046787674537984
0.00user 0.00system 0:00.00elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (98major+9minor)pagefaults 0swaps

This is on a 600MHz Pentium III processor, but it doesn't run long
enough...

<hal2 95 [9:51] ~/Tests >/usr/bin/time ./fib-fast 1000
43466557686937445756758626039894611553701353407918435513335922439814646420061776153691392866339003153875487831495402253175034279652685126479563531171769845954876100774304900908596931657345607837880560339910656
0.00user 0.00system 0:00.00elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (98major+9minor)pagefaults 0swaps

Running it in a loop for 100_000 iterations takes 0.24 seconds (user
time), so we're doing 400_000 calculations of F_1000 per second.

Algorithms count!

--
Ariel Scolnicov        |"GCAAGAATTGAACTGTAG"            | ariels@compugen.co.il
Compugen Ltd.          |   +++ THIS SPACE TO LET +++   	\ We recycle all our Hz
72 Pinhas Rosen St.    |Tel: +972-3-7658117 (Main office)`---------------------
Tel-Aviv 69512, ISRAEL |Fax: +972-3-7658555    http://3w.compugen.co.il/~ariels

```