On Aug 31, 2007, at 3:29 PM, William Stein wrote:
>> 3. Is it possible to compute one bernoulli number mod p directly,
>> rather than computing a whole list of them with bernoulli_mod_p and
>> then picking a specific one out of the list?
>
> The algorithm of Buhler et al for computing bernoulli_mod_p
> involves series
> arithmetic and does not compute just one. There is no algorithm
> that I'm
> aware of that computes just one bernoulli number mod p without
> computing
> a lot more, and which doesn't just compute the Bernoulli number
> over QQ
> and reduce it mod p:
In fact it can be done a bit more quickly. The short version is: you
can save a factor of log(p) (and probably a large constant too) if
you only want one of them. I don't know if that's good enough for
what you want.
Long version:
The algorithm I used to implement bernoulli_mod_p basically
multiplies two polynomials of length O(p) over Z/pZ. Then it
multiplies each resulting coefficient by a certain fudge factor, and
the resulting vector of coefficients turns out to be the bernoulli
numbers B_0, B_2, ..., B_{p-3} mod p. So if you only wanted *one* of
them, then instead of doing the whole polynomial multiplication, just
compute the required term in the product, i.e. just multiply out the
appropriate pairs of coefficients from the two polynomials that would
normally be multiplied together. Assuming your p fits in a word, this
algorithm has complexity O(p), and can be done in constant space.
I don't know if this is faster/slower than just computing the
bernoulli number over Q and reducing.
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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
