3 ms·
> ... the "unoptimised" version is consistently between 4 and 5 times faster than the hand-optimised variants: I'm getting this comment a lot, but so far the r
by ColinWright 3y ago
> ... the "unoptimised" version is consistently between 4 and 5 times faster than the hand-optimised variants:
I'm getting this comment a lot, but so far the reason has been that people are using smallish numbers, and implementing the square root in floats.
In the context where this exploration is taking place, you can't do that. We're working with exact huge integers, and while a square root on floats can get you in the ballpark, you then need to refine the answer to get the exact value, and that takes order of magnitude the same time.
- asQuirreL 3y agoHow big are we talking? The benchmarks I tried the two numbers in your example, but yes, if you go above 2^53, then you will run into trouble with the naive solution, but that is for correctness reasons, not performance reasons.
- ColinWright 3y agoThis is an experiment on aspects of a factoring algorithm ... we're going to be talking about a few hundred digits base 10. So up to around 10^200 or so, which is around 2^600.
- asQuirreL 3y agoWell yes, that definitely changes the game!!