R
Richard Heathfield
(e-mail address removed) said:
Look up sqrt() in your C book. That's how my code gets the square root. And
my program works significantly faster than yours, so I think it's safe to
say that introducing the sqrt() call was not too terribly inefficient.
Or you could just write your own integer-based Newton-Raphson search if you
prefer.
Yes, your super-efficient division by 2 is considerably faster than my
lumbering sqrt call. Undoubtedly this explains the performance difference
between our two programs (although not perhaps in the way you'd like us to
think).
[X-posted, and followups set]
I found something interesting on the Web today, purely by chance.
It would be funny if it weren't so sad. Or sad if it weren't so funny.
I'm not sure which.
http://www.developerdotstar.com/community/node/291
Something I wondered about was why the code tests numbers up through
half the highest value (call it N), rather than up through sqrt(N),
which is clearly (?) sufficient. Most discussions I've read of this
algorithm stop at sqrt(N), though perhaps the original algorithm
didn't?
I saw this recommendation in 1974 (in Wirth) and it makes perfect
sense...if you have an efficient way to get square root.
Look up sqrt() in your C book. That's how my code gets the square root. And
my program works significantly faster than yours, so I think it's safe to
say that introducing the sqrt() call was not too terribly inefficient.
Or you could just write your own integer-based Newton-Raphson search if you
prefer.
Dividing by 2 is implemented by a fast shift in modern compilers which
"loses" the remainder but for the test used, all you need is the value
of the floor.
Yes, your super-efficient division by 2 is considerably faster than my
lumbering sqrt call. Undoubtedly this explains the performance difference
between our two programs (although not perhaps in the way you'd like us to
think).