CSC231 Homework 3 Solutions 2014

--D. Thiebaut (talk) 21:13, 29 September 2014 (EDT)

---

...

Hw3_6

Here's a very quick way of generating some Fibonacci terms:

;;; mostFibs.asm
;;; D. Thiebaut
;;; A very quick program (except for the IO operations that computes and displays 22 Fibonacci numbers)
;;;
extern          _println
extern          _printDec        


;;;  ------------------------------------------------------------
;;;  code area
;;;  ------------------------------------------------------------

                section .text
                global  _start
_start: 
                mov     ebx, 1  ; ebx will contain Fib(n-1)
                mov     edx, 1  ; edx will contain Fib(n-2)

                mov     eax, 1  ; print first 2 fibs
                call    _printDec
                call    _println
        
                call    _printDec
                call    _println
        
;;; compute and print 20 more fibs        
                mov     ecx, 20
for:    
                ;mov     eax, ebx ; compute Fib(n):  get Fib(n-1)
                add     eax, edx ; Fib(n-1) + Fib(n-2)
        
                call    _printDec
                call    _println

                mov     edx, ebx  ; Fib(n-2) gets Fib(n-1)
                mov     ebx, eax  ; Fib(n-1) gets Fib(n)
                loop    for

;;;  exit()
theEnd: 
                mov     eax,1
                mov     ebx,0
                int     0x80    ; final system call

We see that we need 4 instructions to compute a new term of the fibonacci sequence (we remove the printing of the terms, since we are interested in only computing the Fibonacci terms, not printing them).

The processor runs at 2.5 GHz. So a cycle takes 0.4 nanoseconds. 4 instructions take 4 x 0.4 ns = 1.6 ns. So, in 1 second, we could compute 1 sec / 1.6 ns = 1E9 / 1.6 = 625 million terms, or, roughly, 1/2 a billion terms.