On Fri, May 2, 2008 at 12:55 PM, David Harvey <[EMAIL PROTECTED]> wrote: > > > On May 2, 2008, at 3:45 PM, William Stein wrote: > > > The complexity mostly depends on the precision one uses in > > computing a certain Euler product approximation to zeta > > and also the number of factors in the product. If you look > > at the PARI source code the comments do *not* inspire confidence in > > its correctness. I had a student give a provable bound on precision > > and number of factors needed and wasn't able to get anything > > as good as what PARI uses. > > > > Here's the funny part of the PARI code (in trans3.c): > > > > /* 1.712086 = ??? */ > > t = log( gtodouble(d) ) + (n + 0.5) * log(n) - n*(1+log2PI) + > > 1.712086; > > One way to check it is to use the bernoulli_mod_p_single() function, > which computes B_k mod p for a single p and k, and uses a completely > independent algorithm. > > sage: x = bernoulli(240000) > > sage: p = next_prime(500000) > sage: bernoulli_mod_p_single(p, 240000) > 498812 > sage: x % p > 498812 > > sage: p = next_prime(10^6) > sage: bernoulli_mod_p_single(p, 240000) > 841174 > sage: x % p > 841174 > > So I would say the answer is correct. > > david
I've done numerous similar tests, and I definitely don't think PARI is giving wrong answers. The issue is just that I've written a paper to generalize the algorithm to generalized Bernoulli numbers, and was very annoyed that I couldn't prove that even the algorithm used by PARI worked. -- William --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
