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

In summary: ADD =1 STORE 2while2: LOAD 3 ... SUB =1 JGTZ twotwo: LOAD 3 ... ADD =1 STORE 3READ 1ENDWHILE2: LOAD 2 ... SUB =1 JGTZ
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

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
  • #2
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)
 
  • #3
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)
 
  • #4
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)
 
  • #5
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)
 
  • #6
mathmari said:
Why do we get sometimes nothing at all?? (Wondering)

What happens with 11220? (Wondering)
 
  • #7
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
 
  • #8
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)
 
  • #9
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)
 

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

What is the purpose of a program that accepts inputs of the form 1^n 2^{n^2} 0?

The purpose of this program is to generate a sequence of numbers based on the inputs 1, 2, and 0. The sequence follows a specific pattern where the exponent of 1 increases by 1 with each subsequent number and the exponent of 2 increases by the square of the previous number. This program can be used for various mathematical and scientific calculations.

What are the inputs for this program?

The inputs for this program are three numbers: 1, 2, and 0. The first number, 1, is the base of the exponential function. The second number, 2, is the base of the second exponential function. The third number, 0, indicates the end of the sequence.

Can the inputs be changed to different numbers?

Yes, the inputs can be changed to different numbers. However, the sequence will follow a different pattern depending on the inputs. For example, if the inputs are changed to 2^n 3^{n^2} 0, the sequence will follow a pattern where the exponent of 2 increases by 1 and the exponent of 3 increases by the square of the previous number.

What is the output of the program?

The output of the program is a sequence of numbers that follows the pattern specified by the inputs. The sequence will continue until the third input, 0, is reached. The output can be used for further calculations or analysis.

How can this program be useful for scientific research?

This program can be useful for scientific research by generating a sequence of numbers that follows a specific pattern. The output of the program can be used for various calculations and analysis, such as studying the growth of certain phenomena or modeling complex systems. It can also be used to test hypotheses and make predictions in scientific experiments.

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
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
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
1K
MHB Approximating the Double Integral using Monte Carlo Method
Replies
1
Views
1K
Fortran Errors in Fortran code for solving Laplace's equation in 3D
Replies
4
Views
2K
MHB Program to calculate the sum of polynomials
Replies
4
Views
1K

Hot Threads

Recent Insights

Back
Top