Dear Math and FPU-Experts - help needed!

[cobold]

Cheers!

There's an interesting website with hundreds of Math-Problems to solve:
http://projecteuler.net/index.php?section=problems&id=104

I solved a few of the easier ones - no problem. But AARRRGHH!!!! - problem 104, I know _exactly_ how to solve it, but how shall I calcalute the 2749th Fibonacci-number with 32 or 64 bit!
It doesn't work - the numbers are simply too big!

I'll post my work in progress for problem 104 (code is a mess - I just changed generation of fib-sequence from 32 to 64 bit, via fpu but aaah!
k = 47  F(k) = 2971215073 is biggest Fib with 32bit-arithmetic....
k = 98  F(k) = 11810432329172123648 is the biggest Fib that one can generate with 64bit!!
Will this end up in manually adding 256,512 or 8192bit-fields???
Ideas? Help? (No code needed but perhaps a hint how this could be solved without using BIGBITFIELDS?

Code Select Expand

comment *+++++++++++++++++++++++++++++++++++
                EULER104.ASM
           
http://projecteuler.net/index.php?section=problems&id=104

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn1 + Fn2, where F1 = 1 and F2 = 1.
It turns out that F541, which contains 113 digits, is the first Fibonacci number
for which the last nine digits are 1-9 pandigital
(contain all the digits 1 to 9, but not necessarily in order).
And F2749, which contains 575 digits, is the first Fibonacci number for which the
first nine digits are 1-9 pandigital.

Given that Fk is the first Fibonacci number for which the first nine digits AND
the last nine digits are 1-9 pandigital, find k.


+********************************************
include c:\masm32\include\masm32rt.inc

.data
align 4
    k         dd ?
    Fk        dq 1
   
; -------------------------------------------------------------------------

.code   
start:
    mov ecx,1                   ; k
    fild Fk
    fild Fk
    call PrintF
align 4
    .while ecx <= 100
        ;add eax,ebx             ; eax(F3) = F2+F1
        fadd st,st(1)
        fxch st(1)
        fistp qword ptr[Fk]
        fild Fk
        inc ecx
        call PrintF
    .endw
   
    inkey
    invoke ExitProcess,0

PrintF proc
    pushad
    mov k,ecx
    ;mov Fk,ebx
    print "k = "
    print ustr$(k),9
    print "F(k) = "
    print uqword$(Fk),13,10
    popad

    ret   
PrintF endp
end start



[raymond]

I'm absolutely certain that you are going to enjoy that site for a long time if you like solving math problems. There are presently 202 problems with 5 more relatively easy ones scheduled to be published the first week of September.

As a side note, I'm a co-author of that particular problem #104 (and currently one of the administrators on that site). One of my tutorials could probably help you. See:
http://www.ray.masmcode.com/

I have to leave the rest to your imagination and logic.

[cobold]

Thanks very much Raymond,
I'll take a look at your side - you see I mentioned I don't want any code - it was just that somehow I "feel" this should be possible to solve with standard-artihmetic? Anyway - I'll solve that one!

Thks again for the link - and wow! how small is the world! Never thought that you are one of their authors!!
Good Work

rgds
cobold

[cobold]

Raymond?

in the last few hours i made myself some BCD-routines. BCD !!!! Raymond, am I on the right track?

Now I'm too tired to solve problem 104 in the next few hours, but the routines work, I have tested them:
Now I know (thanks to the link you posted - which brought me on BCD-track:
F541 =
16212329273937944282832817223024176844162155653520813722196490508943999028119788
42493025898332777796978839725641

and hihi - I'm a little bit proud about myself - my bcdadd proc definitely works correct, as the last 9 digits of F541 are 'pandigital', right?

Thanks again for the link - and thanks for your work!
----
btw.
Of course I know that I have to optimize my routines (bcdadd, bcd2a) first. But are there only opcodes 'daa' and 'das' - what about multipliying and dividing?

[hutch--]

 :bg

ME count with fingers, eeeny, meanie, miney moe etc .... Lucky computers do it OK.  :P

[FORTRANS]

cobold wrote:

But are there only opcodes 'daa' and 'das' - what about multipliying and dividing?

   If you want to continue using BCD, there are the packed BCD
instructions; AAA, AAS, AAD, and AAM.  But ADD and ADC will
do arbitrary length addition in binary.  BCD should work just fine,
and be easier to debug/visualize.  Though a bit bigger and slower.
Have at it.

   Raymond, nice site!  colbold, thanks for the pointer.  Both,
GrUmph, may have to try some of those.

Regards,

Steve N.

[Mark_Larson]

  sounds cool :)  I am going to work on it as well.

[RuiLoureiro]

Hi  all,
     i like math but i have no time to waste following  Fibonacci "things".
     
     i prefer hutch optimisation methods: eeeny, meanie, miney   AND SO ON !!!
     
Have a lucky day
Rui

[Mark_Larson]

Hi  all,
     i like math but i have no time to waste following  Fibonacci "things".
     
     i prefer hutch optimisation methods: eeeny, meanie, miney   AND SO ON !!!
     
Have a lucky day
Rui

  Yea you got to watch those Aussies, they really are on the bleeding edge of code optimization. 

[cobold]

me:
But are there only opcodes 'daa' and 'das' - what about multipliying and dividing?
hutch:
ME count with fingers, eeeny, meanie, miney moe etc .... Lucky computers do it OK. 

Do you want to ridicule me, or do you want to point out that having good 'add-proc' and 'sub-proc' is what counts?
I believe the latter, because I know you are not a person ridiculing people who want to learn.
Excuse me, if I ask so silly(bluntly) but english is not my mother-tongue, and I had some trouble to figure out the meaning)
------
Rui:
    i like math but i have no time to waste following  Fibonacci "things".

