 |
 Mathematical quiz
|
|
|
Bjørn
|
|
Wed Feb 20 2008, 12:39PM
|
|
|
Registered Member #27
Joined: Fri Feb 03 2006, 02:20AM
Location: Hyperborea
Posts: 2058
|
L movs r1,r0,lsr #1
adccs r1,r0,r0,lsl #1
mov r0,r1
bne L
1. What does this code do
2. What is the name of the mathematician that made a conjecture about this algorithm
3. Which fundamental computability problem does it illustrate
The idea here is to learn something, that is why I tried to make it difficult to use Google to get the answers without thought.
|
|
Back to top
|
|
|
Avi
|
|
Registered Member #580
Joined: Mon Mar 12 2007, 03:17PM
Location: Melbourne, Australia
Posts: 410
|
from what i can work out using the ARM datasheet and some notes on ARM assembly, I'd say it does this.
pseudo code 1:
label0
r1=r0/2
carry=lsb(r0)
zero=ifzero(r1)
if carry is set then r1=r0+(r0*2)+carry
r0=r1
if zero isnt set then jump to label0
pseudo code 2 expanded:
loop=true
do while loop=true
if lsb(r0) then
r1=(r0*3)+1
else
r1=r0>>1
end if
loop=false
if r1<>0 then loop=true
r0=r1
loop
So it seems quite complex. It does not seem easy to work out how many times it will loop or if it will exit, by just looking at it.
|
|
Back to top
|
|
|
Bjørn
|
|
Registered Member #27
Joined: Fri Feb 03 2006, 02:20AM
Location: Hyperborea
Posts: 2058
|
That is correct. Most of the information needed to solve part 1 can be found in the HvWiki 
It is remarkably complex for a 4 instruction long program. The difficulty to fully grasp it is what makes it interesting to matematicians and hints to the answer of part 3.
Part 2 is just a simple google search away for someone that is used to seach for mathematical equations (simple or not).
|
|
Back to top
|
|
|
Chris Russell
|
|
... not Russel!
Registered Member #1
Joined: Thu Jan 26 2006, 12:18AM
Location: Tempe, Arizona
Posts: 1052
|
Basically, the program does this:
Divide r0 by two, store the result in r1, set the zero and carry flags appropriately. If that operation sets the carry flag (r0 was not even, but was odd), multiply r0 by three and add one, and store that result in r1. Copy the value of r1 to r0. If the zero flag has not been set, start over.
Basically, you are basically starting the loop with some integer, r0. If r0 is even, divide it by two. If it's odd, multiply it by three and add one. This process repeats until it reaches one of the powers of two, at which point it will slide down the ladder quickly, finally reaching one and then exiting, ending something like 64,32,16,8,4,2,1. But does this always work? Will it always reach one? Difficult to say just by looking at it.
Curiously, on the last iteration, when r0 is set to 1, r0 will be set to 4 before the loop exits. I suppose you would extract the correct sequence if you extracted your output between the adccs instruction and the mov instruction.
Here's what I would get in c, this should be more or less correct:
int r0 = ; /* starting number here */
int r1,zero;
do
{
r1 = r0 / 2;
zero = r1;
if (r0 & 1)
{
r1 = (r0 * 3) +1;
}
r0 = r1;
} while (zero);
Complete program, modified to accept an integer from the command line and have nice output, is attached.
]bjoern.c.txt[/file]
Example output:
Variable check: 123
Starting...
123, 370, 185, 556, 278, 139, 418, 209, 628, 314, 157, 472, 236, 118, 59, 178, 89, 268, 134, 67, 202, 101, 304, 152, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, done!
Variable check: 112486
Starting...
112486, 56243, 168730, 84365, 253096, 126548, 63274, 31637, 94912, 47456, 23728, 11864, 5932, 2966, 1483, 4450, 2225, 6676, 3338, 1669, 5008, 2504, 1252, 626, 313, 940, 470, 235, 706, 353, 1060, 530, 265, 796, 398, 199, 598, 299, 898, 449, 1348, 674, 337, 1012, 506, 253, 760, 380, 190, 95, 286, 143, 430, 215, 646, 323, 970, 485, 1456, 728, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, done!
I think that explains pretty well what the code does, which bring us to the second item on Bjoern's list: which mathematician made a conjecture about this algorithm? Some googling around turned up that it was Collatz, who said: This process will eventually reach the number 1, regardless of which positive integer is chosen initially.
This looks like an illustration of the halting problem, ie, is it possible to determine if this loop will ever terminate for all possible inputs? Avi already noticed that it's not easy to tell by looking at it. More googling turns up that there is a $500 prize available if you can solve the Collatz conjecture.
|
|
Back to top
|
|
|
Bjørn
|
|
Registered Member #27
Joined: Fri Feb 03 2006, 02:20AM
Location: Hyperborea
Posts: 2058
|
That is 100% correct on both part 2 and 3. I came over this algorithm ages ago before the internet and I tried to solve the problem before I knew that it was a real problem that people had been struggling with since 1937.
I tried all numbers up to 2^32 on an 8 MHz computer without much luck and even ran it on a Transputer trying out a few billion really large numbers before I gave up the brute force method. I got so far that I was sure it would be interesting to do it with complex numbers to make a 2D map before I discovered that it was an old problem and that hundreds of really clever people have tried and failed to solve before me.
It illustrates the halting problem very well, if the brightest minds have spent 70 years trying to find out if a 4 instruction long program is faulty or not, what is the chance of proving the correctness of a real program? (A Turing machine is said to be faulty if it enters an endless loop)
|
|
Back to top
|
|
Moderator(s): Chris Russell, Noelle, Alex, Tesladownunder, Dave Marshall, Dave Billington, Bjørn, Steve Conner, Wolfram, Kizmo, Mads Barnkob
|
|
Powered by e107 Forum System
|
|
