Fibonacci Numbers Using Arrays

[ilian007]

Hello I am trying to create a program which will use 3 Arrays to calculate fibonacci numbers. It have to start with 1 and 1 in Arr1 and Arr2 and go up to 72 digit in Arr3 then msg overflow. However I can not find a way to deal with the carry properly when numbers get to 2 digits and up. Please help with some Ideas. Please take in mind it is a 16bit topic and I  am a beginner. Thank you. Here is what I have so Far. Thank you. I hardcoded CX to be 7 to make it work with 7th element ...

;===================================================================
   INCLUDE PCMAC.INC       
     .MODEL  small,basic
      .586
      .STACK 100
   
;===================================================================
                                       ;PROCEDURES TO
             
      
      EXTRN   CLEAR:FAR     ;CLEAR SCREEN
      EXTRN   NEWLINE:FAR    ;DISPLAY NEWLINE CHARACTER
           EXTRN   GETDEC$:FAR     ;GET 16-BIT DECIMAL FROM KBD
      EXTRN   PUTDEC$:FAR     ;DISPLAY 16-BIT DECIMAL INT
      EXTRN   GETDEC:FAR
      EXTRN   PUTDEC:FAR
      EXTRN   PUTBIN:FAR     ;DISPLAY 16BIT BINARY INT
           EXTRN   PUTOCT:FAR     ;DISPLAY 8-BIT NUMBER
      EXTRN   PUTSTRNG:FAR   ;DISPLAY CHARACTER STRING

   
;===================================================================
;DATA  S E G M E N T   D E F I N I T I O N
;
     .DATA
MyArr1   DB 72 dup (0)
MyArr2   DB 72 dup (0)
MyArr3   DB 72 dup (0)
Carry    DB  0
   
          
.CONST
SPACES DB ' '

;===================================================================
;C O D E   S E G M E N T   D E F I N I T I O N
;
            .CODE
       ASSUME  DS:DGROUP
;===================================================================
MAIN PROC

        MOV     AX,DGROUP ;SET DS-REGISTER TO POINT TO
        MOV     DS,AX        ;CONSTANT DATA SEGMENT
   MOV     ES,AX      ;SET ES-REGISTER
   CALL    CLEAR
   MOV DI,71
   
   MOV [myarr1+DI],1  ;start sequence at 1, 1
   MOV [myarr2+DI],1
   MOV CX,7
Adding:
   DEC CX
   CMP CX,0
   JZ print
   MOV DI,71
   MOV AX,0
   MOV BX,0
      
   MOV AL,[myarr1+DI]
   ADD AL,[myarr2+DI]
   CMP AL,9
   JA Carryloop
   
   
   
nocarry:
   MOV [MyArr3+DI],AL   ; Arr3 = Arr2 + Arr1
   MOV BL,[Myarr2+DI] 
   MOV [MyArr1+DI],BL   ;MOV value of Arr2 to Arr1
   MOV [MyArr2+DI],AL   ;mov Value of arr3 to arr2
   Dec DI
   jmp adding

carryloop:
   SUB AL,10
   MOV [Myarr3+DI],AL
   MOV carry,1
   DEC DI
   MOV AL,Carry
   Add [myarr3+DI],AL
   jmp adding
Print:
   mov di,1
printt:
   mov AX,0
   MOV AL,[MyArr3+DI]
   CALL PUTDEC
   inc DI
   cmp DI,71
   ja endd
   jmp printt
   
ENDD:   

   

.EXIT
MAIN ENDP                       
        END    MAIN

[FORTRANS]

Hi,

Code Select Expand


   MOV carry,1
   DEC DI
   MOV AL,Carry
   Add [myarr3+DI],AL
   jmp adding


   At first glance you are not checking for a carry here.  It
may be caught later when you check for greater than 9,
but it seems easier to propagate the carry through the
array all at once.  The ASCII Adjust for Addition instruction
(AAA) is exactly what you need to keep an array of unpacked
BCD numbers updated.  Assuming that you are allowed to
use it of course.

   The following is an update loop from some of my code.
The loop updates five digits rather than 72, but it should make
sense.

