An astronomical number

[daydreamer]

I wish I had one of the working programs using matrix-exponentiation so I could figure out (by disassembling it) how they can achieve the precision required to generate all those Fibonacci numbers within the "short" times reported.

Maybe can find out with help of compiler that has auto vectorisation?
Because I noticed they use vector  instead of array
http://masm32.com/board/index.php?topic=7708.0
Great raymond 
How slow is division of huge numbers compared to add BCDs?
Jack great showing its enough post 20 first and 20 last digits and compare vs other Algos

otherwise BCD savefile speed 16 millis,zipped shows 93% compression

[jack]

raymond, is your PC 64-bit?
do you implement your own decimal-adjust or do you use the x86 DA which is not available in x64 ?
I think that high-level language that supports inline-asm would be better than using asm only, you could write most of the code in the HL and use inline-asm only in critical parts

[daydreamer]

raymond, is your PC 64-bit?
do you implement your own decimal-adjust or do you use the x86 DA which is not available in x64 ?
I think that high-level language that supports inline-asm would be better than using asm only, you could write most of the code in the HL and use inline-asm only in critical parts

I tested Inline asm before and compiler can break SIMD code with auto pad between variables
Looks like rosetta-code programs are relying on fast biginteger libraries
So develop fastest math library seem like a better way

[jack]

decimal arithmetic instructions are not available in x64 and I think that the DA instructions only work at the byte level so BCD arithmetic is going to be slow, you could probably write your own decimal-adjust routines and use bigger chunks instead of byte but it would also make shifting more complex
binary arithmetic is fastest and easier to implement at the cost of more complex input/output routines

[raymond]

I've been trying to convert my BCD algo to a binary one for implementing Jack's equations. Initial indications are that it would be significantly faster (by a factor of maybe 50) because of the large reduction in the number of multiplications.

I still don't know the eventual cost of conversion to decimal digits. Will let you know when I succeed.

[jack]

Raymond, are you going to share your code?
I also am interested in big-num arithmetic, I did mine in FreeBasic but the algorithms used are very basic/unsophisticated
in my search I found some information that might be useful to you or others

A Multiple-Precision Division Algorithm http://dmsmith.lmu.build/MComp1996.pdf

Simple Algorithm for Arbitrary-Precision Integer Division https://youtu.be/6bpLYxk9TUQ

Arithmetic Operations Beyond Floating Point Number Precision https://ia800403.us.archive.org/10/items/arxiv-1009.5911/1009.5911.pdf

Arbitrary Precision Arithmetic https://www.youtube.com/playlist?list=PLGI5yUFVsUkWO26oPixUNYwKick1LxiWR

Git repo https://github.com/nickelcarbide/arbitrary-precision-arithmetic-demo

BigInteger by Richard/Stephan https://github.com/stephanbrunker/big_integer

[raymond]

Thanks for all that info Jack.

I developed my own multi-precision multiplication algo as if I was doing it with "paper & pencil".

I must admit it would have been a lot easier in 64-bit instead of 32-bit, having access to many more registers. BUT, I have not yet converted (and most probably will not at my age  ). I'll clean up my code and eventually share it.

[daydreamer]

decimal arithmetic instructions are not available in x64 and I think that the DA instructions only work at the byte level so BCD arithmetic is going to be slow, you could probably write your own decimal-adjust routines and use bigger chunks instead of byte but it would also make shifting more complex
binary arithmetic is fastest and easier to implement at the cost of more complex input/output routines

I have debugged thru AAA, to make AAA macro which can use other registers than being restricted to Al,to better possibilities for unroll
I trying SIMT solution, which uses one thread do the slow print,fprint,slow conversion in,other threads calculate
But if you have many cores,you can try solution execute many DA in parallel, might be easier if you lack SIMD skill
If you only have 32bit SSE2 128bit math might help

also wondered about use stack kinda recursion or just calculate and push results on stack, because Createthread support custom bigger stack than standard 1MB

[raymond]

Got the binary algo working perfectly. Computing F-1000000 confirms the last 9 digits reported by others in the "rosetta code" link.

That number contains 21696 dwords and took 1.4 seconds to compute on my 10 year-old laptop. However, it took an additional 3.5 seconds to produce the remainder of 1000000000 (i.e. the least significant 9 decimal digits) following 21695 divisions. My estimate is that a bit more than another 200,000,000 divisions may be required to arrive at the 9 most significant digits of that number with 32-bit arithmetic.

[jack]

congratulations Raymond 
did you use identities or the addition of the previous 2 F's ?
I suspect that you will find a much faster way to do the conversions

[daydreamer]

Got the binary algo working perfectly. Computing F-1000000 confirms the last 9 digits reported by others in the "rosetta code" link.

That number contains 21696 dwords and took 1.4 seconds to compute on my 10 year-old laptop. However, it took an additional 3.5 seconds to produce the remainder of 1000000000 (i.e. the least significant 9 decimal digits) following 21695 divisions. My estimate is that a bit more than another 200,000,000 divisions may be required to arrive at the 9 most significant digits of that number with 32-bit arithmetic.

Congrats 
Wonder if there is faster way to convert binary-> ascii?

[jack]

I did a test with my arbitrary floating-point routines, the binary implementation took 5 seconds to compute F(4784969) but took 1515 seconds to print to console
the base 100000000 implementation took 18 seconds to compute and .16 seconds to print
the test was done in 64-bit, in 32-bit it took nearly 3 times as long, the Fibonacci numbers were computed using the identities posted earlier in this thread

[raymond]

My apology for the error in my last post. It really took only a few additional microseconds to compute the 9 least significant digits of F1,000,000.
I finally got my bearings straight and managed to compute the most significant digits, matching reported data in the Rosetta code link. My timing for that was still 1.4 secs for computing the digital number and an additional 2.0 secs for the most significant 17 digits.
Cleaning up my source code is underway.

[daydreamer]

Great raymond 
I want to try find faster binary -> ascii
Jack saving buffer to file faster
I ran my program two hours yesterday to try get all 20 lowest digits like in the rosetta code, forgot 2^16 and haven't reached 2^64, only reached f _16*2*2^32 So far
Checked all are correct digits

[jack]

I look forward to your code Raymond