On Sun, Aug 21, 2011 at 5:37 PM, David Cleaver <wrai...@morpheus.net> wrote: > Hello all, > > Not too long ago I needed some mathematical functions that I couldn't really > find implemented anywhere. I eventually stumbled on someone's > implementation and was able to code it up with GMP. I was wondering, would > there be any interest in including these functions in the official MPIR? > The functions are the Lucas U and Lucas V sequences, defined with > parameters p and q. Here are the prototypes: > > int mpz_lucasu(mpz_t rop, long int p, long int q, mpz_t k) > int mpz_lucasumod(mpz_t rop, long int p, long int q, mpz_t k, mpz_t n) > int mpz_lucasv(mpz_t rop, long int p, long int q, mpz_t k) > int mpz_lucasvmod(mpz_t rop, long int p, long int q, mpz_t k, mpz_t n) > > You can download the code at the sourceforge site: > http://sourceforge.net/projects/mpzlucas/files/
I don't know if they're appropriate for MPIR. They would be really nice to have in FLINT (http://flintlib.org/), where we already have some functionality for generating special number sequences. Your code should also run quite a bit faster for small to moderate k (k < 100?) if ported to the fmpz type in FLINT. Is there a reason not to allow p and q to be mpz's? It seems entirely reasonable to me to allow bignum coefficients, and it shouldn't really affect performance. Conversely, why is k an mpz in mpz_lucasu/mpz_lucasv? It makes sense in the mod versions, but otherwise I don't think the result can fit in memory for k larger than a long, except in the trivial case p = q = 0. > Along with these Lucas functions, I'd also like to propose that we add > several new prp functions to the official MPIR library. Here are the > prototypes for the new prp functions: > > int mpz_prp(mpz_t n, mpz_t a) aka: Fermat pseudoprime > int mpz_euler_prp(mpz_t n, mpz_t a) aka: Solovay-Strassen pseudoprime > int mpz_sprp(mpz_t n, mpz_t a) aka: Miller-Rabin pseudoprime > int mpz_fibonacci_prp(mpz_t n, long int p, long int q) > int mpz_lucas_prp(mpz_t n, long int p, long int q) > int mpz_stronglucas_prp(mpz_t n, long int p, long int q) > int mpz_extrastronglucas_prp(mpz_t n, long int p) > int mpz_selfridge_prp(mpz_t n) aka: Lucas-Selfridge pseudoprime > int mpz_strongselfridge_prp(mpz_t n) aka: strong Lucas-Selfridge pseudoprime > int mpz_bpsw_prp(mpz_t n) > int mpz_strongbpsw_prp(mpz_t n) > > Where each function can return one of: > #define PRP_ERROR -1 > #define PRP_COMPOSITE 0 > #define PRP_PRP 1 > #define PRP_PRIME 2 This kind of functionality would again probably be welcome in FLINT (where we plan to add more extensive support for primality testing and factoring) if not in MPIR itself. A couple of these primality tests are already implemented very efficiently for word-size numbers in FLINT, I think. Regarding the interface, I would generally just make these functions raise an exception if the parameters are invalid, instead of returning an error code. Fredrik -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to mpir-devel@googlegroups.com. To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.
