Program to compute the factorial of n

[mathmari]

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)

 

[chisigma]

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)

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$

 

[Evgeny.Makarov]

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.

 

[I like Serena]

Hey! (Blush)

The algorithm for a factorial is:

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)

 

[mathmari]

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.
​

The algorithm for a factorial is:

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)

READ n
LOAD n
JGTZ proc
WRITE =1
proc: LOAD n 
      MULT n-1
HALT

 

[I like Serena]

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)

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)

 

[mathmari]

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)

Do you mean the following?? (Wondering)

READ 1
JGTZ proc
WRITE 2
proc: MULT 1

 

[I like Serena]

Do you mean the following?? (Wondering)

READ 1
JGTZ proc
WRITE 2
proc: MULT 1

Nooooooo. (Doh)

Back to the algorithm.
I propose to implement:

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)

 

[mathmari]

Nooooooo. (Doh)

Back to the algorithm.
I propose to implement:

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...

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)

 

[I like Serena]

I tried it again...

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)

Much better! (Happy)

Now suppose we try to calculate the factorial of n=4.

Then we get:
\begin{array}{|c|c|c|}\hline
c(0) & c(1) & c(2) \\
\hline
& \text{READ 1}\to4 & 1 \\
4 &4 & 4 \\
& 3 & \text{WRITE 2}\to 4 \\
\hline
\end{array}

But... but... the factorial of 4 is not 4. (Worried)
What went wrong? (Thinking)

 

[mathmari]

Now suppose we try to calculate the factorial of n=4.

Then we get:
\begin{array}{|c|c|c|}\hline
c(0) & c(1) & c(2) \\
\hline
& \text{READ 1}\to4 & 1 \\
4 &4 & 4 \\
& 3 & \text{WRITE 2}\to 4 \\
\hline
\end{array}

READ 1 : c(1) ← 4

\begin{array}{|c|c|c|}\hline
c(0) & c(1) & c(2) \\
\hline
& 4 & \\
\hline
\end{array}

LOAD =1 : c(0) ← 1
STORE 2 : c(2) ← c(0)

These instructions mean that c(2) ← 1 , right?? (Wondering)

\begin{array}{|c|c|c|}\hline
c(0) & c(1) & c(2) \\
\hline
& 4 & \\
& & 1 \\
\hline
\end{array}

while:
LOAD 1 : c(0) ← v(1)=c(1)=4
JZERO endwhile

\begin{array}{|c|c|c|}\hline
c(0) & c(1) & c(2) \\
\hline
& 4 & \\
& & 1 \\
4& & \\
\hline
\end{array}

LOAD 2 : c(0) ← v(2)=c(2)=1
MULT 1: c(0) ← c(0) x v(1)=1 x c(1)=1 x 4=4
STORE 2 : c(2) ← c(0)

So, we have c(2) ← 4

\begin{array}{|c|c|c|}\hline
c(0) & c(1) & c(2) \\
\hline
& 4 & \\
& & 1 \\
4& & \\
& & 4 \\
\hline
\end{array}

LOAD 1 : c(0) ← v(1)=c(1)=4
SUB =1 : c(0) ←c(0)-v(=1)=4-1=3
STORE 1 : c(1) ← c(0)

So, we have that c(1) ← 3

\begin{array}{|c|c|c|}\hline
c(0) & c(1) & c(2) \\
\hline
& 4 & \\
& & 1 \\
4& & \\
& & 4 \\
& 3 & \\
\hline
\end{array}

WRITE 2 : v(2)=c(2)=4

\begin{array}{|c|c|c|}\hline
c(0) & c(1) & c(2) \\
\hline
& 4 & \\
& & 1 \\
4& & \\
& & 4 \\
& 3 & \\
& & 4 \\
\hline
\end{array}

HALTHow did you get the second $4$ in c(1) ?? (Wondering)

But... but... the factorial of 4 is not 4. (Worried)
What went wrong? (Thinking)

The while loop is executed only once, right?? (Wondering)

 

[I like Serena]

READ 1 : c(1) ← 4

\begin{array}{|c|c|c|}\hline
c(0) & c(1) & c(2) \\
\hline
& 4 & \\
\hline
\end{array}

LOAD =1 : c(0) ← 1
STORE 2 : c(2) ← c(0)

These instructions mean that c(2) ← 1 , right?? (Wondering)

\begin{array}{|c|c|c|}\hline
c(0) & c(1) & c(2) \\
\hline
& 4 & \\
& & 1 \\
\hline
\end{array}

while:
LOAD 1 : c(0) ← v(1)=c(1)=4
JZERO endwhile

