I think a blog post with PARI timings and then timings for a modular dsage approach would be cool.
--Mike On Tue, May 6, 2008 at 11:08 AM, William Stein <[EMAIL PROTECTED]> wrote: > > > On Tue, May 6, 2008 at 10:57 AM, David Harvey <[EMAIL PROTECTED]> wrote: > > > > > > > > On May 6, 2008, at 1:18 PM, William Stein wrote: > > > > > > > > On Tue, May 6, 2008 at 10:15 AM, <[EMAIL PROTECTED]> wrote: > > >> > > >> William has mentioned some congruence tests that we can perform > > >> -- I'd like to make sure that I got the right answer before we pat > > >> ourselves on the back too much. > > >> > > >> > > > > > > David Harvey's congruence tests would be pretty good. Just choose > > > *any* prime p > 10^7 + 10 > > > say and compute B_{10^7+4} modulo it using David Harvey's function; > > > > > > sage: p = next_prime(10^7+10) > > > sage: time bernoulli_mod_p_single(p, 10^7+4) > > > CPU times: user 0.49 s, sys: 0.00 s, total: 0.49 s > > > Wall time: 0.51 > > > 8087583 > > > > > > Pretty cool, eh? > > > > ..... and the natural question is, could you then reconstruct the > > actual bernoulli number, by computing it modulo sufficiently many > > primes? Well, I did the estimates a few days ago, and it turns out > > that the asymptotic behaviour of this proposed algorithm is pretty > > much *the same* as the one using the zeta function (i.e. the one Pari > > uses); they are both around n^2 log^2(n), if I'm not mistaken. > > Unfortunately, I did some further tests, and even if I sped up > > bernoulli_mod_p_single() by the largest factor I could conceive of, > > overall it would still be maybe 50x slower than Pari. If anyone can > > find an extra constant factor of 50x in this algorithm, I'd love to > > hear about it. > > > > I think maybe yours parallelizes much more easily than > Pari's, so just use 1000 computers :-). > > -- 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 -~----------~----~----~----~------~----~------~--~---