Two 10-lines functions

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> I mean: after many recursions, we can hit an odd number above the threshold.
> I agree: speeding up that small product, buried in the 9th recursion level
> of a large product, will probably not be very relevant;

That multiplication should be less than 2^-9 of the total work (I get
2^-9 if I assume multiplication is linear, and since it's actually more
or less super linear, the correct value should be less than 2^-9). So
even if one could do that operation for free, the overall saving would
be at most 0.2%...

> but it may be cheaper than adding 2^9 limbs at the top level.

Interesting observation. One way to look at it, is that since we get the
main part of the savings from the first few levels of recursion,
enabling deeper recursion does not justify rounding up the size more
than a few limbs (say, to a multiple of 8 or 16 or so). Beyond this,
rounding up is justified by the need to get an appropriate size for the
largest fft call.

Which I think is also how the current mulmod_bnm1_nextsize works.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.