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