New mpz_lucas... functions
David Cleaver
wraithx at morpheus.net
Thu Jul 21 14:11:52 CEST 2011
On 7/16/2011 2:08 PM, David Cleaver wrote:
> You can find the C file at the following location:
>
> http://sourceforge.net/projects/mpzlucas/files/
>
> If anyone has any questions or problems, please let me know.
> I'm all for optimizing, and wouldn't mind seeing the k changed to an mpz_t. Let
> me know how this works for everyone and what changes and/or additions we think
> might be necessary.
I've updated all of the mpz_lucas* functions. One motivation for this was that
the mpz_lucasumod code produced correct results, but did not bound its
intermediate values. There was only one mod taken at the end. I have found
another implementation that allowed me to use mods during the computation, thus
keeping intermediate variables bounded. When I timed this new algorithm against
my existing implementation I saw that the new algorithm was 2.8 times faster for
mpz_lucasu and was 2.5 times faster for mpz_lucasv. Here are some timings of my
old code, my new code, and GMP when computing the 1000000th Fibonacci and Lucas
numbers. (in a simple 'for' loop run 100 times)
lu = 2.9531 seconds (my old code)
lu2 = 1.0625 seconds (my new code, about 2.8x faster than lu)
fib = 0.7031 seconds (GMP)
lv = 1.0781 seconds (my old code)
lv2 = 0.4219 seconds (my new code, about 2.5x faster than lv)
luc = 0.4219 seconds (GMP)
I've changed the parameters p and q to be long ints, and I've changed k to be an
mpz_t. So the new function prototypes look like:
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 new code at the above link.
-David C.
More information about the gmp-discuss
mailing list