On Monday 22 August 2011 10:28:23 Fredrik Johansson wrote: > 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. >
I agree I dont know if they are appropriate for MPIR (or FLINT for that matter) , perhaps we should start a new library just for number theory stuff , like prime testing and factoring , and leave MPIR for basic math and FLINT for polys . For sizes up to a few words there a some speed ups to integrating the packages more closely than we do now , but for large sizes it's just a bit of a pain , and pointless. > 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. I think they are necessary for fully random lucas psuedoprime tests , although in practice it's ignored (just like the strong psuedoprime tests) > 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. > I skimmed through the pdf reference you gave and the method proposed there is not the fastest if I interpreted it correctly. See PRIME NUMBERS A COMPUTATIONAL PERSPECTIVE by Crandall and Pomerance , the method there is upto twice as fast. > > 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.
