Asking to write a program for a random access machine (as opposed to, say, a stack machine) is like asking to translate a text to a Romance language (one of Spanish, Portuguese, French, Italian and Romanian, as opposed to, say, many variants of Chinese). It narrows down the language, but not enough to actually do something about it.
procedure factorial(n)
if n=0
return 1
return n * factorial(n-1)
We need a model for a RAM machine to see if we can encode this algorithm.
We could use for instance the Cook and Reckhow (1973) RAM machine, which defines:
LOAD ( C, rd ) ; C → rd, C is any integer
Example: LOAD ( 0, 5 ) will clear register 5.
ADD ( rs1, rs2, rd ) ; [rs1] + [rs2] → rd, the registers can be the same or different;
Example: ADD ( A, A, A ) will double the contents of register A.
SUB ( rs1, rs2, rd ) ; [rs1] - [rs2] → rd, the registers can be the same or different:
Example: SUB ( 3, 3, 3 ) will clear register 3.
COPY ( i, rp, d, rd ) ; [[rp] ] → rd, Indirectly copy the contents of the source-register pointed to by pointer-register rp into the destination register.
COPY ( d, rs, i, rp ) ; [rs] → [rp]. Copy the contents of source register rs into the destination-register pointed to by the pointer-register rp.
JNZ ( r, Iz ) ; Conditional jump if [r] is positive; i.e. IF [r] > 0 THEN jump to instruction z else continue in sequence (Cook and Reckhow call this: "TRAnsfer control to line m if Xj > 0")
READ ( rd ) ; copy "the input" into destination register rd
PRINT ( rs ) ; copy the contents of source register rs to "the output."
How could you encode the algorithm in such a model?
Or do you have a different model that you're supposed to use? (Wondering)
Or do you have a different model that you're supposed to use? (Wondering)
I have to use the RAM machine, which defines the following:
LOAD a ; c(0) ← v(a), c(i) is the integer stored in register i (the contents of register i), v(a) is the value of operand a
(v(=i)=i, v(i)=c(i), v(*i)=c(c(i)) )
STORE i ; c(i) ← c(0)
STORE *i ; c(c(i)) ←c(0)
ADD a ; c(0) ← c(0)+v(a)
SUB a ; c(0) ← c(0)-v(a)
MULT a ; c(0) ← c(0) × v(a)
DIV a ; c(0) ← ⌊c(0)/v(a)⌋
READ i ; c(i) ← current input symbol
READ *i ; c(c(i)) ← current input symbol. The input tape head moves one square right in either case.
WRITE a ; v(a) is printed on the square of the output tape currently under the output tape head. Then the tape head is moved one square right.
JUMP b ; The location counter is set to the instruction labeled b.
JGTZ b ; The location counter is set to the instruction labeled b if c(0)>0; otherwise, the location counter is set to the next instruction.
JZERO b ; The location counter is set to the instruction labeled b if c(0)=0; otherwise, the location counter is set to the next instruction.
HALT ; Execution ceases.
I like Serena said:
The algorithm for a factorial is:
Code:
procedure factorial(n)
if n=0
return 1
return n * factorial(n-1)
How could you encode the algorithm in such a model?
Is it maybe as followed?? (Wondering)
Code:
READ n
LOAD n
JGTZ proc
WRITE =1
proc: LOAD n
MULT n-1
HALT
I have to use the RAM machine, which defines the following:
LOAD a ; c(0) ← v(a), c(i) is the integer stored in register i (the contents of register i), v(a) is the value of operand a
(v(=i)=i, v(i)=c(i), v(*i)=c(c(i)) )
STORE i ; c(i) ← c(0)
STORE *i ; c(c(i)) ←c(0)
ADD a ; c(0) ← c(0)+v(a)
SUB a ; c(0) ← c(0)-v(a)
MULT a ; c(0) ← c(0) × v(a)
DIV a ; c(0) ← ⌊c(0)/v(a)⌋
READ i ; c(i) ← current input symbol
READ *i ; c(c(i)) ← current input symbol. The input tape head moves one square right in either case.
WRITE a ; v(a) is printed on the square of the output tape currently under the output tape head. Then the tape head is moved one square right.
JUMP b ; The location counter is set to the instruction labeled b.
JGTZ b ; The location counter is set to the instruction labeled b if c(0)>0; otherwise, the location counter is set to the next instruction.
JZERO b ; The location counter is set to the instruction labeled b if c(0)=0; otherwise, the location counter is set to the next instruction.
HALT ; Execution ceases.
Aha! (Happy)
Is it maybe as followed?? (Wondering)
Code:
READ n
LOAD n
JGTZ proc
WRITE =1
proc: LOAD n
MULT n-1
HALT
Let's start with what [m]READ n[/m] is supposed to do.
Apparently, it will read an input symbol and assign it to register n.
But... $n$ is not number, so which register would that be?
So I think we should choose a register to hold $n$ - say register 1.
Then we could use [m]READ 1[/m] to read the number n from input, and store it in register 1.As I understand it, [m]WRITE =1[/m] will print the number 1 on the output.
But that does not seem to be very useful. (Shake)
I suggest to use register 2 to hold the result of the factorial calculation.
In that case we should use [m]WRITE 2[/m] to print the number in register 2.The instruction [m]MULT n-1[/m] would not be allowed.
Instead I think it should be [m]MULT 1[/m], which would multiply register 0 with register 1, and store the result in register 0. (Nerd)
Let's start with what [m]READ n[/m] is supposed to do.
Apparently, it will read an input symbol and assign it to register n.
But... $n$ is not number, so which register would that be?
So I think we should choose a register to hold $n$ - say register 1.
Then we could use [m]READ 1[/m] to read the number n from input, and store it in register 1.As I understand it, [m]WRITE =1[/m] will print the number 1 on the output.
But that does not seem to be very useful. (Shake)
I suggest to use register 2 to hold the result of the factorial calculation.
In that case we should use [m]WRITE 2[/m] to print the number in register 2.The instruction [m]MULT n-1[/m] would not be allowed.
Instead I think it should be [m]MULT 1[/m], which would multiple register 0 with register 1, and store the result in register 0. (Nerd)
Read n from input
result = 1
while n > 0
result = result * n
n = n - 1
Write result to output
And I propose to keep track of $n$ in register 1, and to track $result$ in register 2.
When needed, one of these at a time will need to be loaded into register 0, and afterwards stored back again.
Read n from input
result = 1
while n > 0
result = result * n
n = n - 1
Write result to output
And I propose to keep track of $n$ in register 1, and to track $result$ in register 2.
When needed, one of these at a time will need to be loaded into register 0, and afterwards stored back again.
How does that sound? (Wondering)
I tried it again...
Code:
1. READ 1
2. LOAD =1
3. STORE 2
4.while: LOAD 1
5. JZERO endwhile
6. LOAD 2
7. MULT 1
8. STORE 2
9. LOAD 1
10. SUB =1
11. STORE 1
12.endwhile: WRITE 2
13. HALT
1.: Read n from input
2. & 3. : result=1
6. & 7. & 8. : result=result*n
9. & 10. & 11. : n=n-1Is it better now?? (Wondering)
At the lines 1-3, there is one instruction per line, so $3$.
At the lines 13-14, there is one instruction per line, so $2$.
A the line 5, there is one instruction.
At the lines 4, 6-12, there is a while loop. Each time when this loop is executed, there is one instruction per line, so $8$ instructions. The while loop is executed $n$ times, or not?? (Wondering)
Therefore, we have that the total number of instructions is:
$$3+2+1+8n=8n+6=O(n)$$
At the lines 1-3, there is one instruction per line, so $3$.
At the lines 13-14, there is one instruction per line, so $2$.
A the line 5, there is one instruction.
At the lines 4, 6-12, there is a while loop. Each time when this loop is executed, there is one instruction per line, so $8$ instructions. The while loop is executed $n$ times, or not?? (Wondering)
Therefore, we have that the total number of instructions is:
$$3+2+1+8n=8n+6=O(n)$$
Is this correct?? (Wondering)
Isn't line 5 also executed in every iteration? (Wondering)
How many instructions are executed if $n=0$? (Wondering)
There are a couple of instructions, that are part of the loop, that are executed whether the loop is executed or not. (Wasntme)
Do you mean the instructions of the lines 4 and 5?? (Wondering)
So is it as followed?? (Wondering)At the lines 1-3, there is one instruction per line, so $3$.
At the lines 13-14, there is one instruction per line, so $2$.
At the lines 4-5, there is one instruction per line, so $2$
At the lines 4-12, there is a while loop. Each time when this loop is executed, there is one instruction per line, so $9$ instructions. The while loop is executed $n$ times.
Therefore, we have that the total number of instructions is:
$$3+2+2+9n=9n+7=O(n)$$
Do you mean the instructions of the lines 4 and 5?? (Wondering)
So is it as followed?? (Wondering)At the lines 1-3, there is one instruction per line, so $3$.
At the lines 13-14, there is one instruction per line, so $2$.
At the lines 4-5, there is one instruction per line, so $2$
At the lines 4-12, there is a while loop. Each time when this loop is executed, there is one instruction per line, so $9$ instructions. The while loop is executed $n$ times.
Therefore, we have that the total number of instructions is:
$$3+2+2+9n=9n+7=O(n)$$
I have to analyze also the time complexity under the logarithmic cost.
Let $l(i)$ be the following logarithmic function on the integers:
$l(i)=\left\{\begin{matrix}
\lfloor \log \lfloor i \rfloor \rfloor +1, i \neq 0\\
1, i=0
\end{matrix}\right.$The logarithmic cost $t(a)$ of an operand $a$ is:
6. LOAD 2 : t(2)=l(2)=2
7. MULT 1 : l(c(0))+t(1)=l(c(0))+1
8. STORE 2 : l(c(0))+l(2)=l(c(0))+2
9. LOAD 1 : t(1)=l(1)+l(c(1))=l(c(1))
10. SUB =1 : l(c(0))+t(=1)=l(c(0))+l(1)=l(c(0))+1
11. STORE 1 : l(c(0))+l(1)=l(c(0))+1
12. JUMP while : 1
13.endwhile: WRITE 2 : t(2)=l(2)=2
14. HALT : 1So, do we have to add the cost of the lines 1-5, 14 and the cost of the body of the while multiplied by the times the loop is executed?? (Wondering)
I have to analyze also the time complexity under the logarithmic cost.
Let $l(i)$ be the following logarithmic function on the integers:
$l(i)=\left\{\begin{matrix}
\lfloor \log \lfloor i \rfloor \rfloor +1, i \neq 0\\
1, i=0
\end{matrix}\right.$The logarithmic cost $t(a)$ of an operand $a$ is:
6. LOAD 2 : t(2)=l(2)=2
7. MULT 1 : l(c(0))+t(1)=l(c(0))+1
8. STORE 2 : l(c(0))+l(2)=l(c(0))+2
9. LOAD 1 : t(1)=l(1)+l(c(1))=l(c(1))
10. SUB =1 : l(c(0))+t(=1)=l(c(0))+l(1)=l(c(0))+1
11. STORE 1 : l(c(0))+l(1)=l(c(0))+1
12. JUMP while : 1
13.endwhile: WRITE 2 : t(2)=l(2)=2
14. HALT : 1So, do we have to add the cost of the lines 1-5, 14 and the cost of the body of the while multiplied by the times the loop is executed?? (Wondering)
It looks about right. (Smile)
I guess it could be expanded a little more, since now you typically refer to c(0), which can be replaced by what it actually is.
For instance, in line 3 you write l(c(0))+2.
Since you know that c(0)=1, we can expand and simplify this to l(1)+2=3. (Nerd)
I guess it could be expanded a little more, since now you typically refer to c(0), which can be replaced by what it actually is.
For instance, in line 3 you write l(c(0))+2.
Since you know that c(0)=1, we can expand and simplify this to l(1)+2=3. (Nerd)