I don't consider it a 'waste of time' to go a little bit into the basics of math and algorithms (if time allows for it  :U)
On the contrary, I think I'm a very practicallly oriented person, but I have learned that a deeper understanding of underlying concepts may/can/will help you designing better/shorter/faster algos. After all, f.ex. it's not trivial task to calculate with 500+++diigit numbers on a system that doesn't support that natively.

Mark Larson:
Yea you got to watch those Aussies, they really are on the bleeding edge of code optimization. 

I cannot say yes to this AND cannot say no to this, because I don't know so many Aussies!  :bdg
Certainly, the abitlity to learn (theory) and DO(praxis) depends on the assistance from your environment and your personal comittment; nationality is not the factor, imho!  :wink

[raymond]

and hihi - I'm a little bit proud about myself - my bcdadd proc definitely works correct, as the last 9 digits of F541 are 'pandigital', right?

Congratulations.

But are there only opcodes 'daa' and 'das' - what about multipliying and dividing?

You cannot multiply nor divide with packed BCDs. You can only do it with unpacked BCDs. Look at the other instructions in the tutorial.

If you want to continue using BCD, there are the packed BCD
instructions; AAA, AAS, AAD, and AAM.

Those are instructions for UNPACKED BCDs.

P.S. I think "eeeny, meanie, miney moe" is part of Big Crooked Digitals. :bdg :bdg

[PBrennick]

Hey, it's all ones and zeroes to me? If you can make a two, be proud of it.

-- Paul

[dsouza123]

I used base 1 000 000 000 ( 1 billion ), with each dword holding 9 digits
and the array size used, 2048 dwords, it can handle a fibonnaci number with 18432 digits.

It does checking to prevent overflowing bounds.

Mixed pascal/masm pseudo code.

Code Select Expand


     for i := 0 to max do
       a[i] := a[i] + b[i]

     clc
     for i := 0 to max do
       adc a[i]
       if a[i] > 999 999 999 then
         a[i] := a[i] - 1 000 000 000
         stc
       endif;
     endfor;

     if c then
       inc max
       mov edx, max
       shl edx, 2
       a[max] := a[max] + 1
     endif;

[attachment deleted by admin]

[RuiLoureiro]

I don't consider it a 'waste of time' to go a little bit into the basics of math and algorithms (if time allows for it 

Hi cobold,
              Yes, developing math and algos is a good task and somebody should do it if they like
               and have time.
               But now i want to understand other things about windows and i have no time to math.
               More: i guess that "ME count with fingers, eeeny, meanie, miney moe etc" is a way
               to play with this issue and nothing more. It´s a funny expression.
Rui

[FORTRANS]

If you want to continue using BCD, there are the packed BCD
instructions; AAA, AAS, AAD, and AAM.

Those are instructions for UNPACKED BCDs.

Oops, indeed.  Packed/Unpacked, Decimal/ASCII.

Sorry,

Steve