University of Iceland



Software Assignment 1The Fibonacci SequenceValdemar ?rn ErlingssonPseudo CodeI Started out writing a simple version of the software in a language that I know very well, C++. I made sure it did what it was supposed to and then altered the code to be more language-independent. Obviously some parts must be changed as Assembly does not directly have some of the functionality I use (like while-loops and if-statements).Main:int n// for calculating the nth fibonacci numberint f// This is the final outcome, f = fibonacci(n)print "Calculate fibonacci number: "n = [input from user]f = Fibo(n)// Call subroutine fibo, pass n to it, and return the number fprint f// Print f to the screenFibo:int ai = 1// the ith number in the sequence. Start at one for referenceint ah = 1// the i-1th number. Start at one for referenceint store = 0// Placeholder value.int i = 0// The number to which we have calculated the fibonacci number.while i ≤ n// Calculate within this regionif i < 2ai = 1// fibonacci numbers 0 and 1 equal one.i = i + 1// increment to the next place in sequenceelsestore = ai// Keep old number for referenceai = ah + ai// sum the current number with the old one.ah = store// We have now calculated the next place in the sequence, // insert [store] as old numberi = i + 1// increment to the next place in sequencereturn aiAssembly Code*-----------------------------------------------------------* Program : Fibonacci Sequence* Written by : Valdemar Erlingsson* Date : 28.09.2008* Description: Short and simple program that finds the n'th *fibonacci number in the sequence*-----------------------------------------------------------STARTORG$1000LEAoutput,A1* Load output for use in the Trap functionMOVE.B#14,D0* Set the action of the Trap function to printTRAP#15* Display messageMOVE.B#4,D0* Set the action of the Trap function to inputTRAP #15* Get inputMOVE.BD1,n* Store input value in a safe locationBSRFIBO* Branch to subroutine, pass n through register D1* the outcome is accessible through f and D2LEAoutput2,A1MOVE.B#14,D0TRAP#15* Print second messageMOVE.Lf,D1* Move f do D1 for displayingMOVE.B#3,D0TRAP#15* Print fBRAEND* End programFIBO* Use D1 Register for nMOVE.L#1,D2* Use D2 Register for aiMOVE.L#1,D3* Use D3 Register for ahMOVE.L#0,D4* Use D4 Register for storeMOVE.L#0,D5* Use D5 Register for i (iterator)CHECKCMP.LD1,D5* compare i and nBGTCOMPLETE* Inverse of the pseudocode, branch if i>nCMP.L#2,D5* Is 2 < i ? Should the program branch?BGEOVERTWO* i is greater than 2, goto OVERTWOMOVE.L#1,D2* ai = 1ADDI.L#1,D5* i++BRA CHECK* Go back to loop requirementOVERTWOMOVE.LD2,D4* store = aiADD.LD3,D2* ai = ah + aiMOVE.LD4,D3* ah = storeADDI.L#1,D5* i++BRA CHECK* Go back to loop requirementCOMPLETEMOVE.LD2,f* Store output value in a safe locationRTS* Return back to lower stacknDS.L1* Reserve space for n and ffDS.L1outputDC.B'Calculate fibonacci number: ',0output2DC.B'The number is: ',0ENDMOVE.B#9,D0TRAP#15Halt SimulatorENDSTARTAbout the programHad some problems at first getting values higher than 65536 ( = 216), but this was due to the fact that I forgot to add a .L parameter to the Add statement. This was easily rectified. Other than that, I was able to collect everything I needed to know to complete the assignment from and Karl's lectures.The program itself is very simple. It starts out asking the user for a number, n, which represents that nth number in the Fibonacci sequence. The first two numbers equal zero, but all numbers above that are the sum of the two previous numbers. hopefully the pseudocode and the commented assembly code are enough to explain the execution of the program.Execution:Calculate fibonacci number: 7The number is: 21Calculate fibonacci number: 27The number is: 317811Differences between Assembly and Pseudo-code:Definition of variables. I define n and f at the bottom of the program, as data storage of size Long (I used long variables allow greater outcomes than 216 = 65536).Registers are used to hold variables within the Fibo() function. This makes the program run faster and simplifies it.one quirk of transporting the project from pseudo to assembly were the compare statements:CMP.L#2,D5* Is 2 < i ? Should the program branch?BGEOVERTWO* i is greater than 2, go to OVERTWOHere it was easier to reverse the if-statement (originally written if(i < 2) ), because a BRANCH must be used if the condition is not met (if it's met we simply execute the code that follows).SidenoteIn the assignment the Fibonacci sequence is defined as:Fn= 1 n=0,1Fn-1+F(n-2)n>1 This is actually not the usual way to define the sequence. Rather, it is defined:Fn= 0 n=0 1 n=1,2Fn-1+F(n-2)n≥3 This doesn't really affect our assignment, but I thought it was a fact to notice. ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download