Front page | perl.fwp | Postings from November 2001

## Re: Feel good benchmarks

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

> On Wed, Nov 21, 2001 at 09:51:32AM +0200, Ariel Scolnicov wrote:
> > > 139423224561697698330489613862193018947914545343780323868775030943672596190605867771863846635039486902272
> >
> > For mission-critical enterprise-level high-throughput Fibonacci
> > generation, you want to logarithmic-time algorithm.
> >
> > <hal2 92 [9:50] ~/Tests >/usr/bin/time ./fib-fast 500
> > 139423224561697873388268830107091057642465893024716039229340111610069135233925734164006795046787674537984
> >
> > Algorithms count!
>
> So does correctness, yours gives the wrong answer.

Actually, we're using doubles.  And their mantissa is hardly big
enough to give that many digits of precision.  They have what? 56
bits?  That's enough to represent 36028797018963967 exactly.  So let's
try bc:

a=1
b=0
for(i=0; i<499; i++) { c=a+b; b=a; a=c; }
c
13942322456169788013972438287040728395007025658769730726410896294832\
5571622863290691557658876222521294125

Mine is a bit closer (the error is 3% what yours is).

Which makes sense: we're both doing repeated floating-point addition.
(Once the numbers are big enough) every time you add you lose

[...]

Will recode in Perl with Math::BigInt so we can both get correct
results and compare speeds in a more realistic test of Fibonacci
computation...

--
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

```