speedup help

[Bill Wood]

Oleg has a very interesting approach; in particular, he avoids
explicit recursion and (most) computing with rationals, while
also replacing the factorials in binary coefficients by using
successive rows of Pascal's triangle. He also skips over the
B_{2k+1}, k > 0, which are all 0.

I slogged through the "standard" expansions, deriving a tail
recursive function that rolls along successive Bernoulli numbers,
generating successive rows of Pascal's triangle along the way,
and returning the list of B_n .. B_0.  You can think of the list
of Bernoulli numbers as "memoizing" just-in-time.

Running it in Hugs on a 650Mhz Athlon with 128M RAM, bernoulli 82
took ca. 1 sec.  Compiling with ghc -O, bernoulli 1000 took approx.
15 sec. wall time; bernoulli 10000 blew the heap.

I couldn't get getCPUTime (from module CPUTime) to work for me; if
anyone can enlighten me on how to get timing of function execution
I'd appreciate it.

BTW profiling didn't work; when I tried to compile with profiling
flags I received error msgs saying that interface files for standard
libraries couldn't be found.  Compiling without the flags seems to
work just fine.

Oleg's program brings up another interesting point for all you
mathematicians out there: I found two basically different expansion
formulas for Bernoulli numbers.  One is based on the formal
expansion of the equation

    (B + 1)^n = B^n

which results in binomial-theorem expansions all of whose terms are
positive.  The other is based on formal expansion of the equation

    (B - 1)^n = B^n

which results in binomial-theorem expansions whose terms alternate
in sign.  The amazing thing is, they two sets of numbers only differ
at one term: the first formula results in B_1 = -1/2 while the
second results in B_1 = +1/2 !

I found the second formula in Conway & Guy, _The Book of Numbers_,
p.108.
The second formula, with tiny variations, can be found in Knuth,
_Fundamental Algorithms_, p. 109, Abramowitz & Stegun, _Handbook
of Mathematical Functions_, p. 804 and Song Y. Yan, _Number Theory for
Computing_, p. 75

This has gotten a little long, sorry.  If you want I can post my Haskell
code or send privately.

 -- Bill Wood
    wtwjek@winternet.com