Converting Recursion into Loops for Computing n^n

[mathmari]

Hey!

Write a RAM program of uniform-cost time complexity $O(\log n)$ to compute $n^n$.Prove that your program is correct.

(Under the uniform cost criterion each RAM instruction requires one unit of time.)

So that the time complexity is $O(\log n)$ the size of the problem should get divided by $2$ each time, right?? (Wondering)

I have done the following:

Read n from input
result=n
i=⌊n/2⌋
j=⌊n/2⌋
while i>0
    result=result*result
    i=⌊i/2⌋
if j+j-n=0
    Write result to output
else 
    result=result*n
    Write result to output

Is this correct?? (Wondering)

The instructions of the RAM machine are the following:

Spoiler

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 RAM program would be as followed:

READ 1
LOAD =n
STORE 2
LOAD =n
DIV =2
STORE 3
LOAD =n
DIV =2
STORE 4
while: LOAD 3
       JZERO endwhile
LOAD 2
MULT 2
STORE 2
LOAD 3
DIV =2
STORE 3
JUMP while
endwhile: LOAD 4
          ADD 4
          SUB =n
          JZERO res
LOAD 2
MULT =n
STORE 2
WRITE 2
res: WRITE 2
HALT

Is this correct?? (Wondering)

 

[I like Serena]

Write a RAM program of uniform-cost time complexity $O(\log n)$ to compute $n^n$.Prove that your program is correct.
I have done the following:

Read n from input
result=n
i=⌊n/2⌋
j=⌊n/2⌋
while i>0
    result=result*result
    i=⌊i/2⌋
if j+j-n=0
    Write result to output
else 
    result=result*n
    Write result to output

Hey! (Smile)

Let's see... suppose we pick n=6
\begin{array}{|c|c|c|}\hline
result & i & j \\
\hline
6 & 2 & 2 \\
6^2 & 1 & \\
6^3 & 0 & \\
6^3\cdot 6 & & \\
\hline\end{array}

Hmm... isn't that $6^4$ instead of $6^6$? (Thinking)

The RAM program would be as followed:
Is this correct?? (Wondering)

What does [m]LOAD =n[/m] do? (Wondering)Oh, and can you specify the list of instructions and what they do?
Perhaps in the opening post? (Thinking)

 

[mathmari]

The instructions of the RAM machine are 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.
​

P.S. I can't edit my first post, that's why I write the instructions here.

 

[I like Serena]

That's okay. (Wink)
I have added the instruction set for you to your opening post.
And I've put them between spoiler tags so they don't take up so much space. (Bandit)

 

[mathmari]

That's okay. (Wink)
I have added the instruction set for you to your opening post.
And I've put them between spoiler tags so they don't take up so much space. (Bandit)

Nice! (Yes)

 

[mathmari]

Let's see... suppose we pick n=6
\begin{array}{|c|c|c|}\hline
result & i & j \\
\hline
6 & 2 & 2 \\
6^2 & 1 & \\
6^3 & 0 & \\
6^3\cdot 6 & & \\
\hline\end{array}

Hmm... isn't that $6^4$ instead of $6^6$? (Thinking)

So, is it wrong to divide the step by $2$ ?? (Wondering)

 

[I like Serena]

So, is it wrong to divide the step by $2$ ?? (Wondering)

Yes, I think so.
I think we should start with a step of 1 and double it.
And I also think we should track intermediate results.
We will need a smarter algorithm! (Thinking)

 

[I like Serena]

Perhaps we should take a look at an algorithm to implement $n^n$ in $O(\log n)$ time.

procedure pow(n, k)
  if k=0
    return 1
  result = pow(n, ⌊k/2⌋)
  result = result * result
  if k odd
    result = result * n
  return result

How does that look? (Wondering)

 

[mathmari]

How could we compute pow(n,floor(k/2)) when there is no instruction to calculate the power of a number?? (Wondering)

Could we maybe compute it as followed?? (Wondering)

Read n from input
i=1
result=n*n
Result=n*n
while i<floor(n/2)
       Result=Result*result
       i=i+1
if n-2*i=0
       Write Result
