The discussion focuses on creating a RAM program to compute the factorial of a number n. Participants explore the necessary instructions for the RAM model, including reading input, performing arithmetic operations, and controlling program flow with jumps and conditionals. A proposed algorithm involves initializing a result variable, iterating while n is greater than zero, multiplying the result by n, and decrementing n until it reaches zero. There is a realization that the loop must be structured to ensure it executes multiple times for accurate factorial calculation. The conversation emphasizes refining the algorithm to correctly implement the factorial logic in the RAM programming context.
#1
mathmari
Gold Member
MHB
4,984
7
Hey!
I am asked to write a RAM (Random Access Machines) program to compute $n!$ given input $n$.
Could you give me some hints how I could do that?? (Wondering)
I am asked to write a RAM (Random Access Machines) program to compute $n!$ given input $n$.
Could you give me some hints how I could do that?? (Wondering)
What is the range [ie the maximum possible value...] od n?... and what is the number of digit of the numerical data of Your machine?...
Kind regards
$\chi$ $\sigma$
#3
Evgeny.Makarov
Gold Member
MHB
2,434
4
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)
#5
mathmari
Gold Member
MHB
4,984
7
I like Serena said:
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)
#7
mathmari
Gold Member
MHB
4,984
7
I like Serena said:
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.
How does that sound? (Wondering)
#9
mathmari
Gold Member
MHB
4,984
7
I like Serena said:
Nooooooo. (Doh)
Back to the algorithm.
I propose to implement:
Code:
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)
Under the uniform cost criterion each RAM instruction requires one unit of time.
So, to find the time complexity under the uniform cost do we just counter the instructions?? (Wondering)
That sounds right. (Smile)
#17
mathmari
Gold Member
MHB
4,984
7
I like Serena said:
That sounds right. (Smile)
So, is it as foilowed?? (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)
#19
mathmari
Gold Member
MHB
4,984
7
I like Serena said:
Isn't line 5 also executed in every iteration? (Wondering)
So, is it $9n+5$ ?? (Wondering)
I like Serena said:
How many instructions are executed if $n=0$? (Wondering)
$7$ instructions are executed in that case, right?? (Wondering)
So, which of them have I counted wrong?? (Wondering)
There are a couple of instructions, that are part of the loop, that are executed whether the loop is executed or not. (Wasntme)
#23
mathmari
Gold Member
MHB
4,984
7
I like Serena said:
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)$$
Yes! (Party)
#25
mathmari
Gold Member
MHB
4,984
7
I like Serena said:
Yes! (Party)
Nice! (Music)
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)
#27
mathmari
Gold Member
MHB
4,984
7
I like Serena said:
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)
