MHB Program that accepts inputs of the form 1^n 2^{n^2} 0

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Form Program
AI Thread Summary
The discussion revolves around writing a RAM program to accept inputs of the form $1^n 2^{n^2} 0$. The initial program attempts to count the number of 1's (d) and 2's (s) in the input, but there are concerns about its correctness and handling of invalid inputs. Participants clarify that the program should only accept sequences where all 1's precede all 2's, and it should reject any other symbols.The program is refined multiple times, with discussions focusing on the correct use of instructions like JZERO and JGTZ, which determine the flow of the program based on the input values. There are debates about whether to use WRITE =0 or simply HALT for invalid inputs, and the necessity of conditional statements after loops is also discussed. Ultimately, the program is adjusted to ensure it correctly identifies valid inputs and handles edge cases, with participants confirming improvements and clarifying misunderstandings about the RAM instruction set.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

I have to write a RAM program to accept all inputs of the form $1^n 2^{n^2} 0$.

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.


I have done the following:

Code: 
Read x from input
d=0, s=0
while x!=0
       if x-1=0
           d=d+1
       else
           s=s+1
       Read x from input
p=d*d
r=s-p
if r=0
   Write 1

Then the RAM program is the following:

Code: 
READ 1

LOAD =0
STORE 2

LOAD =0
STORE 3

while: LOAD 1
       JZERO endwhile 

LOAD 1
SUB =1
JGTZ two

LOAD 2
ADD =1
STORE 2

two: LOAD 3
     ADD =1
     STORE 3

READ 1

endwhile:  LOAD 2
           MULT 2
           STORE 4

           LOAD 3
           SUB 4
           STORE 5

LOAD 5
JZERO output
HALT
output: WRITE =1
        HALT

Is this correct?? (Wondering)
 
Technology news on Phys.org
Hi! (Smile)

mathmari said:
I have to write a RAM program to accept all inputs of the form $1^n 2^{n^2} 0$.
Code: 
Read x from input
d=0, s=0
while x!=0
       if x-1=0
           d=d+1
       else
           s=s+1
       Read x from input
p=d*d
r=s-p
if r=0
   Write 1

Suppose we give the input 1212220.
Will it be accepted? (Wondering)

And what happens to 1134560? (Wondering)
 
I like Serena said:
Suppose we give the input 1212220.
Will it be accepted? (Wondering)

It will be accepted... (Doh)

So, we have to make sure that an input will be accepted if all $1$'s are all together at the beginning of the string and then the $2$'s follow, right?? (Wondering)

I like Serena said:
And what happens to 1134560? (Wondering)

And the program has to accept only the symbols $1$ and $2$, right?? (Wondering)

I tried it again... (Nerd)

Code: 
Read x from input
d=0, s=0
while x-1=0
    d=d+1
    Read x from input
while x-2=0
    s=s+1
    Read x from input
if x=0
    p=d*d
    r=s-p
    if r=0
       Write 1
else
    Write 0

Is it better now?? (Wondering)
 
mathmari said:
So, we have to make sure that an input will be accepted if all $1$'s are all together at the beginning of the string and then the $2$'s follow, right?? (Wondering)

And the program has to accept only the symbols $1$ and $2$, right?? (Wondering)

Right! (Nod)
I tried it again... (Nerd)
Code: 
Read x from input
d=0, s=0
while x-1=0
    d=d+1
    Read x from input
while x-2=0
    s=s+1
    Read x from input
if x=0
    p=d*d
    r=s-p
    if r=0
       Write 1
else
    Write 0
Is it better now?? (Wondering)

Much better! (Nod)

Still, if the input is not accepted, we now sometimes get 0 and sometimes we get nothing at all. (Worried)
 
I like Serena said:
Still, if the input is not accepted, we now sometimes get 0 and sometimes we get nothing at all. (Worried)

Why do we get sometimes nothing at all?? (Wondering)
 
mathmari said:
Why do we get sometimes nothing at all?? (Wondering)

What happens with 11220? (Wondering)
 
I like Serena said:
What happens with 11220? (Wondering)

Is it maybe as followed?? (Wondering)

Code: 
Read x from input
d=0, s=0
while x-1=0
    d=d+1
    Read x from input
while x-2=0
    s=s+1
    Read x from input
if x=0
    p=d*d
    r=s-p
    if r=0
       Write 1
    else
       Write 0
else
    Write 0
 
mathmari said:
Is it maybe as followed?? (Wondering)

Code: 
Read x from input
d=0, s=0
while x-1=0
    d=d+1
    Read x from input
while x-2=0
    s=s+1
    Read x from input
if x=0
    p=d*d
    r=s-p
    if r=0
       Write 1
    else
       Write 0
else
    Write 0

That will do the trick!
Good! (Sun)
 
I like Serena said:
That will do the trick!
Good! (Sun)

Great! (Happy)

So, is the RAM program the following?? (Wondering)

Code: 
READ 1

LOAD =0
STORE 2

LOAD =0
STORE 3

while1: LOAD 1
       SUB =1
       JGTZ endwhile1 

LOAD 2
ADD =1
STORE 2

READ 1

JUMP while1

endwhile1: while2: LOAD 1
                   SUB =2
                   JGTZ endwhile2

LOAD 3
ADD =1
STORE 3

READ 1

JUMP while2

endwhile2:  LOAD 1
            JGTZ N
           
LOAD 2          
MULT 2
STORE 4

LOAD 3
SUB 4
STORE 5

LOAD 5
JZERO output
WRITE =0
HALT
output: WRITE =1
        HALT