else
       Result=Result*n
       Write Result

 

[I like Serena]

How could we compute pow(n,floor(k/2)) when there is no instruction to calculate the power of a number?? (Wondering)

So we have to write it ourselves using multiplications and divisions.
That's what the algorithm I gave does. (Dull)

Could we maybe compute it as followed?? (Wondering)

Read n from input
i=1
result=n*n
Result=n*n
while i<floor(n/2)
       Result=Result*result
       i=i+1
if n-2*i=0
       Write Result
else
       Result=Result*n
       Write Result

What would the intermediate and final results of $6^6$ be? (Wondering)

 

[mathmari]

So we have to write it ourselves using multiplications and divisions.
That's what the algorithm I gave does. (Dull)

I am confused with the algorithm pow(n,k) because it is a recursive function. Do we have to use a while loop?? Or can we write a recursive function in a RAM program??

What would the intermediate and final results of $6^6$ be? (Wondering)

Isn't it as followed?? (Wondering)

Read 6
i=1
result=6*6
Result=6*6
i<3 $\checkmark$
Result=6*6*6*6
i=2
i<3 $\checkmark$
Result=6*6*6*6*6*6
i=3
i<3 $\times$
6-2*3=0
Write 6*6*6*6*6*6

 

[I like Serena]

I am confused with the algorithm pow(n,k) because it is a recursive function. Do we have to use a while loop?? Or can we write a recursive function in a RAM program??

Yeah.
So the recursive function has to be "unrolled" somehow. (Worried)
The typical approaches are to either convert it into a while loop, or implement an engine that can handle recursive functions.

I suggest converting it into a while loop.
It still requires you to build up intermediate results in an array.
And, when you have them, work back to find the proper result. (Sweating)

Isn't it as followed?? (Wondering)

Read 6
i=1
result=6*6
Result=6*6
i<3 $\checkmark$
Result=6*6*6*6
i=2
i<3 $\checkmark$
Result=6*6*6*6*6*6
i=3
i<3 $\times$
6-2*3=0
Write 6*6*6*6*6*6

Ah yes...
How about $n=1$? (Wondering)

 

[mathmari]

procedure pow(n, k)
  if k=0
    return 1
  result = pow(n, ⌊k/2⌋)
  result = result * result
  if k odd
    result = result * n
  return result

I suggest converting it into a while loop.
It still requires you to build up intermediate results in an array.
And, when you have them, work back to find the proper result. (Sweating)

I tried to convert the recursive function pow(n,n) into a while loop... (Wait)

But I'm not sure if it correct... (Worried)

Read n from input
result=1
i=⌊n/2⌋
while i>0
     result=result*result
     if i odd
        result=result*n
     i=⌊i/2⌋
result=result*result
Write result

Ah yes...
How about $n=1$? (Wondering)

We have to take seperately the case $n=1$, or not?? (Wondering)

Read n from input
if n=1 Write 1
i=1
result=n*n
Result=n*n
while i<floor(n/2)
       Result=Result*result
       i=i+1
if n-2*i=0
       Write Result
else
       Result=Result*n
       Write Result

 

[I like Serena]

I tried to convert the recursive function pow(n,n) into a while loop... (Wait)

Read n from input
if n=1 Write 1
i=1
result=n*n
Result=n*n
while i<floor(n/2)
       Result=Result*result
       i=i+1
if n-2*i=0
       Write Result
else
       Result=Result*n
       Write Result

It looks as if this algorithm will indeed give the right results.

However, you now have a while-loop that is executed floor(n/2) times.
Isn't that O(n)? (Worried)Perhaps we should take a look at the algorithm I gave earlier.

procedure pow(n, k)
  if k=0
    return 1
  result = pow(n, ⌊k/2⌋)
  result = result * result
  if k odd
    result = result * n
  return result

Let's see what happens we apply the algorithm to $n=6$.
I will append the number of the recursion level, starting with 0.

