In my 3X+1 post, I needed to check if a value was odd or even. I did so by using “AND 1” which would test the least significant bit. This works, and is fast, but is limited to values 32767 or lower (15 bits).
Comments from William Astle, RogelioP and John offered corrections and updates to my code. I decided to benchmark a few different methods for detecting if a value was odd or even, and here is what I came up with.
0 REM 3x+1 Benchmarking 5 'GOTO 300 100 ' 0-32767 ONLY 110 TIMER=0 120 FOR A=1 TO 1000 130 IF X AND 1 THEN REM 140 NEXT:PRINT TIMER 200 ' ALL RANGES? 210 TIMER=0 220 FOR A=1 TO 1000 230 IF INT(X/2)=X/2 THEN REM 240 NEXT:PRINT TIMER 300 ' ROGELIO P 310 TIMER=0 320 FOR A=1 TO 1000 330 IF INT(X/2)*2=X THEN REM 340 NEXT:PRINT TIMER 400 ' WILLIAM ASTLE 405 T=0:H=0.5 410 TIMER=0 420 FOR A=1 TO 1000 430 T=X*H:IF T=INT(T) THEN REM 440 NEXT:PRINT TIMER 500 ' DIVIDE TEST 505 T=0:H=2 510 TIMER=0 520 FOR A=1 TO 1000 530 T=X/H:IF T=INT(T) THEN REM 540 NEXT:PRINT TIMER
When I run this program in Xroar on my Raspberry Pi 400, I get:
313 508 506 485 485
As expected, AND is the fastest, so use this if you know your values will be 32767 or lower.
Using INT(X/2)=X/2 was a fraction slower as INT(X/2)*2=X, which I guess makes sense since both do an INT and two math functions.
William’s suggestion of multiplying by .5 instead of dividing by two rang a bell. I believe he (or someone) pointed this out to me a few years ago when I was doing similar benchmarks. A big speed up comes just from putting the value in a variable, but I was surprised to see that dividing by a variable of 2 was the same speed as multiplying by a variable of .5.
What ideas do you have? Anything with math (“/2”) can be sped up by using a variable (“/H”), so there are some improvements just from that. Using HEX values (“&H2”) instead of decimal is also faster, as is removing extra spaces.
But are there better approaches we can use?