New mpz_lucas... functions
David Cleaver
wraithx at morpheus.net
Fri Jul 15 02:56:08 CEST 2011
On 7/14/2011 8:19 AM, bodrato at mail.dm.unipi.it wrote:
> Hi,
>
> Il Gio, 14 Luglio 2011 6:00 am, David Cleaver ha scritto:
>> int mpz_lucasu(mpz_t rop, int p, int q, int k)
>> int mpz_lucasumod(mpz_t rop, int p, int q, int k, mpz_t n)
>> int mpz_lucasv(mpz_t rop, int p, int q, int k)
>> int mpz_lucasvmod(mpz_t rop, int p, int q, int k, mpz_t n)
>>
>> With these functions, you can generate several familiar sequences, like:
>> U[k](1,-1) : Fibonacci Numbers
>> V[k](1,-1) : Lucas Numbers
>
> As you can see from the manual of GMP we already have:
>
> void mpz_fib_ui (mpz_t fn, unsigned long int n)
> void mpz_fib2_ui (mpz_t fn, mpz_t fnsub1, unsigned long int n)
> void mpz_lucnum_ui (mpz_t ln, unsigned long int n)
> void mpz_lucnum2_ui (mpz_t ln, mpz_t lnsub1, unsigned long int n)
Yes, I do know about these functions. However, these are just very specific
examples of Lucas U and Lucas V sequences. The program I wrote needed access to
the generalized sequences.
> I mean: the functions that are actually available in the standard GMP
> library, and are more similar to the functions you propose, use long int
> for the parameters and void for return. You should probably consider it.
I see no problem with using 'long int' for the functions. However, with the
generalized sequences, they can produce negative values and they can take
parameters that don't produce valid Lucas sequences. I use the return value
only to indicate whether the input parameters produced a valid sequence or not.
I'm not sure how you would indicate 'error' to the user with a void return.
>> my computer it takes about 0.03 seconds to calculate the 1000000th
>> Fibonacci Number.
>
> It would be nice to have a speed comparison with current code for
> Fibonacci. We may expect that the code in the library is faster, because
> it is not as general as yours, but the difference should not be too large.
Ah, good point. I put each into a 'for' loop that ran 100 times. The time for
my function was 2.96 seconds, and for mpz_fib_ui was 0.71 seconds.
>> I have a c file already written, but wanted to see if there was interest
>> before sending it out.
>
> I'd rather reverse the sequence. I suggest you to publish your code (with
> some free licence of your choice), so that anyone can test it. It can be
> useful even if it is not integrated in the GMP library yet.
Is there a license that would make this easier to include in GMP? I wouldn't
want to choose a wrong license and have my code rejected for that reason.
Also, I'd like to 'publish' the code, but I don't have a web site and am not
sure where to post it so that it is publicly available. Could you recommend a
place that is easy and free for everyone to access?
-David C.
More information about the gmp-discuss
mailing list