Integer Sequence Identifier using Assembly Language Homework Solution

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:

1. 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.
2. 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