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

Reply via email to