Determine the Integer Sequence
Your program will receive a sequence of integers from the user and decide if this sequence is a Fibonacci sequence, a Triangular sequence, or neither.
Background
A Fibonacci sequence is formed by generating a number in the sequence by adding the previous two numbers in the sequence. Specifically,
F0 =F1 =1
Fi =Fi-1 +Fi-2 fori>1
Hence, the first few numbers in the sequence are: 1, 1, 2, 3, 5, 8, 13, 21, ... The next number in the sequence is 13 + 21 = 34.
A Triangular sequence is formed of numbers representing triangles drawn with dots or asterisks: 1, 3, 6, 10, 15, ... Specifically,
T0 = 1
Ti=Ti-1 +i +1 for i >0
Hence, the next number in the above sequence is T5 = 15 + 5 + 1 = 21.
Details
The program generates a random integer and then prompts the user to enter the numbers in the sequence. The sequence is read one number at a time. You will need to call the C library scanf() function. The user ends the sequence with a negative number, in which case, your program exits after displaying a message indicating the length and type of the sequence. If it is neither Fibonacci nor Triangular, the program displays the largest two numbers in the sequence. If the program reads a number that matches the randomly generated integer, it displays an appropriate message (suggestion: You won the jackpot).
Write two versions of the program:
- Write the Assembly Language assignment without macros (i.e. don't use m4). Use a pre-test loop, where the test is at the top of the loop.
- Rewrite the above program by putting the loop test at the bottom of the loop (make sure it is still a pre-test loop) and add macros to the above program to make it more readable (use m4). In particular, provide macros for heavily used registers.
.data
n: .word 0
.text
output0: .string "Enter a value:%d"
ldr X0, =output0
bl printf
output1:string "The length of this sequence is %d, and it is a Fibonacci sequence."
output2:string "The length of this sequence is %d, and it is a Triangular sequence."
output3: .string "Congratulations! You have won the jackpot."
output4: .string "The length of this sequence is %d, and it is neither a Fibonacci nor a Triangular sequence. The greatest value in this sequence is %d"
input0: .string "%d"
.balign 4
.global main
// Initialization of the random number using the C library.
mov x0,#0
bl time
bl srand
bl rand
mov X25,x0
main: stp X29, X30, [sp, -16]!
mov X29, sp
mov X19, #1
mov X20, #2
mov X23, xzr
b output0
b WHILE1 // Obtain the first value of the seqeunce.
b isNegative
b jackpot
b isFibonacci
b isTriangular
b isNeither
b output0 // Obtain the second value in the sequence.
b WHILE1
b isNegative
b jackpot
cmp X14,X21 // Compare the user's next input (copied to X14) and the value predicted by the function isFibonacci
b.eq isFibonacci
b.ne elseTriangular // If the two values are not equal, the sequence may be triangular or arbitrary.
ldp X29, X30, [sp], 16
ret
elseTriangular:
cmp X14,X22 // If the condition above is not satisfied, we check to see if the sequence may be triangular.
b.eq isTriangular
b.ne is neither
b main // Go back to the top of the main function
WHILE1:
ldr X0, =input0
ldr X1, =n
bl scanf
ldr X14, n
ret
isNegative:
mul X15, X19, X14 // Negate the result of the multiplication of 1 (X19) and the user input (X14)
add X24, X24,#1 // Increment the count register X24 to keep track of the length of the sequence.
cmp X14,X15
b.ne ret
jackpot:cmp X14,X24
b.ne ret
ldr X0, =output3
bl printf
ret
isFibonacci: // Adapted from https://www.geeksforgeeks.org/find-the-next-fibonacci-number/
add X15,X19,X20 // The approximation of sqrt(5) is 2. The division at the end truncates remainder, so an approximation here is justified.
mul X16,X15,X14
udiv X21,X16,X20 // We must round the final answer, however the remainder gets truncated at the end of udiv.
add X21,X21,X19 // To round the next number in the sequence, we add 1 to the result.
udiv X21,X21,X19 // Then, we divide the updated result with 1 again to get its rounded integer value.
ret
isTriangular: // The general formula for finding the next number in a triangular sequence is as follows with n being the user input: n(n+1)/2
add X15,X14,X19
mul X16,X14,X15
udiv X22,X16,X20
ret
isNeither:
cmp X23,X14
b.le ignore // le's complement is gt (greater than). We ignore any value that is less the greatest value.
mov X24, X14 // If the user has entered a value greater than zero (initially), we set that to be the greatest value that the user has entered.
b main
ret
ignore:
done: // Print statement calls
Solution:
1.
.data
n: .word 0
.text
output0: .string "Enter value %d: "
output1: .string "The length of this sequence is %d, and it is a Fibonacci sequence.\n"
output2: .string "The length of this sequence is %d, and it is a Triangular sequence.\n"
output3: .string "Congratulations! You have won the jackpot.\n"
output4: .string "The sequence is neither a Fibonacci nor a Triangular sequence. The largest numbers in this sequence are %d and %d\n"
errmsg0: .string "Not enough numbers in the sequence!\n"
input0: .string "%d"
.balign 4
.global main
main: stp X29, X30, [sp, -16]!
mov X29, sp
// Initialization of the random number using the C library.
mov x0, 0
bl time
bl srand
bl rand
mov W19, W0 // save random number in X19
and W19, W19, 31 // use only range from 1 - 32
add W19, W19, 1
mov X24, 0 // which series is?, -1 = none, 0 = undecided, 1 = fibonacci, 2= triangular
mov X27, 0 // sequence length
ldr X0, =output0 // load string address
mov X1, X27 // load seq length
bl printf // print
ldr X0, =input0 // read number
ldr X1, =n
bl scanf
ldr X0, =n // load number
ldr W20, [X0]
cmp W20, 0 // check if it's negative
blt error1 // if negative, error
add X27, X27, 1 // increment length
cmp W19, W20 // if jackpot
beq jackpot
cmp W20, 1 // first value must be 1
beq read2nd
mov X24, -1 // seq is not valid
read2nd:
ldr X0, =output0 // load string address
mov X1, X27 // load seq length
bl printf // print
ldr X0, =input0 // read number
ldr X1, =n
bl scanf
ldr X0, =n // load number
ldr W21, [X0]
cmp W21, 0 // check if it's negative
blt error1 // if negative, error
add X27, X27, 1 // increment length
cmp W19, W21 // if jackpot
beq jackpot
cmp W21, 1 // if valid second
beq initialize
cmp W21, 3 // if valid second
beq initialize
mov X24, -1 // error, not a sequence
initialize:
mov W26, W21 // first max
mov W25, W20 // second max
cmp W21, W20 // compare read numbers
bge numok // if in sequence, ok
mov W26, W20 // else, swap
mov W25, W21
mov X24, -1 // error, not a sequence
b while1 // read more numbers
numok:
// calculate next fibonacci
add W22, W20, W21
// calculate next triangular
sub W0, W21, W20 // difference = i + 1
add W23, W21, W0 // next = Ti-1 + i + 1
add W23, W23, 1
while1:
ldr X0, =output0 // load string address
mov X1, X27 // load seq length
bl printf // print
ldr X0, =input0 // read number
ldr X1, =n
bl scanf
ldr X0, =n // load number
ldr W0, [X0]
cmp W0, #0 // check if it's negative
blt printResults // if negative, end loop and print results
add X27, X27, 1 // increment sequence
cmp W19, W0 // if jackpot
beq jackpot
cmp W0, W26 // see if > max1
blt chkMax2
mov W25, W26
mov W26, W0 // if >, replace max1
b chkType
chkMax2:
cmp W0, W25 // see if > max2
blt chkType
mov W25, W0 // if >, replace max2
chkType:
cmp X24, -1 // if error
beq while1 // read another
// check if fibonacci
cmp W0, W22 // if fibonacci
bne checkTri
cmp X24, 2 // if it was triangular
beq notSeq // set as not valid
mov X24, 1 // set as fibonacci
mov W20, W21 // shift register values
mov W21, W0
// calculate next fibonacci
add W22, W20, W21
b while1 // repeat
checkTri:
cmp W0, W23 // if triangular
bne notSeq
cmp X24, 1 // if it was fibonacci
beq notSeq // set as not valid
mov X24, 2 // set as triangular
mov W20, W21 // shift register values
mov W21, W0
// calculate next triangular
sub W0, W21, W20 // difference = i + 1
add W23, W21, W0 // next = Ti-1 + i + 1
add W23, W23, 1
b while1
notSeq:
mov X24,-1
b while1
error1:
ldr X0, =errmsg0 // load string address
bl printf // print
b terminate
printResults:
cmp X24, -1 // if no sequence
beq notFound
cmp X24, 1 // if fibonacci
beq isFibonacci
cmp X24, 2 // if triangular
beq isTriangular
notFound:
ldr X0, =output4
mov X1, X25
mov X2, X26
bl printf
b terminate
isFibonacci:
ldr X0, =output1
mov X1, X27
bl printf
b terminate
isTriangular:
ldr X0, =output2
mov X1, X27
bl printf
b terminate
jackpot:
ldr X0, =output3
bl printf
terminate:
ldp X29, X30, [sp], 16
ret
2.
//----- Macros
define(fp, X29) // frame pointer
define(lr, X30) // link register
define(rndnum, W19) // random number
define(seq0, W20) // first number in seq
define(seq1, W21) // second number in seq
define(nextFib, W22) // next number in fibonacci seq
define(nextTri, W23) // next number in triangular seq
define(seqType, X24) // type of sequence
define(max2, W25) // second maximum
define(max1, W26) // first maximum
define(seqLen, X27) // sequence length
.data
n: .word 0
.text
output0: .string "Enter value %d: "
output1: .string "The length of this sequence is %d, and it is a Fibonacci sequence.\n"
output2: .string "The length of this sequence is %d, and it is a Triangular sequence.\n"
output3: .string "Congratulations! You have won the jackpot.\n"
output4: .string "The sequence is neither a Fibonacci nor a Triangular sequence. The largest numbers in this sequence are %d and %d\n"
errmsg0: .string "Not enough numbers in the sequence!\n"
input0: .string "%d"
.balign 4
.global main
main: stp fp, lr, [sp, -16]!
mov fp, sp
// Initialization of the random number using the C library.
mov x0, 0
bl time
bl srand
bl rand
mov rndnum, W0 // save random number in rndnum
and rndnum, rndnum, 31 // use only range from 1 - 32
add rndnum, rndnum, 1
mov seqType, 0 // which series is?, -1 = none, 0 = undecided, 1 = fibonacci, 2= triangular
mov seqLen, 0 // sequence length
ldr X0, =output0 // load string address
mov X1, seqLen // load seq length
bl printf // print
ldr X0, =input0 // read number
ldr X1, =n
bl scanf
ldr X0, =n // load number
ldr W20, [X0]
cmp W20, 0 // check if it's negative
blt error1 // if negative, error
add seqLen, seqLen, 1 // increment length
cmp rndnum, W20 // if jackpot
beq jackpot
cmp W20, 1 // first value must be 1
beq read2nd
mov seqType, -1 // seq is not valid
read2nd:
ldr X0, =output0 // load string address
mov X1, seqLen // load seq length
bl printf // print
ldr X0, =input0 // read number
ldr X1, =n
bl scanf
ldr X0, =n // load number
ldr seq1, [X0]
cmp seq1, 0 // check if it's negative
blt error1 // if negative, error
add seqLen, seqLen, 1 // increment length
cmp rndnum, seq1 // if jackpot
beq jackpot
cmp seq1, 1 // if valid second
beq initialize
cmp seq1, 3 // if valid second
beq initialize
mov seqType, -1 // error, not a sequence
initialize:
mov max1, seq1 // first max
mov max2, W20 // second max
cmp seq1, W20 // compare read numbers
bge numok // if in sequence, ok
mov max1, W20 // else, swap
mov max2, seq1
mov seqType, -1 // error, not a sequence
b while1 // read more numbers
numok:
// calculate next fibonacci
add nextFib, W20, seq1
// calculate next triangular
sub W0, seq1, W20 // difference = i + 1
add W23, seq1, W0 // next = Ti-1 + i + 1
add W23, W23, 1
while1:
ldr X0, =output0 // load string address
mov X1, seqLen // load seq length
bl printf // print
ldr X0, =input0 // read number
ldr X1, =n
bl scanf
ldr X0, =n // load number
ldr W0, [X0]
cmp W0, #0 // check if it's negative
blt printResults // if negative, end loop and print results
add seqLen, seqLen, 1 // increment sequence
cmp rndnum, W0 // if jackpot
beq jackpot
cmp W0, max1 // see if > max1
blt chkMax2
mov max2, max1
mov max1, W0 // if >, replace max1
b chkType
chkMax2:
cmp W0, max2 // see if > max2
blt chkType
mov max2, W0 // if >, replace max2
chkType:
cmp seqType, -1 // if error
beq while1 // read another
// check if fibonacci
cmp W0, nextFib // if fibonacci
bne checkTri
cmp seqType, 2 // if it was triangular
beq notSeq // set as not valid
mov seqType, 1 // set as fibonacci
mov seq0, seq1 // shift register values
mov seq1, W0
// calculate next fibonacci
add nextFib, seq0, seq1
b while1 // repeat
checkTri:
cmp W0, nextTri // if triangular
bne notSeq
cmp seqType, 1 // if it was fibonacci
beq notSeq // set as not valid
mov seqType, 2 // set as triangular
mov seq0, seq1 // shift register values
mov seq1, W0
// calculate next triangular
sub W0, seq1, seq0 // difference = i + 1
add nextTri, seq1, W0 // next = Ti-1 + i + 1
add nextTri, nextTri, 1
b while1
notSeq:
mov seqType,-1
b while1
error1:
ldr X0, =errmsg0 // load string address
bl printf // print
b terminate
printResults:
cmp seqType, -1 // if no sequence
beq notFound
cmp seqType, 1 // if fibonacci
beq isFibonacci
cmp seqType, 2 // if triangular
beq isTriangular
notFound:
ldr X0, =output4
mov X1, X25
mov X2, X26
bl printf
b terminate
isFibonacci:
ldr X0, =output1
mov X1, seqLen
bl printf
b terminate
isTriangular:
ldr X0, =output2
mov X1, seqLen
bl printf
b terminate
jackpot:
ldr X0, =output3
bl printf
terminate:
ldp fp, lr, [sp], 16
ret