[PATCH] Fibonacci/Lucas tweaks

[marco.bodrato at tutanota.com]

Ciao David,

17 feb 2026, 01:54 da sparks05 at proton.me:

> On Monday, February 16th, 2026 at 23:49, marco.bodrato at tutanota.com <marco.bodrato at tutanota.com> wrote:
>
>> Why did you swap that test (order [edited])?
>>
> Would you like a revised patch that puts it back the way it
> should be, or are you happy to do that yourself?
>
I reduced the patch as much as I could. That way I now understand what it changes: it asks to fib2_ui the values for k+1 instead of k, so that a portion of the code can be skipped.
But the copyleft of the idea and the comments is still yours.
Did you already pass the paperwork phase to contribute to FSF?

I also skipped the "lalloc = MPN_FIB2_SIZE (n + 2) -1" change, because its impact is very small and is risks an overflow when n > ULONG_MAX - 2.
If unsigned long is 32 bits, ULONG_MAX is not that large.
Should we wrap the change with an #if?#if BITS_PER_ULONG > 50

The "Notes", lines 39-54, should be updated too.
>> I wonder if it's wort adding a condition:
>>   if (FIB_TABLE_LUCNUM_LIMIT < FIB_TABLE_LIMIT)
>>     /* L[n] = F[n+1] + F[n-1] */
>>     lp[0] = FIB_TABLE ((int) n + 1) + FIB_TABLE ((int) n - 1);
>>   else
>>     /* L[n] = F[n] + 2F[n-1] */
>>     lp[0] = FIB_TABLE (n) + 2 * FIB_TABLE ((int) n - 1);
>>
> Er, FIB_TABLE_LIMIT - 2 <= FIB_TABLE_LUCNUM_LIMIT <= FIB_TABLE_LIMIT-1.
>
> It should be pretty obvious.
> F[n+1] = F[n] + F[n-1] < F[n+1] F[n-1] = L[n] < F[n+1] + F[n] = F[n+2].
>
Of course you are right!
I should sleep at night, instead of writing e-mails :-)

But the question is:
should we use
  FIB_TABLE (n) + 2 * FIB_TABLE (n - 1);
or
  FIB_TABLE (n + 1) + FIB_TABLE (n - 1);
?
Almost equivalent, probably. So we can simply let this unchanged...

> The proposed one: a couple of shifts, an and mask, 3 additions.
>
>> How much does the MPN_FIB2_SUB term change the result?
>>
>
> By 1.16 bits, i.e. one 64-bit limb 1.8% of the time.
> I'd have omitted it, but we need an additive constant for the +1
> limb anyway, so fine-tuning it doesn't cost more.
>
There already is a +1, let's use +2.

>> Should we replace this estimate with a single umul_ppmm (_result, _dummy, n, _const) like we do in macros like DIGITS_IN_BASE_FROM_BITS?
>>
>> The constant could be generated by gen-fib.c
>>
> #define GMP_RADIX (1.0 * (CNST_LIB(1) << GMP_NUMB_BITS/2) * (CNST_LIB(1) << (GMP_NUMB_BITS+1)/2)
> #define MPN_FIB2_MULT (1+ (mp_limb_t)(0.6942419136306173017387902668986 * GMP_RADIX / GMP_NUMB_BITS))
>
> It's simple compile-time math.
>
Oh, I fear the result is larger than needed when GMP_NUMB_BITS is 128 :-D

Ĝis,
mb
-------------- next part --------------
A non-text attachment was scrubbed...
Name: lucnum_ui.patch
Type: text/x-patch
Size: 1857 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20260217/583c3afd/attachment.bin>