Michael G Schwern <[EMAIL PROTECTED]> 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" | [EMAIL PROTECTED]
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
