Paul Eggert <egg...@cs.ucla.edu> writes: Could you give an example of where the 128-bit code shines, compared to the GMP code on the same arguments? I could add the example as a comment in the factor.c code, to let me and future maintainers know why it's useful for performance.
Any number which does not happen to be B-smooth for, say B < 2^30, will show easily measurable performance difference of 5x to 40x IIRC. A semantic difference which sometimes makes the speed difference less pronounced is that the non-GMP code proves that the printed factors are indeed prime. We use a criterion which requires factoring of p-1 for any assumed prime factor p. In unlucky cases that recursive factorisation is costlier than the main factorisation. I have a patch which makes the non-GMP code some 2x - 3x faster. It's been maturing for several years now, so I suppose I should really finish it. (It got tangled with code which improves the GMP case by letting it fall into the non-GMP code as numbers get smaller. That sounds simple but is quite messy for various reasons. It is also not clear how much complexity we could defend for this command of limited utility.) -- Torbjörn Please encrypt, key id 0xC8601622