pow(6,6)
  result0 = pow(6,3)
    result1 = pow(6,1)
      result2 = pow(6,0)
      result2 = 1
      result2 = result2 * result2 = 1
      result2 = result2 * n = 6
    result1 = 6
    result1 = result2 * result2 = 6 * 6
    result1 = result1 * n = 6 * 6 * 6
  result0 = 6 * 6 * 6
  result0 = result0 * result0 = 6 * 6 * 6 * 6 * 6 * 6

What we see, is that we recursively go down, first with k=6, then k=3, k=1, and finally k=0, and we effectively "remember" where we are.

Then we come back up and calculate $6^0, 6^1, 6^3, 6^6$.

Now suppose we create an array a[] that tracks where we are.
We will fill it with a[0] = 6, a[1] = 3, a[2] = 1, a[3] = 0.
Then we track the result, starting with $result=1$, and we work our way back from the end of the array.
Since a[2]=1 is odd, we multiply 1*1 by an extra 6 to get 6.
Since a[1]=3 is odd, we multiply 6*6 by an extra 6 to get $6^3$.
Since a[0]=6 is even, we finally get $6^3 \cdot 6^3 = 6^6$.

How would that look with a while-loop (or rather, 2 while-loops in succession)? (Wondering)

 

[mathmari]

It looks as if this algorithm will indeed give the right results.

However, you now have a while-loop that is executed floor(n/2) times.
Isn't that O(n)? (Worried)

Yes... (Sweating)

Perhaps we should take a look at the algorithm I gave earlier.

procedure pow(n, k)
  if k=0
    return 1
  result = pow(n, ⌊k/2⌋)
  result = result * result
  if k odd
    result = result * n
  return result

Let's see what happens we apply the algorithm to $n=6$.
I will append the number of the recursion level, starting with 0.

pow(6,6)
  result0 = pow(6,3)
    result1 = pow(6,1)
      result2 = pow(6,0)
      result2 = 1
      result2 = result2 * result2 = 1
      result2 = result2 * n = 6
    result1 = 6
    result1 = result2 * result2 = 6 * 6
    result1 = result1 * n = 6 * 6 * 6
  result0 = 6 * 6 * 6
  result0 = result0 * result0 = 6 * 6 * 6 * 6 * 6 * 6

What we see, is that we recursively go down, first with k=6, then k=3, k=1, and finally k=0, and we effectively "remember" where we are.

Then we come back up and calculate $6^0, 6^1, 6^3, 6^6$.

Now suppose we create an array a[] that tracks where we are.
We will fill it with a[0] = 6, a[1] = 3, a[2] = 1, a[3] = 0.
Then we track the result, starting with $result=1$, and we work our way back from the end of the array.
Since a[2]=1 is odd, we multiply 1*1 by an extra 6 to get 6.
Since a[1]=3 is odd, we multiply 6*6 by an extra 6 to get $6^3$.
Since a[0]=6 is even, we finally get $6^3 \cdot 6^3 = 6^6$.

How would that look with a while-loop (or rather, 2 while-loops in succession)? (Wondering)

I don't know how the recursion could be converted into two while-loops... (Wondering)

I thought that it could be for example as followed:

i=n;
result=1;
while i>0
   if i even then 
      result=result*result
   else
      result=result*result*n;
   i=⌊i/2⌋;
if n even 
   result=result*result;
else 
   result=result*result*n;

But this works only for $n=6$.

I got stuck right now... (Doh)

 

[I like Serena]

Yes... (Sweating)

I don't know how the recursion could be converted into two while-loops... (Wondering)

I thought that it could be for example as followed:

i=n;
result=1;
while i>0
   if i even then 
      result=result*result
   else
      result=result*result*n;
   i=⌊i/2⌋;
if n even 
   result=result*result;
else 
   result=result*result*n;

But this works only for $n=6$.

I got stuck right now... (Doh)

I would introduce an array $a[]$ to hold the powers of $n$.
And then I would do something like:

i=1
a[1] = n
while 2 * i <= n
  a[2 * i] = a[i] * a[i]
  i = 2 * i

remainder = n - i
result = a[i]
while remainder > 0
  if i <= remainder
    result = result * a[i]
    remainder = remainder - i
  i = i / 2

(Thinking)