Hi all, Fredrik Johansson recently wrote a function for computing primorials (2*3*5*7*11*13.....) in flint. As he implemented it at the mpn level, it strikes us that it should perhaps be contributed to MPIR, if there is any interest.
Strictly speaking, I think it relies on a few functions not already in MPIR, but most of the functionality is there (basically you just have to be able to sieve for a large number of primes from 0 to n, and the basic primality test stuff for single limbs that Peter Shrimpton and I already contributed basically covers this (except possibly the sieving). The code computes the primorial just using a lookup table for the first few primorials, then using a standard iterative multiplication for primorials that fit in a few limbs, and finally switches to a balanced multiplication for larger primorials, which is probably about the best you can do. I made it use as little memory as possible and did some minor adjustments to save some more time. It computes *ALL* the primorials (where primorial(n) is defined to be the product of all primes less than n) up to primorial(50000) in about 7 seconds. Anyhow, if anyone is interested, the code can be accessed at my git repository, in the roadmap branch, in the arith directory: http://selmer.warwick.ac.uk/flint2.git MPIR already has all the code contributed by Peter Shrimpton after he relicensed it LGPL v2.1+. The code by Fredrik and myself is currently under GPL v2+ but I imagine neither of us would have objections to changing that for MPIR. Note that we do not have explicit permission from Tom Boothby for any code he has contributed, to change the license on that, so please ask if that is needed, so we can contact him (we simply haven't asked). Of course this is not a huge contribution, but I know of other things coming that flint may be able to contribute to MPIR in the future (I'm still thinking about how best to finish off my FFT, and have an idea for a NTT which may or may not be of use in MPIR). If anyone has suggestions on how it might be made faster, don't hesitate.... Bill. -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.
