4 ms·

You would normally use something like newton-raphson to compute a square root, which still isn't O(1) but converges fairly quickly. I would be very skeptical t

by uxcn 11y ago

You would normally use something like newton-raphson to compute a square root, which still isn't O(1) but converges fairly quickly. I would be very skeptical that n muls/adds would be faster than an sqrt, at very least for x86-64 since it is implemented as an instruction.

Someone 11y ago
My mental model of a CPU is a 6502 or, at best, a 68000 without FPU :-) When asked about modern day performance, I would just say “I do not know”. Thing is that those muls, on modern CPUs, might be pipelined in parallel with the adds, so that, time wise, you would get them for free. But of course, it might be possible to get that sqrt for free, too. Even if it takes 50 cycles, you might start one, do a few iterations without checking for ‘reached sqrt(n) yet’, and then start a loop testing for the limit. If you really want to know for x_64, http://www.agner.org/optimize/ http://www.agner.org/optimize/ probably has the answers, but then, you would have to know the x86 instruction set, which is horrendous (compared to that 6502 or 68000). Even realising that there will be single, double and vector variants, the number of different instructions with ‘SQRT’ in their name I find in http://www.agner.org/optimize/instruction_tables.pdf http://www.agner.org/optimize/instruction_tables.pdf is insane. And of course, probably, something completely out of left field could well be the fastest way to do this (by a few ns, probably). For example, modern CPUs can count leading zeros in an integer. If that instruction is fast (for x86, that is not a given; ‘bit scan reverse’ was slow on some CPUs) subtract from 64/32/16, and halve, and you have a decent approximation to 2log(sqrt(n)) (using ‘if n has b bits, sqrt(n) has about b/2’)
- waterhouse 11y ago
  Incidentally, even if you are using Newton's method to do square roots, it helps significantly to start with a guess of the right size. If your initial guess is way too large, each step will cut it down by about a factor of 1/2; if it's way too small, it's equivalent (for finding sqrt(N)) to choosing N/guess. Thus, if you're taking the square root of 2^64, and you start with 1, your subsequent guesses will be roughly 2^63, 2^62, 2^61, 2^60, ..., taking a total of 36 steps to reach the right integer; whereas if you started with 2^33, it takes (by my computation) only 5 steps to get to the right integer. The effect is more significant with larger numbers: arc> (newton-steps (round (* 3/2 (expt 2 1000))) 1) 508 arc> (newton-steps (round (* 3/2 (expt 2 1000))) (expt 2 500)) 8
- uxcn 11y ago
  My mental model of a CPU unfortunately tends toward x86. > But of course, it might be possible to get that sqrt for free, too. Even if it takes 50 cycles, you might start one, do a few iterations without checking for ‘reached sqrt(n) yet’, and then start a loop testing for the limit. On the CPU side, the branch predictor might make the sqrt free by pipelining it, but that starts to make the analysis a bit harder. Strange things can happen when you introduce branch prediction. The performance would also depend on ALU/FPU contention, hyperthreads, etc... > If you really want to know for x_64, http://www.agner.org/optimize/ http://www.agner.org/optimize/ probably has the answers, but then, you would have to know the x86 instruction set, which is horrendous (compared to that 6502 or 68000). Even realising that there will be single, double and vector variants, the number of different instructions with ‘SQRT’ in their name I find in http://www.agner.org/optimize/instruction_tables.pdf http://www.agner.org/optimize/instruction_tables.pdf is insane. I've only just started reading Agner Fog's documentation (which is awesome), but it definitely seems like the place the find low level information of the ilk when it's needed. If you read through the instruction table though, you probably noticed there are fsqrt and (v)sqrt(p)(s/d). For most purposes, x87 is actually deprecated and SSE2, the latter, is preferred for scalar floating point. I would guess the Mill devs might have some insightful comments. > And of course, probably, something completely out of left field could well be the fastest way to do this (by a few ns, probably). For example, modern CPUs can count leading zeros in an integer. If that instruction is fast (for x86, that is not a given; ‘bit scan reverse’ was slow on some CPUs) subtract from 64/32/16, and halve, and you have a decent approximation to 2log(sqrt(n)) (using ‘if n has b bits, sqrt(n) has about b/2’) I'm not sure that's quite right. Counting leading zeros is normally very fast if you have the instruction, but those two functions diverge pretty quick. For a constant cost, my guess is that the accuracy lost wouldn't be performance gained. The other point is that accuracy is fairly important if you're testing for primality.
nibnib 11y ago
It's an FPU instruction with some setup and teardown instructions associated. I usually bow to Agner Fog on this: "On Core2 65nm, FSQRT takes 9 to 69 cc's (with almost equal reciprocal throughput), depending on the value and precision bits. For comparison, FDIV takes 9 to 38 cc's (with almost equal reciprocal throughput), FMUL takes 5 (recipthroughput = 2) and FADD takes 3 (recipthroughput = 1). SSE performance is about equal, but looks faster because it can't do 80bit math. SSE has a super fast approximate reciprocal and approximate reciprocal sqrt though. On Core2 45nm, division and square root got faster; FSQRT takes 6 to 20 cc's, FDIV takes 6 to 21 cc's, FADD and FMUL haven't changed. Once again SSE performance is about the same."
- uxcn 11y ago
  x87 is largely deprecated. Try inspecting the code emitted for floating point by all the major compilers.
  - nibnib 11y ago
    You are correct. It looks like SSE sqrt matches or beats fsqrt too.
    - uxcn 11y ago
      SSE performance is better than x87, for a number of reasons. Latency and throughput are generally better, but SSE also supports SIMD which allows more than one op per instruction. SSE also has more registers (x87 only has 8 80bit compared to at least 16 128bit). If I'm not mistaken, the number of available execution units with SSE is also larger, which means more opportunities for instruction level parallelism. These are why modern compilers don't emit x87 for floating point.