N: WRITE =0
   HALT
 
  • #10
mathmari said:
Great! (Happy)

So, is the RAM program the following?? (Wondering)

Code: 
READ 1

LOAD =0
STORE 2

LOAD =0
STORE 3

while1: LOAD 1
       SUB =1
       JGTZ endwhile1 

LOAD 2
ADD =1
STORE 2

READ 1

JUMP while1

endwhile1: while2: LOAD 1
                   SUB =2
                   JGTZ endwhile2

LOAD 3
ADD =1
STORE 3

READ 1

JUMP while2

endwhile2:  LOAD 1
            JGTZ N
           
LOAD 2          
MULT 2
STORE 4

LOAD 3
SUB 4
STORE 5

LOAD 5
JZERO output
WRITE =0
HALT
output: WRITE =1
        HALT

N: WRITE =0
   HALT

You have a couple JGTZ's in there that I think should be JZERO's. (Worried)

And I think WRITE =0 is not an allowed instruction. (Wasntme)
 
  • #11
I like Serena said:
You have a couple JGTZ's in there that I think should be JZERO's. (Worried)

Why should they be JZERO?? (Wondering)

The loop is executed while [m]x-1=0[/m].
So, it goes to endwhile when [m]x-1>0[/m], or not??
I like Serena said:
And I think WRITE =0 is not an allowed instruction. (Wasntme)

Why isn't it an allowed instruction?? (Wondering)

So, should I just write [m]HALT[/m]??
 
  • #12
mathmari said:
Why should they be JZERO?? (Wondering)

The loop is executed while [m]x-1=0[/m].
So, it goes to endwhile when [m]x-1>0[/m], or not??

It is supposed to go to endwhile when [m]x-1≠0[/m].
That is different, is it not? :confused:More to the point, suppose your input is $1121110$.
What will happen in your RAM code? (Wondering)
Why isn't it an allowed instruction?? (Wondering)

Mmh... I guess it is allowed.
I had the impression that WRITE needed to have the number of a register as parameter.
But rereading the spec, I guess it can also be an actual number. (Blush)
 
  • #13
I like Serena said:
It is supposed to go to endwhile when [m]x-1≠0[/m].
That is different, is it not? :confused:

JZERO endwhile means that the location counter is set to the instruction labeled endwhile if c(0)=0; otherwise, the location counter is set to the next instruction.

And JGTZ endwhile means that the location counter is set to the instruction labeled endwhile if c(0)>0; otherwise, the location counter is set to the next instruction.

So, which of them do we have to use?? (Wondering)

I like Serena said:
More to the point, suppose your input is $1121110$.
What will happen in your RAM code? (Wondering)

Do we have to use an if statement after the second while ??

Code: 
if x-1=0
   Write 0

(Wondering)
 
  • #14
mathmari said:
JZERO endwhile means that the location counter is set to the instruction labeled endwhile if c(0)=0; otherwise, the location counter is set to the next instruction.

And JGTZ endwhile means that the location counter is set to the instruction labeled endwhile if c(0)>0; otherwise, the location counter is set to the next instruction.

So, which of them do we have to use?? (Wondering)

You are testing for "greater than", when the test should be for "inequality".
I suggest using JZERO to implement a test for inequality.
Do we have to use an if statement after the second while ??

Code: 
if x-1=0
   Write 0

(Wondering)

Let's see... (Thinking)

You have:
Code: 
while x-1=0
  do statements

How about encoding it with:
Code: 
while:
  SUB =1
  JZERO do
  JUMP endwhile
do:
  statements
  JUMP while
endwhile:
(Wondering)
 
  • #15
I like Serena said:
You are testing for "greater than", when the test should be for "inequality".
I suggest using JZERO to implement a test for inequality.
We have

Code: 
while x-1=0
    d=d+1
    Read x from input

So, isn't the while loop executed while [m]x-1=0[/m] ?? (Wondering)

When we write

Code: 
JZERO endwhile

doesn't this mean that the while loop ends when [m]x-1=0[/m] ?? (Wondering)

Or haven't I understood it right?? (Wondering)
 
  • #16
mathmari said:
We have

Code: 
while x-1=0
    d=d+1
    Read x from input

So, isn't the while loop executed while [m]x-1=0[/m] ?? (Wondering)

Yes... (Thinking)

When we write

Code: 
JZERO endwhile

doesn't this mean that the while loop ends when [m]x-1=0[/m] ?? (Wondering)

Or haven't I understood it right?? (Wondering)

Also true.
That's why we should use [m]JZERO do[/m] instead, meaning we jump to the do-part of the while loop instead of the end of the while loop. (Wasntme)
 

Similar threads

MHB Converting Recursion into Loops for Computing n^n
Replies
15
Views
3K
MHB Read numbers and print them in sorted order
Replies
8
Views
2K
Python Partial pivoting in getting the reduced row echelon form of a matrix
Replies
2
Views
1K
Character pattern program -- Print large words using "X" characters
Replies
12
Views
2K
Adding 2 and 3 digit capacity for assembly program
Replies
4
Views
4K
Is this computability theory proof correct?
Replies
1
Views
1K
Python Simple code example of transforming matrix into upper triangular form
Replies
3
Views
1K
C/C++ Matrix33 in C++: Create, Add, Check & Program
Replies
25
Views
2K
Python Python: Semidefinite program with CVXPy 'Error parsing inputs'
Replies
2
Views
2K
Fortran Errors in Fortran code for solving Laplace's equation in 3D
Replies
4
Views
2K

Hot Threads

Recent Insights

Back
Top