Fibonacci Numbers Using Arrays

[dedndave]

        mov     ax,@DATA
        mov     ds,ax
        mov     es,ax
        mov     bx,offset MyArr1  ;start with BX = MyArr1
        mov     bp,offset MyArr2  ;start with BP = MyArr2
        mov     si,offset MyArr3  ;start with SI = MyArr3
        mov     dx,10             ;DL = 10, DH = 0

        mov     cx,72             ;<------------------------------- put the fibonacci number you want in CX

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

add_loop:
        adc     al,[bx+di]        ;add carry flag to digit from value 1
        add     al,ds:[bp+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:
        xchg    si,bx             ;we need SI to be in either BP or BX for base+index addressing
        mov     [bx+di],al        ;store the result
        xchg    si,bx             ;switch BX and SI back
        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

        xchg    bp,si             ;rotate the array base addresses
        xchg    bp,bx
        pop     cx                ;recall the loop count
        jc      loop_overflow

        loop    fibonacci_loop    ;loop until overflow occurs

;the base address of the array with the last valid result is in SI

loop_overflow:

add the ascii loop and PUTSTRNG here
the array address is in SI
with a little work, we can get rid of the leading 0's

[dedndave]

add this code to the end of the code above
it will get rid of leading zeros
i found out that PUTSTRNG wants the address in DI - not in DX
notice in the code above, the ES register is set to @DATA, as well as DS

loop_overflow:
        mov     di,si               ;save the address in DI for PUTSTRNG
        mov     al,30h              ;ASCII "0"
        mov     cx,72

ascii_loop:
        or      [si],al
        inc     si
        loop    ascii_loop

        cld
        mov     cx,71
        repz    scasb
        dec     di
        inc     cx
        call    PUTSTRNG

[ilian007]

yeah it works now :) just take attention from 344 to 346 .. after 344 number doesnt change. I believe after CX = 346 it shouldnt work and have to display msg. 346 is the max number to display in 72 digit. 347 need 73 digits.

Now I am going to class thanks :) will examine it tonite ..

[ilian007]

Hi dedndave I was playing with the program on ThanksGiving and can not make it work with 345 and 346 the overflow should be on 347.. if I remove the JC it displays normally the 345th and 346th. I fixed some of the code you gave me because it didnt display first 5 numbers. I believe it was something small in CX. here is the code which overflow at 345 instead of 347. can you take a look? Thanks

;===================================================================
   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   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 71 dup (0),1
MyArr2   DB 71 dup (0),1
MyArr3   DB 72 dup (0)
Carry    DB  0
   
         
.CONST
SPACES DB ' '
over   DB 'overflow occured please go one step backward'
;===================================================================
;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     bx,offset MyArr1  ;start with BX = MyArr1
        mov     bp,offset MyArr2  ;start with BP = MyArr2
        mov     si,offset MyArr3  ;start with SI = MyArr3
        mov     dx,10             ;DL = 10, DH = 0

        CALL getDEC
   mov     cx,AX             ;<------------------------------- put the fibonacci number you want in CX

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