by uxcn 11y ago

Someone 11y ago

My mental model of a CPU is a 6502 or, at best, a 68000 without FPU :-) When asked about modern day performance, I would just say “I do not know”. Thing is that those muls, on modern CPUs, might be pipelined in parallel with the adds, so that, time wise, you would get them for free. But of course, it might be possible to get that sqrt for free, too. Even if it takes 50 cycles, you might start one, do a few iterations without checking for ‘reached sqrt(n) yet’, and then start a loop testing for the limit. If you really want to know for x_64, http://www.agner.org/optimize/ http://www.agner.org/optimize/ probably has the answers, but then, you would have to know the x86 instruction set, which is horrendous (compared to that 6502 or 68000). Even realising that there will be single, double and vector variants, the number of different instructions with ‘SQRT’ in their name I find in http://www.agner.org/optimize/instruction_tables.pdf http://www.agner.org/optimize/instruction_tables.pdf is insane. And of course, probably, something completely out of left field could well be the fastest way to do this (by a few ns, probably). For example, modern CPUs can count leading zeros in an integer. If that instruction is fast (for x86, that is not a given; ‘bit scan reverse’ was slow on some CPUs) subtract from 64/32/16, and halve, and you have a decent approximation to 2log(sqrt(n)) (using ‘if n has b bits, sqrt(n) has about b/2’)

waterhouse 11y ago
Incidentally, even if you are using Newton's method to do square roots, it helps significantly to start with a guess of the right size. If your initial guess is way too large, each step will cut it down by about a factor of 1/2; if it's way too small, it's equivalent (for finding sqrt(N)) to choosing N/guess. Thus, if you're taking the square root of 2^64, and you start with 1, your subsequent guesses will be roughly 2^63, 2^62, 2^61, 2^60, ..., taking a total of 36 steps to reach the right integer; whereas if you started with 2^33, it takes (by my computation) only 5 steps to get to the right integer. The effect is more significant with larger numbers: arc> (newton-steps (round (* 3/2 (expt 2 1000))) 1) 508 arc> (newton-steps (round (* 3/2 (expt 2 1000))) (expt 2 500)) 8
uxcn 11y ago
My mental model of a CPU unfortunately tends toward x86. > But of course, it might be possible to get that sqrt for free, too. Even if it takes 50 cycles, you might start one, do a few iterations without checking for ‘reached sqrt(n) yet’, and then start a loop testing for the limit. On the CPU side, the branch predictor might make the sqrt free by pipelining it, but that starts to make the analysis a bit harder. Strange things can happen when you introduce branch prediction. The performance would also depend on ALU/FPU contention, hyperthreads, etc... > If you really want to know for x_64, http://www.agner.org/optimize/ http://www.agner.org/optimize/ probably has the answers, but then, you would have to know the x86 instruction set, which is horrendous (compared to that 6502 or 68000). Even realising that there will be single, double and vector variants, the number of different instructions with ‘SQRT’ in their name I find in http://www.agner.org/optimize/instruction_tables.pdf http://www.agner.org/optimize/instruction_tables.pdf is insane. I've only just started reading Agner Fog's documentation (which is awesome), but it definitely seems like the place the find low level information of the ilk when it's needed. If you read through the instruction table though, you probably noticed there are fsqrt and (v)sqrt(p)(s/d). For most purposes, x87 is actually deprecated and SSE2, the latter, is preferred for scalar floating point. I would guess the Mill devs might have some insightful comments. > And of course, probably, something completely out of left field could well be the fastest way to do this (by a few ns, probably). For example, modern CPUs can count leading zeros in an integer. If that instruction is fast (for x86, that is not a given; ‘bit scan reverse’ was slow on some CPUs) subtract from 64/32/16, and halve, and you have a decent approximation to 2log(sqrt(n)) (using ‘if n has b bits, sqrt(n) has about b/2’) I'm not sure that's quite right. Counting leading zeros is normally very fast if you have the instruction, but those two functions diverge pretty quick. For a constant cost, my guess is that the accuracy lost wouldn't be performance gained. The other point is that accuracy is fairly important if you're testing for primality.

nibnib 11y ago

It's an FPU instruction with some setup and teardown instructions associated. I usually bow to Agner Fog on this: "On Core2 65nm, FSQRT takes 9 to 69 cc's (with almost equal reciprocal throughput), depending on the value and precision bits. For comparison, FDIV takes 9 to 38 cc's (with almost equal reciprocal throughput), FMUL takes 5 (recipthroughput = 2) and FADD takes 3 (recipthroughput = 1). SSE performance is about equal, but looks faster because it can't do 80bit math. SSE has a super fast approximate reciprocal and approximate reciprocal sqrt though. On Core2 45nm, division and square root got faster; FSQRT takes 6 to 20 cc's, FDIV takes 6 to 21 cc's, FADD and FMUL haven't changed. Once again SSE performance is about the same."

uxcn 11y ago
x87 is largely deprecated. Try inspecting the code emitted for floating point by all the major compilers.
- nibnib 11y ago
  You are correct. It looks like SSE sqrt matches or beats fsqrt too.
  - uxcn 11y ago
    SSE performance is better than x87, for a number of reasons. Latency and throughput are generally better, but SSE also supports SIMD which allows more than one op per instruction. SSE also has more registers (x87 only has 8 80bit compared to at least 16 128bit). If I'm not mistaken, the number of available execution units with SSE is also larger, which means more opportunities for instruction level parallelism. These are why modern compilers don't emit x87 for floating point.