\begin{array}{|c|c|c|}\hline
c(0) & c(1) & c(2) \\
\hline
& 4 & \\
& & 1 \\
4& & \\
\hline
\end{array}

LOAD 2 : c(0) ← v(2)=c(2)=1
MULT 1: c(0) ← c(0) x v(1)=1 x c(1)=1 x 4=4
STORE 2 : c(2) ← c(0)

So, we have c(2) ← 4

\begin{array}{|c|c|c|}\hline
c(0) & c(1) & c(2) \\
\hline
& 4 & \\
& & 1 \\
4& & \\
& & 4 \\
\hline
\end{array}

LOAD 1 : c(0) ← v(1)=c(1)=4
SUB =1 : c(0) ←c(0)-v(=1)=4-1=3
STORE 1 : c(1) ← c(0)

So, we have that c(1) ← 3

\begin{array}{|c|c|c|}\hline
c(0) & c(1) & c(2) \\
\hline
& 4 & \\
& & 1 \\
4& & \\
& & 4 \\
& 3 & \\
\hline
\end{array}

WRITE 2 : v(2)=c(2)=4

\begin{array}{|c|c|c|}\hline
c(0) & c(1) & c(2) \\
\hline
& 4 & \\
& & 1 \\
4& & \\
& & 4 \\
& 3 & \\
& & 4 \\
\hline
\end{array}

HALT

Good! (Happy)

How did you get the second $4$ in c(1) ?? (Wondering)

I was just repeating the value c(1) had.
To be fair, c(2) is also not getting another $4$ when $\text{WRITE 2}$ is executed. (Wasntme)

The while loop is executed only once, right?? (Wondering)

Exactly! (Nod)
I think we need something extra to ensure it gets executed more than once... (Thinking)

 

[mathmari]

Good! (Happy)

(Sun)

I was just repeating the value c(1) had.
To be fair, c(2) is also not getting another $4$ when $\text{WRITE 2}$ is executed. (Wasntme)

I see... (Smile)

Exactly! (Nod)
I think we need something extra to ensure it gets executed more than once... (Thinking)

Is it maybe as followed?? (Wondering)

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. JUMP while

13.endwhile: WRITE 2

14. HALT

 

[I like Serena]

Is it maybe as followed?? (Wondering)

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. JUMP while

13.endwhile: WRITE 2

14. HALT

Yep. (Cool)

 

[mathmari]

Yep. (Cool)

Great! (Happy)

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)

 

[I like Serena]

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)

 

[mathmari]

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)$$

Is this correct?? (Wondering)

 

[I like Serena]

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)$$

Is this correct?? (Wondering)

Isn't line 5 also executed in every iteration? (Wondering)

How many instructions are executed if $n=0$? (Wondering)

 

[mathmari]

Isn't line 5 also executed in every iteration? (Wondering)

So, is it $9n+5$ ?? (Wondering)

How many instructions are executed if $n=0$? (Wondering)

$7$ instructions are executed in that case, right?? (Wondering)

 

[I like Serena]

So, is it $9n+5$ ?? (Wondering)
$7$ instructions are executed in that case, right?? (Wondering)

Hmm... isn't $9\cdot 0 +5 \ne 7$? (Worried)

 

[mathmari]

Hmm... isn't $9\cdot 0 +5 \ne 7$? (Worried)

(Doh)

So, which of them have I counted wrong?? (Wondering)

 

[I like Serena]

(Doh)

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)

 

[mathmari]

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)$$

 

[I like Serena]

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)

 

[mathmari]

Yes! (Party)

Nice! (Music)

I have to analyze also the time complexity under the logarithmic cost.

Spoiler

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:

$\text{ Operand }a \ \ \ \ \ \text{ Cost } t(a)$
$ =i \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ l(i)$
$ i \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ l(i)+l(c(i))$
$ *i \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ l(i)+l(c(i))+l(c(c(i))$

The logarithmic cost of RAM instructions:

LOAD a : t(a)

STORE i : l(c(0))+l(i)
STORE *i : l(c(0))+l(i)+l(c(i))

ADD a : l(c(0))+t(a)

SUB a : l(c(0))+t(a)

MULT a : l(c(0))+t(a)

DIV a : l(c(0))+t(a)

READ i : l(input)+l(i)
READ *i : l(input)+l(i)+l(c(i))

WRITE a : t(a)

JUMP b : 1

JGTZ b : l(c(0))

JZERO : l(c(0))

HALT : 1

So, is it as followed?? (Wondering)

1. READ 1 : l(input)+l(1)=l(input)+1

2. LOAD =1 : t(=1)=l(1)=1
3. STORE 2 : l(c(0))+l(2)=l(c(0))+2

4.while: LOAD 1 : t(1)=l(1)+l(c(1))=l(c(1))
5. JZERO endwhile : l(c(0))

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 like Serena]