Code Select Expand


        MOV     BX,OFFSET Dec_Wrk+4 ; Destination for Decimal bytes.
        MOV     CX,5            ; Five bytes in integer.
        CLC                     ; Clear carry for the first add.

UpD_3:  ; Loop over the 5 digits for the current bit adding the numbers up.
        MOV     AL,CS:[BP]      ; New number
        ADC     AL,[BX]         ; Total sum
        AAA                     ; Adjust unpacked BCD
        MOV     [BX],AL         ; save new sum
        DEC     BX              ; INC/DEC don't affect carry.
        DEC     BP
        LOOP    UpD_3           ; LOOP doesn't affect carry.


   Adding two digits with the carry, adjusting the result to
be a valid single digit, with a possible carry, and store the
result.  Then loop to process the rest of the array.  I have
two arrays, you have three, so adjust the store.

HTH,

Steve N.

Edit:

P.S.  If the carry is set after the loop, you overflowed the
array.

SRN

[ilian007]

We are not allowed to use unpacked BCD or any sort of it for that one. One of our next exercises uses BCD. Teachers idea is to show us the difference. My problem is I have to start adding always from the 72st digit of the array I can not get it how the program will go left to 47th or some digit where it needs to go. like if I have to add


000000000000000000000000000034124141221412412
000000000000000000000000000043214125435235124
0000000000000000000000000 Added

I can not get it how the loop will go left thru the arrays and calculates. I can go through it if it steps just once thru each index. but sometimes it has to step more than once like

00000000000000000000000000000001
00000000000000000000000000000001
00000000000000000000000000000002

00000000000000000000000000000001
00000000000000000000000000000002
00000000000000000000000000000003

has to step a few times thru the 72th digit and then to go to 71st ... 

[dedndave]

We are not allowed to use unpacked BCD or any sort of it for that one.

are they ASCII numeric characters, then ?
by "unpacked BCD", we mean bytes with binary values from 0 to 9
"packed BCD" - they put 2 BCD digits in each byte

we can't tell what you are using because the code shows no initialization of the array values

[ilian007]

Ded.
Unfortenatelly, I dont know what I am using or what I have to use. Teacher gave us 3 arrays and said: add first 2 together and put result in 3rd one. If u get number >9 substract it from 10 add result to A3 and add 1 to carry. and thats for 72 digit arrray ..

[dedndave]

lol
well - just a guess, here - i would say that they are unpacked BCD digits
if they are not, they should be converted to unpacked BCD
if you have ASCII numeric characters, that is a simple matter of XOR'ing or SUB'ing 30h from the ASCII to get BCD
i see a little problem with Steve's code
that is that i don't see where the carry after AAA that is created in AH is applied to the next pass
http://www.arl.wustl.edu/~lockwood/class/cs306/books/artofasm/Chapter_6/CH06-2.html#HEADING2-133

[ilian007]

I Believe I will have to move to next index after each adding operation no matter if there is carry or no. And to stop when a1 + a2 equal to 0 and move back to 72 element (start position)

[ilian007]

Ded, yeah by what I see I guess it is unpacked BCD. I will do a little bit more research

[dedndave]

if i understand what you are saying, the instructor does not want you to use the AAA instruction
he/she wants you to handle the carry into the next digit, "manually"
give me a few minutes to write a little loop....

[dedndave]

        mov     di,71           ;index to last digit
        mov     bx,10           ;bl = 10, bh = 0
        mov     ah,bh           ;clear the carry
        mov     cx,72           ;digit count

add_loop:
        mov     al,MyArr1[di]   ;digit from value 1
        add     al,MyArr2[di]   ;add digit from value 2
        add     al,ah           ;add carry from previous pass
        mov     ah,bh           ;clear out the old carry
        cmp     al,bl           ;is it > 9 ?
        jb      no_carry        ;no - skip carry

        sub     al,bl           ;subtract 10
        inc     ah              ;set carry

no_carry:
        mov     MyArr3[di],al
        dec     di
        loop    add_loop

;if ah = 1 at this point, the accumulator has overflowed

[FORTRANS]

Hi,

   Dave the carry is in the flags.  I ignore AH as it's not
