I did some computations using von Staudt's theorem and up to 400000 no errors. Of course that doesn't prove anything for much larger n.
Bill. On 2 May, 21:04, "William Stein" <[EMAIL PROTECTED]> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
