msieve icon indicating copy to clipboard operation
msieve copied to clipboard

Simplify perfect-square testing loop

Open tim-one opened this issue 6 years ago • 0 comments

There's no need for the bits variable here. The number of loop iterations can be cut in half by repeatedly shifting right by 2 so long as the last 2 bits are zeroes. If there were in fact an odd number of trailing zero bits in q0, that will leave tmp with a last bit of 0, and so it won't pass the later (tmp & 7) == 1 test. If there were an even number of trailing zero bits, tmp is left the same as before the change, and again the only real thing left to test is whether (tmp & 7) == 1.

Caution: I didn't test or even compile this code! I was just browsing this on the web, and am using the web UI to edit. I've used the same trick in other projects, and am sure it's sound (give it a little thought - it's obvious ;-) ). Apologies in advance for any typos.

tim-one avatar Jul 25 '18 00:07 tim-one