New mpz_lucas... functions

[David Cleaver]

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.