Collatz Sequence
|
| Author | Content |
|---|---|
| Bob_Robertson May 06, 2013 4:25 PM EDT |
Folks, As per a previous thread, where everyone seemed to know what I was talking about, I recreated the BYTE basic-programming puzzle from so very long ago, to wit: If the number is odd, multiply by three and add one, if even then divide by two, and any number will eventually reach 1. "What number takes the greatest number of iterations?" Anyway, I did it in C, on my present box. As I recall, testing every number from 2 to 500 in TRS-80 interpreted basic took several minutes. Compiled basic was quicker, while the Pascal for the same box was woefully slow to do the same task, some 20 minutes. Fortran took a while, as well. It was the hardware. The last time I ran it, in C on a DOS 386-33, it took less than 10 seconds. Just now, in order to get this result: $ time ./cpuzz ...(output omitted because it really doesn't matter) real 0m0.069s user 0m0.044s sys 0m0.004s I had to run it not on all integers from 2 to 500, but from 2 to 100,000. I had a friend who borrowed the Apple Cray for this test who had to increase the top number to 1,000 in order to get a measurable response. That was 1990. Wow. |
| gus3 May 06, 2013 4:48 PM EDT |
I have yet to find a compiled language with optimizations that can beat hand-assembled code at the Collatz sequence. It's true for x86, x86_64, ARM, and Sparc. If someone wants to send me an Itanium or an S/390, I'll try my hand at that, too. |
| Bob_Robertson May 07, 2013 8:34 AM EDT |
Of course, I'm putting no effort into optimizing, just playing. One difference this time, though, is that rather than comparing the integer value of "x/2" to the float value of "x/2", and if they're different it's odd, I found the binary compare "x & 1" which I expect was a substantial improvement on the scheme. Thanks for reminding me of the name, "Collatz Sequence", I couldn't remember it to put it in the title. Thank you for your indulgence, I know this is exceptionally unimportant. |
| Bob_Robertson May 07, 2013 9:43 AM EDT |
THANKYOU! Whatever board gods changed the title, thank you. Nicely done. |
You cannot post until you login.