8 ms·
I expect a lot of time being wasted in `sqrt`, which is probably similar in the two languages.
by steerablesafe 6y ago
I expect a lot of time being wasted in `sqrt`, which is probably similar in the two languages.
- contravariant 6y agoYeah it's probably better to use something like k*k < n as a stopping condition. Though that one uses requires some additional calculation per step. I've once tried to fix that part by using the (usually discarded) result of `n div k` to determine when k < sqrt(n). I couldn't get it to work (faster) but it was fun to try.
- steerablesafe 6y agoInteresting. In principle that idea does look better, but the data dependency on the loop condition could be the bottleneck. CPUs probably have plenty of pipelining capacity to calculate `k*k` parallel to `n div k`, so effectively free as it's much faster than division.