Feature #797
SmallFpImpl: make it faster
Description
After comparing gcd for DUPFp and DUPFF, I saw that the latter was significantly faster (e.g. factor 2 or more in some cases)
Investigating I saw that the old finite field impl did create log/exp tables (for primes up to a certain limit), and these tables were used to compute implement "shift-add" inside the euclidean algorithm.
Consider whether to have a smallfp impl which combines both SmallFpImpl and SmallFpLogImpl.
Related issues
History
#1
Updated by John Abbott over 8 years ago
Updated by - Status changed from New to In Progress
- Assignee set to John Abbott
- % Done changed from 0 to 10
The speed gains varies form platform to platform -- surprise, surprise!
The old DUPFF code was (significantly) faster for GCD of high degree polys with coeffs in medium sized finite fields. The new code was faster (on my old MacBook Pro) when the prime was large (e.g. 32003). I should conduct some more speed tests.
Should SmallFpImpl automatically include a SmallFpLogImpl? Or should there be a new SmallFpXYZ class which includes both?
#2
Updated by John Abbott over 8 years ago
- the advantage of having log/exp tables is that some computations can be noticeably faster (e.g. gcd as mentioned in the intro)
- the disadvantage is that it takes longer to construct a (small prime) finite field, and the field itself occupies more space (for the tables)
Overall, I think it is probably worth offering a combined implementation sooner or later; there will also be the question of which impl to use by default when the user asks for a small, prime finite field.
#3
Updated by John Abbott over 6 years ago
- Related to Feature #1154: SmallFpImpl: new ctor arg to say do-not-check-that-arg-is-prime added
#4
Updated by John Abbott 2 months ago
- % Done changed from 10 to 20
I have just wasted quite a bit of time thus evening rediscovering this phenomenon... sigh!
I should consider making the log/exp tables optional, perhaps with a call that triggers their creation (if appropriate).
We do not want to create the tables if the modulus is too large.
For instance, a call to DUPFp gcd with high degree polynomials could trigger the creation of the tables.
The impl of gcd will then have have to test whether the tables exist, and then call the relevant impl so...
Not exactly KISS, but a speed gain by a factor of 2-3 is very enticing!