5 ms·

Decreasing the loop's upper bound to Math.sqrt(value) and only testing odd values after 2 are really simple ways to improve performance. Beyond that it'd be ni

• xigency 11y ago
  It's faster to check that the value isn't less than the loop counter squared than to perform a square root.
  • parfe 11y ago
    No it isn't. You only calculate the square root once, vs calculating the square at each iteration.
    • JoeAltmaier 11y ago
      Calculating a square is ~1. A square root it ~N. Much harder to do. Its a common optimization in graphics code to compare squares for this reason.
      • borkabrak 11y ago
        She's right about squaring on each iteration, though. And granted, a square root is much more expensive, though done only once. Which method is faster would depend on the number of iterations.
        • uxcn 11y ago
          The latency for sqrtss on broadwell is 11 cycles with a throughput of 4, where mul is a latency of 3 and throughput of 1. So, using some concrete numbers, sqrt is more expensive, but not polynomially or even an order of magnitude.
          • JoeAltmaier 11y ago
            Right with modern floating point implementations its not the old guess-and-iterate method any more. SQRT is probably now on the order of an inverse?
            • uxcn 11y ago
              I honestly haven't looked into it in that much detail, but if I had to guess... probably. I'm not sure what the implementation used in hardware currently is, but at very least it's constant bounded, Conversions are still somewhat expensive, but I do know compared to polynomial time or a large enough constant, it can be a better choice for an optimization. For example, computing log10 of an integer.
      • shasta 11y ago
        Since you're claiming that square root is "~N", the N here must be the number of digits. The number of multiplications required for the "optimization" you're proposing is exponential in this N.
  • Someone 11y ago
    If you go that way, it may be even faster (depending on you CPU, of course) to use a recursion for computing the squares: (n+1)^2 = n^2 + 2n + 1 That gets you: def squares: n = 1 nSquared = 1 delta = 1 while nSquared <= n: n += 1 yield n delta += 2 nSquared += delta but as others said, once your limit is large enough, the relatively large cost of computing a square root once may be lower than the O(sqrt(n)) additions in this loop. (Quick check: if you use a binary search to find sqrt(n), you need 2log(n) iterations, each of which requires a division by two (for integers, that is a bit shift) and one addition. A linear search takes sqrt(n) iterations, each with three additions. For whatever ratio of speed of operations you pick, the former will be faster for sufficiently large n)
    • 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’)
• andrepd 11y ago
  Dynamic programming (testing divisibility by the primes already found) would greatly improve the algorithm. And of course sieving is absurdly fast compared to checking primality individually.