MHB Converting Recursion into Loops for Computing n^n

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Program Ram
AI Thread Summary
The discussion focuses on converting a recursive algorithm for computing n^n into a loop-based implementation with a time complexity of O(log n). Participants explore various approaches, debating the correctness of their implementations and the need for intermediate results. A key point is the challenge of handling odd and even values of n within the loop structure. Suggestions include using an array to track powers and employing two while loops to manage the calculations. Ultimately, the conversation emphasizes the necessity of refining the algorithm to ensure it meets the desired time complexity while accurately computing the result.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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:

Code: 
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:

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:

Code: 
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)
 
Last edited by a moderator:
Technology news on Phys.org
mathmari said:
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:
Code: 
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)
 
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.
 
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)
 
I like Serena said:
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)
 
I like Serena said:
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)
 
mathmari said:
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)
 
Perhaps we should take a look at an algorithm to implement $n^n$ in $O(\log n)$ time.
Code: 
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)
 
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)

Code: 
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
 
  • #10
mathmari said:
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)

Code: 
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)
 
  • #11
I like Serena said:
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??
I like Serena said:
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
 
  • #12
mathmari said:
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)
 
  • #13
I like Serena said:
Code: 
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 like Serena said:
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)

Code: 
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
I like Serena said:
Ah yes...
How about $n=1$? (Wondering)

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

Code: 
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
 
  • #14
mathmari said:
I tried to convert the recursive function pow(n,n) into a while loop... (Wait)
Code: 
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.
Code: 
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.

Code: 
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)
 
  • #15
I like Serena said:
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)
I like Serena said:
Perhaps we should take a look at the algorithm I gave earlier.
Code: 
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.

Code: 
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:

Code: 
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)
 
  • #16
mathmari said:
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:

Code: 
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:
Code: 
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)
 

Similar threads

Making The Best Use Of RAM In Windows
Replies
1
Views
430
MHB Program that accepts inputs of the form 1^n 2^{n^2} 0
Replies
15
Views
4K
MHB Read numbers and print them in sorted order
Replies
8
Views
2K
MHB Equivalent RAM Program: Hints to Show Complexity $O(T^2(n))$
Replies
9
Views
2K
MHB Program to compute the factorial of n
Replies
28
Views
6K
C/C++ Matrix33 in C++: Create, Add, Check & Program
Replies
25
Views
2K
MHB How to Sort Elements of a Matrix in O(n) Time Complexity?
Replies
1
Views
2K
Adding 2 and 3 digit capacity for assembly program
Replies
4
Views
4K
C/C++ How do I compute N factorial in C++?
Replies
3
Views
3K
Programming succesive trapezoidal integrator
Replies
20
Views
2K

Hot Threads

Recent Insights

Back
Top