useful here.

   MGG, okay, what you are doing is what the AAA does
anyway.  If the number is grater than 9, subtract 10 and
propagate the carry.  You just need to change your loop
structure a bit.  Pseudo code follows.

Code Select Expand


Normal setup
        Outer loop, do the Fibonacci adds
        (Debug, do a fixed number, later until overflow.)
        Clear carry, set up starting addresses, set count for inner loop, etc..

                Inner loop, do the addition over all elements in the array.
                add with carry ( or as you were doing, keep track in a variable )
                Emulate AAA as you were doing
                        Check if greater than 9
                        if so, sub 10, and set carry
                Change your array indicies.
                LOOP inner

        (Debug, print out the lowest members of the arrays)
        Test for overflow of highest array element, if so exit loop
        Copy your arrays as wanted.

        LOOP outer ( one complete Fib add per loop )

Print results
Exit processsing


HTH?

Steve

P.S.  Dave preempted me again, must type faster...
SRN

[dedndave]

lol Steve - i make a lot of typos, though
my loop could be modified to use the carry flag if AL was set to 0 after it was stored and use STC after SUB
i thought it was just easier to use AH - so the SUB doesn't wipe it out

[ilian007]

Ded, Sorry maybe my bad when I said "teacher wants us to add arr1 and arr2 and put result in arr3' he actually wants that but with fibonacci numbers: something like that:
0 0 0 1
0 0 0 1
0 0 0 2
-------
0 0 0 1
0 0 0 2
0 0 0 3
-------
0 0 0 2
0 0 0 3
0 0 0 5
-------
0 0 0 3
0 0 0 5
0 0 0 8
-------
0 0 0 5
0 0 0 8
0 0 1 3
-------
0 0 0 8
0 0 1 3
0 0 2 1
-------
0 0 1 3
0 0 2 1
0 0 3 4

I have to togle digits in the array I guess and go back to 72 element after each adding procedure ?For what I think is after each adding move value of arr2[di] to arr1[di] and then arr3[di] to arr2[di] and continue ?

[FORTRANS]

Hi Dave,

   Yeah, if "doing it by hand" It's easier to use a variable
or register.  The subtract 10 will do bad things to the flags.
With my code it was easier to use the carry flag as AAA
does all the BCD work, so it is less confusing.  (To me at
least.)

   Hope we're doing more good than bad here.

Regards,

Steve N.

[dedndave]

a Fibonacci sequence is created when the new number is the sum of the previous two numbers
rather than copying numbers, you could just switch arrays:
1) add MyArr1 to MyArr2 and put the sum in MyArr3
2) add MyArr2 to MyArr3 and put the sum in MyArr1
3) add MyArr3 to MyArr1 and put the sum in MyArr2
repeat steps (1) through (3)
you can do this by using "base+index" addressing, then switch bases

first, though - let's make a little improvement to our basic add loop
one technique that can be used is to get rid of the CMP instruction by using SUB in its' place
if the SUB creates a carry, it means the number was less than 10 to start with, so 10 is added back on to correct it
we can combine that with Steve's use of the carry flag to make the loop more efficient

        mov     di,71           ;index to last digit
        lea     cx,[di+1]       ;calculates 72 for the loop count
        mov     dx,10           ;DL = 10, DH = 0
        xor     ax,ax           ;start with AX = 0 and XOR always clears the carry flag

add_loop:
        adc     al,MyArr1[di]   ;add carry flag to digit from value 1
        add     al,MyArr2[di]   ;add digit from value 2

        sub     al,dl           ;is it > 10 ?
        jnc     no_correction   ;yes - skip correction (carry flag = 0)

        add     al,dl           ;add the 10 back in (carry flag = 1)

no_correction:
        mov     MyArr3[di],al   ;store the result
        cmc                     ;invert (compliment) the carry flag
        dec     di              ;adjust the index - INC and DEC do not affect the carry flag
        mov     al,dh           ;zero the accumulator
        loop    add_loop        ;loop decrements CX but also does not affect the carry flag

;if CF = 1 at this point, the accumulator has overflowed

now, give me a few minutes to write the Fibonacci generator...