Nice! (Music)

I have to analyze also the time complexity under the logarithmic cost.

Spoiler

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:

$\text{ Operand }a \ \ \ \ \ \text{ Cost } t(a)$
$ =i \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ l(i)$
$ i \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ l(i)+l(c(i))$
$ *i \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ l(i)+l(c(i))+l(c(c(i))$

The logarithmic cost of RAM instructions:

LOAD a : t(a)

STORE i : l(c(0))+l(i)
STORE *i : l(c(0))+l(i)+l(c(i))

ADD a : l(c(0))+t(a)

SUB a : l(c(0))+t(a)

MULT a : l(c(0))+t(a)

DIV a : l(c(0))+t(a)

READ i : l(input)+l(i)
READ *i : l(input)+l(i)+l(c(i))

WRITE a : t(a)

JUMP b : 1

JGTZ b : l(c(0))

JZERO : l(c(0))

HALT : 1

So, is it as followed?? (Wondering)

1. READ 1 : l(input)+l(1)=l(input)+1

2. LOAD =1 : t(=1)=l(1)=1
3. STORE 2 : l(c(0))+l(2)=l(c(0))+2

4.while: LOAD 1 : t(1)=l(1)+l(c(1))=l(c(1))
5. JZERO endwhile : l(c(0))

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)

 

[mathmari]

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)

So, is it as followed??

1. READ 1 : c(1) ← n=input $\Rightarrow$ l(input)+l(1)=l(input)+1=l(n)+1=⌊log(⌊n⌋)⌋+1+1=⌊log(⌊n⌋)⌋+2

2. LOAD =1 : c(0) ← 1 $\Rightarrow$ t(=1)=l(1)=1

3. STORE 2 : c(2) ← c(0)=1 $\Rightarrow$ l(c(0))+l(2)=l(c(0))+2=l(1)+2=1+2=3

4.while: LOAD 1 : c(0) ← c(1)=input=n $\Rightarrow$ t(1)=l(1)+l(c(1))=l(c(1))=l(n)=⌊log(⌊n⌋)⌋+1

5. JZERO endwhile : l(c(0))=l(n)=⌊log(⌊n⌋)⌋+1

6. LOAD 2 : c(0) ← c(2)=1 $\Rightarrow$ t(2)=l(2)=2

7. MULT 1 : c(0) ← c(0) x c(1) = c(2) x c(1) = 1 x n = n $\Rightarrow$ l(c(0))+t(1)=l(c(0))+1=l(n)+1=⌊log(⌊n⌋)⌋+1+1=⌊log(⌊n⌋)⌋+2

8. STORE 2 : c(2) ← c(0) = n $\Rightarrow$ l(c(0))+l(2)=l(c(0))+2=l(n)+2=⌊log(⌊n⌋)⌋+1+2=⌊log(⌊n⌋)⌋+3

9. LOAD 1 : c(0) ← c(1) = n $\Rightarrow$ t(1)=l(1)+l(c(1))=l(c(1))=l(n)=⌊log(⌊n⌋)⌋+1

10. SUB =1 : c(0) ← c(0) - 1 = n-1 $\Rightarrow$ l(c(0))+t(=1)=l(c(0))+l(1)=l(c(0))+1=l(n-1)+1=⌊log(⌊n-1⌋)⌋+1+1=⌊log(⌊n-1⌋)⌋+2

11. STORE 1 : c(1) ← c(0) = n-1 $\Rightarrow$ l(c(0))+l(1)=l(c(0))+1=l(n-1)+1=⌊log(⌊n-1⌋)⌋+1+1=⌊log(⌊n-1⌋)⌋+2

12. JUMP while : 1

13.endwhile: WRITE 2 : t(2)=l(2)=2

14. HALT : 1(Wondering)So, is the time complexity under the logarithmic cost the following??

⌊log(⌊n⌋)⌋+2+1+3+⌊log(⌊n⌋)⌋+1+⌊log(⌊n⌋)⌋+1+2+1+WHILE

where the time complexity of WHILE is the following:

n(⌊log(⌊n⌋)⌋+1+⌊log(⌊n⌋)⌋+1+2+⌊log(⌊n⌋)⌋+2+⌊log(⌊n⌋)⌋+3+⌊log(⌊n⌋)⌋+1+⌊log(⌊n-1⌋)⌋+2+⌊log(⌊n-1⌋)⌋+2+1)So, in total, the time complexity under the logarithmic cost is:
$$3\lfloor \log(\lfloor n \rfloor )\rfloor+11+n \left (5 \lfloor \log(\lfloor n \rfloor )\rfloor+2 \lfloor \log( \lfloor n-1 \rfloor ) \rfloor+15 \right ) \\ =5n \lfloor \log( \lfloor n \rfloor ) \rfloor +2n \lfloor \log( \lfloor n-1 \rfloor ) \rfloor +15n+3 \lfloor \log(\lfloor n \rfloor ) \rfloor +11 \\ =O(n \lfloor \log( \lfloor n \rfloor )\rfloor )$$

Is that correct?? (Wondering)

 

[I like Serena]

So, is it as followed??

1. READ 1 : c(1) ← n=input $\Rightarrow$ l(input)+l(1)=l(input)+1=l(n)+1=⌊log(⌊n⌋)⌋+1+1=⌊log(⌊n⌋)⌋+2

2. LOAD =1 : c(0) ← 1 $\Rightarrow$ t(=1)=l(1)=1

3. STORE 2 : c(2) ← c(0)=1 $\Rightarrow$ l(c(0))+l(2)=l(c(0))+2=l(1)+2=1+2=3

4.while: LOAD 1 : c(0) ← c(1)=input=n $\Rightarrow$ t(1)=l(1)+l(c(1))=l(c(1))=l(n)=⌊log(⌊n⌋)⌋+1

5. JZERO endwhile : l(c(0))=l(n)=⌊log(⌊n⌋)⌋+1

6. LOAD 2 : c(0) ← c(2)=1 $\Rightarrow$ t(2)=l(2)=2

7. MULT 1 : c(0) ← c(0) x c(1) = c(2) x c(1) = 1 x n = n $\Rightarrow$ l(c(0))+t(1)=l(c(0))+1=l(n)+1=⌊log(⌊n⌋)⌋+1+1=⌊log(⌊n⌋)⌋+2

8. STORE 2 : c(2) ← c(0) = n $\Rightarrow$ l(c(0))+l(2)=l(c(0))+2=l(n)+2=⌊log(⌊n⌋)⌋+1+2=⌊log(⌊n⌋)⌋+3

9. LOAD 1 : c(0) ← c(1) = n $\Rightarrow$ t(1)=l(1)+l(c(1))=l(c(1))=l(n)=⌊log(⌊n⌋)⌋+1

10. SUB =1 : c(0) ← c(0) - 1 = n-1 $\Rightarrow$ l(c(0))+t(=1)=l(c(0))+l(1)=l(c(0))+1=l(n-1)+1=⌊log(⌊n-1⌋)⌋+1+1=⌊log(⌊n-1⌋)⌋+2

11. STORE 1 : c(1) ← c(0) = n-1 $\Rightarrow$ l(c(0))+l(1)=l(c(0))+1=l(n-1)+1=⌊log(⌊n-1⌋)⌋+1+1=⌊log(⌊n-1⌋)⌋+2

12. JUMP while : 1

13.endwhile: WRITE 2 : t(2)=l(2)=2

14. HALT : 1(Wondering)So, is the time complexity under the logarithmic cost the following??

⌊log(⌊n⌋)⌋+2+1+3+⌊log(⌊n⌋)⌋+1+⌊log(⌊n⌋)⌋+1+2+1+WHILE

where the time complexity of WHILE is the following:

n(⌊log(⌊n⌋)⌋+1+⌊log(⌊n⌋)⌋+1+2+⌊log(⌊n⌋)⌋+2+⌊log(⌊n⌋)⌋+3+⌊log(⌊n⌋)⌋+1+⌊log(⌊n-1⌋)⌋+2+⌊log(⌊n-1⌋)⌋+2+1)So, in total, the time complexity under the logarithmic cost is:
$$3\lfloor \log(\lfloor n \rfloor )\rfloor+11+n \left (5 \lfloor \log(\lfloor n \rfloor )\rfloor+2 \lfloor \log( \lfloor n-1 \rfloor ) \rfloor+15 \right ) \\ =5n \lfloor \log( \lfloor n \rfloor ) \rfloor +2n \lfloor \log( \lfloor n-1 \rfloor ) \rfloor +15n+3 \lfloor \log(\lfloor n \rfloor ) \rfloor +11 \\ =O(n \lfloor \log( \lfloor n \rfloor )\rfloor )$$

Is that correct?? (Wondering)

Your approach looks right! (Smile)

Btw, I would leave out the floor symbols in the big-O order notation. (Nerd)

 

[mathmari]

Your approach looks right! (Smile)

Great! Thank you very much! (Handshake)

Btw, I would leave out the floor symbols in the big-O order notation. (Nerd)

Ok! (Nerd)