add_loop:
        adc     al,[bx+di]        ;add carry flag to digit from value 1
        add     al,ds:[bp+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:
        xchg    si,bx             ;we need SI to be in either BP or BX for base+index addressing
        mov     [bx+di],al        ;store the result
        xchg    si,bx             ;switch BX and SI back
        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

   jc      loop_overflow


        xchg    bp,si             ;rotate the array base addresses
        xchg    bp,bx
        pop     cx                ;recall the loop count
        loop    fibonacci_loop    ;loop until overflow occurs

   
   jmp print
;the base address of the array with the last valid result is in SI

loop_overflow:
   LEA DI,OFFSET over
   MOV cx,sizeof over
   call putstrng
   jmp endd       
   
print:

   mov     di,si               ;save the address in DI for PUTSTRNG
        mov     al,30h              ;ASCII "0"
        mov     cx,72

ascii_loop:
        or      [si],al
        inc     si
        loop    ascii_loop

        cld
        mov     cx,72
        repz    scasb
        dec     di
        inc     cx
        call    PUTSTRNG




ENDD:   

   

.EXIT
MAIN ENDP                       
        END    MAIN

[dedndave]

the reason that happens is this...
the overflow is detected before we allow it to happen in the [SI] array
that way, the array pointed to in SI is always valid
the array that actually is overflowed is pointed to in BX
also - remember, your teacher is counting the Fibonacci numbers off by 1
what he is calling Fibonacci #8 is actually Fibonacci #9
if you go to the web-based calculator site and crank out the 72 digit number, we have it right

one way to fix the problem is to add an extra element to all the arrays
when we get to the end, if the first element of the [SI] array is not 0, it overflowed
i don't know if that is acceptable to you, as we are now using 73 element arrays instead of 72
however, it could be explained that the 73rd element is the "carry" or "overflow" element and not part of the value

another way to fix it would be to set a flag the first time carry is set and allow the loop to make one more pass
that is clumsy and silly, really, as we are forcing it to give us an invalid number
in the end, we won't display that number, anyway - we will just display an "Overflow" message in it's place
this still may be the best solution, as we are using 72 byte arrays which meet his criteria

EDIT - i think i have a better solution
we can simply use the array in [BX] instead of the one in [SI] and adjust our count number so they match the teachers
i will play with it tomorrow and see if it flies

[dedndave]

here we go - give this a try....

[raymond]

One thing I would like to know is why your teacher is insisting that you use three arrays. Computing Fibonacci numbers is so much easier using only two arrays. Is it possible to ask him that question and post his reply?

[ilian007]

I will ask him tomorrow and will anser your quest raymond

[FORTRANS]

   This is something of an insomnia induced rant.  If you are a
person looking for "real" content, bail out now.  You have been
warned.  Those that like blither carry on.

   Here is a version of a Fibonacci number program that uses an
AAA instruction to correct the unpacked BCD number.  In reply 1
I showed some code using the carry flag and an ADC to propagate
the carries along.  Dave in reply 5 showed that a different way
that uses the AH register to propagate a carry was possible.  I
think that until Dave pointed to that I just considered this to
be something to work around.  It changes AH so you can't use it
for something else.  But as that was intentional, you should be
able to use that effect productively.  This idea popped into my
so called mind after I woke up in the middle of the night.  And
it wouldn't leave me until I worked it out and coded it up.  As
I have not seen it used this way before (or do not remember any
such examples) I thought I would post it.

   After coding it up, I do not see any real advantage over the
way I did it before.  I did find it interesting to play with an
X86 instruction that RISC aficionados probably sneer at.  In my
program I used the three arrays that the other programs in this
thread use to ease any comparison wanted.  To address Raymond's
comments in reply 36, I think that when teaching beginners that
using two source arrays with a distinct destination array would
make it easier to describe the Fibonacci sequence and a program
to generate it, rather than using a two array program to do the
same thing.  Once the ideas settle in, it is better to use only
two arrays, change pointers to the arrays, and overwrite one of
the arrays with the result.  It obviates the need for a routine
to copy the arrays before the next iteration and saves space as
well.  But I think teaching rank beginners those concepts would
be more difficult.  Of course then my incrementing digits in an
ASCII label to create a loop counter would not be productive in
such an environment.  Oopsie.

   End rant.

Cheers,

Steve N.

[dedndave]

well, Steve, if it makes you feel any better, i wouldn't use "arrays" (BCD strings) at all
i would use multi-byte binary integers   :bg
it would greatly simplify the loop and the carry flag would wrap around nicely
as for using 2 registers instead of 3 - it would be easier to use 2, especially with multi-byte integers
i think we all were trying to follow the students example, in order to satisfy the instructor
we have done the same thing on several threads in the 16-bit sub-forum
i was interested in teaching the students 2 basic things
1) how to approach problems using assembler
2) how to write code that others can read - lol

[FORTRANS]

Hi Dave,

   Right, I used BCD and the three arrays only as an illustration.
And it would have been pointless to play with AAA without them.
The discussion of how to teach to beginners was one point I
wanted to make.  That programming is fun, even if it keeps
you from sleeping was another.  I tried to show two ways to
solve the problem and the advantages of each.  Is my code
unreadable?  That was not the intent.

Regards,

Steve N.

[dedndave]

Is my code unreadable?

:bg  not your code, Steve - their code
i forget which student it was, but i had to edit the whole file just to understand what they were trying to do
if they didn't take anything else away, i hope it was neat code - lol

[FORTRANS]

Hi,

   Ah indeed, their code often leaves me surprised.  That is
one of the best thing to teach and not always emphasised.
I try to look at my code after a few days just to see if I
glossed over something that will fade from memory if not
commented.  Some code I wrote would be easier to rewrite
than for me to try and figure out.  Oh well.

Best regards,

Steve