Equivalent RAM Program: Hints to Show Complexity $O(T^2(n))$

Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
9 replies · 3K views
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

I have to show that for each RAM program of time complexity $T(n)$ under the logarithmic cost function there is an equivalent RAM program of time complexity $O(T^2(n))$ which has no MULT or DIV instructions.

Could you give me some hints how to show that?? (Wondering)
 

Discussion

Physics news on Phys.org
mathmari said:
Hey! :o

I have to show that for each RAM program of time complexity $T(n)$ under the logarithmic cost function there is an equivalent RAM program of time complexity $O(T^2(n))$ which has no MULT or DIV instructions.

Could you give me some hints how to show that?? (Wondering)

Hi! (Smile)

Let's assume a worst case scenario, where at an innermost loop on the critical path we have a MULT or DIV instruction.

Then we should replace that instruction by a sub program.
Can you create such a RAM sub program for the MULT instruction? (Wondering)

If so, what is its complexity? (Wondering)
 
I like Serena said:
Can you create such a RAM sub program for the MULT instruction? (Wondering)

Is it maybe as followed??

c(0) ← c(0)
c(0) ← c(0)+c(0)
...
c(0) ← c(0)+...c(0) (v(a) times)
Code: 
LOAD =1
STORE 1

LOAD a
STORE 2

while: LOAD 2
      SUB 1
      JZERO endwhile

ADD 0
LOAD 1
ADD =1

endwhile: WRITE 0

(Wondering)
 
mathmari said:
Is it maybe as followed??

c(0) ← c(0)
c(0) ← c(0)+c(0)
...
c(0) ← c(0)+...c(0) (v(a) times)
Code: 
LOAD =1
STORE 1

LOAD a
STORE 2

while: LOAD 2
      SUB 1
      JZERO endwhile

ADD 0
LOAD 1
ADD =1

endwhile: WRITE 0

(Wondering)

Something like that, although I don't think this will quite work. (Worried)

What are you multiplying exactly? (Wondering)
I'd expect an $a$ and a $b$, but I'm only seeing an $a$.

Which pseudo code do you have? (Wondering)
 
I like Serena said:
Something like that, although I don't think this will quite work. (Worried)

What are you multiplying exactly? (Wondering)
I'd expect an $a$ and a $b$, but I'm only seeing an $a$.

Which pseudo code do you have? (Wondering)

I thought again about it and I wrote the following pseudocode:

Code: 
i=1
result=0
Read a
Read b
while b-i>0
     result=result+a
     i=i+1
Write result

And the RAM progam is the following:

Code: 
LOAD =1
STORE 1

LOAD =0
STORE 2

READ 3
READ 4

while: LOAD 4
       SUB 1
       JZERO endwhile

LOAD 2
ADD 3

endwhile: WRITE 2

Is this correct? (Wondering)
 
mathmari said:
I thought again about it and I wrote the following pseudocode:

Code: 
i=1
result=0
Read a
Read b
while b-i>0
     result=result+a
     i=i+1
Write result

Let's see... (Thinking)
Suppose I pick $a=b=1$, then I get... $a * b = 1 * 1 = 0$.
Does that sound right? (Worried)
 
I like Serena said:
Let's see... (Thinking)
Suppose I pick $a=b=1$, then I get... $a * b = 1 * 1 = 0$.
Does that sound right? (Worried)

Is it maybe as followed??

Code: 
i=1
Read a
Read b
if b=0
     Write 0
result=a
while b-i>0
     result=result+a
     i=i+1
Write result

(Wondering)
 
mathmari said:
Is it maybe as followed??

Code: 
i=1
Read a
Read b
if b=0
     Write 0
result=a
while b-i>0
     result=result+a
     i=i+1
Write result

(Wondering)

That would work. (Smile)

How about:
Code: 
i=b
result=0
while i>0
     result=result+a
     i=i-1
(Thinking)
 
mathmari said:
Code: 
i=1
Read a
Read b
if b=0
     Write 0
result=a
while b-i>0
     result=result+a
     i=i+1
Write result

Is the RAM program the following??
Code: 
LOAD =1
STORE 1

READ 2
READ 3

LOAD 3
JZERO z

LOAD 2
STORE 4

while: LOAD 3
       SUB 1
       JZERO endwhile

LOAD 4
ADD 2
STORE 4

LOAD 1
ADD =1
STORE 1

JUMP while

endwhile: WRITE 4
          HALT

So is the the time complexity under the logarithmic cost as followed??

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

READ 2 : l(a)+2
READ 3 : l(b)+2

LOAD 3 : l(3)+l(c(3))=log(3)+1+l(b)
JZERO z : l(c(0))=l(b)

LOAD 2 : l(2)+l(c(2))=2+l(a)
STORE 4 : l(c(0))+l(4)=l(a)+3

while: LOAD 3 : l(3)+l(c(3))=log(3)+l(b)
SUB 1 : l(c(0))+l(1)+l(c(1))=l(b)+1+l(1)=l(b)+1+1=l(b)+2
JZERO endwhile : l(c(0))=l(b-1)=log(b-1)+1

LOAD 4 : l(4)+l(c(4))=3+l(a)
ADD 2 : l(c(0))+l(2)+l(c(2))=l(a)+2+l(a)=2l(a)+2
STORE 4 : l(c(0))+l(4)=l(2a)+3

LOAD 1 : l(1)+l(c(1))=1=1=2
ADD =1 : l(c(0))+l(1)=l(1)+l(1)=2
STORE 1 : l(c(0)+l(1)=l(2)+1=3+1=4

JUMP while : 1

endwhile: WRITE 4 : l(4)+l(c(4))=3+l(2a)
HALT : 1$$1+2+l(a)+2+l(b)+2+log(3)+1+l(b)+l(b)+2+l(a)+l(a)+3+log(3)+l(b)+l(b)+2+log(b-1)+1+WHILE +3 l(2a)+1=20+3l(a)+l(2a)+5l(b)+2log(3)+log(b-1)+WHILE=20+3log(a)+3+log(2a)+1+5log(b)+5+2log(3)+log(b-1)+WHILE$$

Where $$WHILE=(b-1)(log(3)+l(b)+l(b)+2+log(b-1)+1+3+l(a)+2l(a)+2+l(2a)+3+2+2+4+1)=(b-1)(20+2l(b)+3l(a)+l(2a)+log(3)+log(b-1))=(b-1)(20+2log(b)+2+3log(a)+3+log(2a)+1+log(3)+log(b-1))$$

Is this correct?? (Wondering)
 
mathmari said:
Is the RAM program the following??

It should be something like that, but the exact form is not all that important.
What is important, is that you have a while-loop that will iterate $n$ times in a worst case scenario.
When determining the order of complexity, the stuff that is outside the while-loop is not relevant. (Nerd)
So is the the time complexity under the logarithmic cost as followed??

That might be correct I guess, but I think it is too detailed. (Worried)

The important thing to note is that the while-loop is more "complex" than the rest of the RAM sub program.
The complexity of this MULT operation is $O(T(\text{whileloop}) \cdot n)$

Since we were assuming the real RAM program had complexity $T(n)$, that means that if we replace a MULT, that is a bottleneck, by the sub program, the resulting complexity is $O(T(n) \cdot T(\text{whileloop}) \cdot n)$. (Wasntme)