Fibonacci Numbers Using Arrays

[ilian007]

we have to start fib sequence from 1 and 1 in arr1 and arr2 (72th digit). ded please keep it as simple as possible for me to be able to understand it....

Thanks a lot :)

[dedndave]

notice that MyArr2 should start with a value of 1, or the thing will loop forever - lol
give this a try....

        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
        xor     ax,ax             ;start with AX = 0 and XOR always clears the carry flag

fibonacci_loop:
        mov     di,71             ;index to last digit
        lea     cx,[di+1]         ;calculates 72 for the loop count

add_loop:
        adc     al,[bx+di]        ;add carry flag to digit from value 1
        add     al,[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
        jnc     fibonacci_loop    ;loop until overflow occurs

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

EDIT - made a couple corrections

[ilian007]

thanks I am going to my lunch break to examine it. Will write after that :)

[ilian007]

DednDave after I examine your code on paper I have few questions.

1. If I want to set 72th element of Myarr1 and Myarr2 to 1 do I have to do that in the begining:
        mov     bx,1
        mov     bp,1
        mov     si,offset MyArr3  ;start with SI = MyArr3

2. adc  al,[bx+di] is equal to : add al,[bx+di] ; add al,carry ? if we had 5 in [bx+di] will have 6 after adc ?

3. Can we change: sub al,dl with after
add     al,[bp+di]
CMP AL,9
JA carry

4.     xchg    si,bx         
        mov     [bx+di],al        ;store the result
        xchg    si,bx

Isnt that equal to : mov [si+di],al ?

5. Printing: is that the way to print the result

Mov SI,72

print:
MOV AX, [SI]
CALL PUTDEC

dec si
cmp SI,0
JNZ print

Thanks

[FORTRANS]

Hi,

1. If I want to set 72th element of Myarr1 and Myarr2 to 1 do I have to do that in the begining:
        mov     bx,1
        mov     bp,1
        mov     si,offset MyArr3  ;start with SI = MyArr3

   Well, you seem to be working with the right end of the array
being the first elements?  Then something like.

Code Select Expand


        MOV     BYTE PTR [BX+71]        ; Set first element of byte array to 1

Or
MyArr1  DB      71 dup (0), 1     ; Set first element of byte array to 1


2. adc  al,[bx+di] is equal to : add al,[bx+di] ; add al,carry ? if we had 5 in [bx+di] will have 6 after adc ?

   Well that depends on what is in AL and if the carry flag is set.
If AL = zero and CF = 1 and [BX+DI] = 5, then 6 yes.
If AL = zero and CF = 0 and [BX+DI] = 5, then 5.

4.     xchg    si,bx         
        mov     [bx+di],al        ;store the result
        xchg    si,bx

Isnt that equal to : mov [si+di],al ?

   Yes, sort of.  You cannot use two index registers to
address a memory location.  (And you can't use two base
registers either.)  So Dave is using BX with the contents of
SI for the access.  So he has to swap an index register with
a base register to have a legal instruction.  (One base register
and one index register is allowed.)

Steve N.

[dedndave]

1) you could use the BX or SI registers
but, the simplest way is to direct address them
Steve is right also - you could initialize the arrays that way
this way, you can put the arrays in the uninitialized data segment and make the program a little smaller

        mov byte ptr MyArr1+71,1
        mov byte ptr MyArr2+71,1

2) that depends on the carry flag
ADC is similar to ADD, but it adds another 1 if the carry flag is set
if the carry flag is clear, it is the same as ADD

3) the SUB/ADD combination i showed you is more efficient
the CMP is replaced by the SUB
the two instructions leave the carry flag in opposite states

4) if i remember correctly, you cannot use [SI+DI] in 16-bit code - i could be wrong, there
i thought one of the registers had to be BX or BP and the other had to be SI or DI
i may be wrong - try it - the assembler will spit out an error if the register combination is illegal
just a note: if you use BP by itself ( [BP] ), it is referenced to the SS stack segment
if you use BP with SI or DI ( [BP+DI] ), it is referenced to the DS data segment

5) PUTDEC would be slow - faster to print the whole string at once
write a loop to convert the final value to ASCII numeric characters
then, use PUTSTRNG with CX = 72
as you recall, SI holds the address of the final value
i think PUTSTRNG uses DX, so.....

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

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

        mov     cx,72
        call    PUTSTRNG

Steve beat me, that time - lol

[ilian007]

Steve, dedndave my level of programming cant handle more efficient code I need more understandable code for me. CMP AL,9 looks more clear in my eyes. and Putdec is well known command. I tried using your methods and program to generate the 72th fibonacci number which CX should point to (the 72th Fibo number). It should be(49845 40118 79264). I can not get to that result and since I dont understand many of the procedures I can not see/fix what the problem is. I tried using ascii it prints $#!@$ instead of number. with putdec it prints number but not any of those. If I change CX to 8 it should print - 21 instead it prints zero ...  It is all good and efficient with all the carry's and and moving through the indexes but cant make it work that way :((

72 (15 digits) :
49845 40118 79264
8 (2 digits) :
21

[dedndave]

ohhhhhhhhhhhhhhhhh - lol
i wrote the loop so it would generate numbers until it overflows
i did not know you wanted the 72nd one - lol
so - if you set MyArr1 = 1 and MyArr2 = 1, MyArr3 on the first pass would be the first one ? or the third one ?
usually, i see it starting at 0,1,1,2,3,5,8,13,21.......
if the answer is only 15 digits long, why are we adding 72 digit numbers ? - lol
give me a little time - let me write a program for it.....

[ilian007]

I did set CX static just to make the program work. CX will change from the input KBD.... User will ask for 22nd fibbo number and program has to generate and print that number on the screen. Program has to overflow if number goes over 72 digit ... and to generate message for it.. 

in fact we can calculate if arr1[bx] + arr2[bx] = 0 to stop and to print... but I  am not looking for speed just to work so if it adds zeroes it doesnt mather to me :) speed is not issue here working is issue :P

first numbers should be 1 and 1 in myarr1 and myarr2. the user will input number like : 22 ... it will go to CX throug getdec. and means user wanth 22nd fibonacci number. and the program has to show him: 22nd Fibo number ... in the way teacher set 1 1 first number should be 2 ... I guess ... I was looking that one for reference : http://www.fullbooks.com/The-Fibonacci-Number-Series1.html

He wants us to tell him what will be the max fibonacci number we can input in 72 digit without overflow. In the website is says 346th fibo number displays in 72 digit and 347th overflow ...

[dedndave]

ok - lemme play with it a little bit.....

[ilian007]

found that calculator. It works like the previous website + 1
http://www.calcresult.com/maths/Sequences/expanded_fibonacci.html

[dedndave]

do you want to generate a list like that ?
or just the one value ?

[ilian007]

just one value the last one in Arr3 ...Teacher said user should try different numbers as input til program say: overflow occured. please try smaller number. pleaseeee as simple as possible no fancy jumps through the indexes and registers :)

[dedndave]

i found a boo-boo - lol
i thought that [BP+DI] used the DS segment
i was wrong - lol - it uses the SS segment
it has been a while since i wrote any 16-bit base index code - sorry about that
that line has to be changed...

        add     al,ds:[bp+di]     ;add digit from value 2

[ilian007]

it should be like:

CX = some number from KBD
Loop CX

loop DI
for DI=72 to 0 do
Arr3 = arr1 + arr2 + carry  ----> somehow have to move values from arr2 to arr1 and arr3 to arr2 to work for fibonacci ...

if arr3>9

arr3=arr3-10
carry=1
DI=DI-1
else
carry = 0
Di=di-1


SHould be something like that