New Big Integer library is almost finished

[ad1mt]

I've just made version 4.91 available.
This has a minor bug fix, and works with the 64bit switch set in 32bit compiler.

Setting the 64bit switch gives a significant speed increase with the 32bit compiler.

NB - on a 32bit Raspberry Pi, with the 64bit switch set in the 32bit compiler, and with -O3 optimisation set, the code crashes. The problem does not happen with -O2 optimisation. I will investigate further, and might be able to fix this later.

[ad1mt]

I've just made version 4.92 available.
This has several minor bug fixes, and slightly faster multiply/add/subtract algorithms for the Multi_Int_X2/3/4/5 types.

[srvaldez]

👍

[MathMan]

Hello ad1mt, srvaldez,

@ad1mt: You once said that you can only handle donations to you project in source and that you had a hard time considering the division routines I provided earlier. I can see that you are really into this development and already have plans for further things like efficient multiplication / division, etc.

So I sat down last week, took your version 4.85 and modified it, paving a way for easier developments from your side in the future. The result pls find attached

* unit ArbInt which contains most of what is in 4.85 (only missing the assignments to/from FP and from string)
* a command line unit test for ArbInt
* a command line benchmark utility
* an implementation of Pi-Chudnovsy

The unit only implements schoolbook O( n^2 ) algorithms, but is designed in a way that efficient variants can be integrated easy. I did my best to test the 32 bit support and it seems working for me. However I don't have a native 32 bit machine so can not be 100% sure. There are a lot of comments, on design decisions etc., some 'todo' which you could address ...

@srvaldez: Maybe you want to test the pi program?

Cheers,
MathMan

[srvaldez]

hello MathMan 
that's quite fast performance, 100,000 digits in about .67 seconds 👍

[ad1mt]

hello MathMan 
that's quite fast performance, 100,000 digits in about .67 seconds 👍

Thanks. I've re-designed the add/subtract/multiply routines with faster algorithms. Although each one is only about 50-75% faster, there seems to be a greater cumulative speed-up when several routines call each other repeatedly.

Misunderstanding there!  I thought you were talking about my improvements   

[ad1mt]

Hello ad1mt, srvaldez,
So I sat down last week, took your version 4.85 and modified it, paving a way for easier developments from your side in the future. The result pls find attached
Cheers,
MathMan

Thanks for your contribution, I will have a look shortly.

[ad1mt]

I've just made version 4.93 available.
This has faster decimal ansistring conversion for the fixed-size Multi_Int_X2/3/4 types, and some code tidy-up.

[ad1mt]

I can see that you are really into this development and already have plans for further things like efficient multiplication / division, etc.

Yes...  what started as a quick-and-dirty big-integer solution to another program I was working on, has turned into a project that is now almost bigger than the other program.

However, I am now getting tired of this project, and am thinking that its time to stop soon... unless anyone finds more serious bugs, or has suggestions that would be a big improvement.

[ad1mt]

The result pls find attached
The unit only implements schoolbook O( n^2 ) algorithms, but is designed in a way that efficient variants can be integrated easy.

I've just looked at your code, and I seem to remember you sending me some code in a previous conversation.
It looks like you did not just design/write this code in the week or so... it looks like a lot of work has gone into it.
Have you designed/written your own big integer library? If so, is it freely available?

If the answer is yes (you have designed a library) and no (it is not freely available), then I would like to propose that a few Free Pascal programmers here get together to design/write a basic big-integer library that can be donated to the Free Pascal project. That was my intention, but it appears that there are better programmers here than me, that could do a better job than I have.

Addendum: I timed your pi_chudnovsky program using your big-integer library, and again using my library... yours ran in 0.9 secs, mine ran in 53 secs... x54 faster... I'm very impressed!  Your code makes my big-integer library redundant.

regards, Mark.

[MathMan]

I've just looked at your code, and I seem to remember you sending me some code in a previous conversation.
It looks like you did not just design/write this code in the week or so... it looks like a lot of work has gone into it.
Have you designed/written your own big integer library? If so, is it freely available?

I have about a decade worth experience in that specific matter - more or less started out as a complete newbee on arbitrary precision arithmetics in 2014. However my objective was to understand the math & algorithms behind it - so this stuff is a pet project on my side. I don't have 'a library', just a pile of routines doing as I please to do some research in number theory etc. So yes, roughly 50% of 'ArbInt.pas' is from that resources - the core routines, so to say. The rest, together with the unit test & the benchmark tool are new.

If the answer is yes (you have designed a library) and no (it is not freely available), then I would like to propose that a few Free Pascal programmers here get together to design/write a basic big-integer library that can be donated to the Free Pascal project. That was my intention, but it appears that there are better programmers here than me, that could do a better job than I have.

I did not publicise anything, and have no intentions to do so besides addressing the few open points in 'ArbInt' - assignments to/from floating point and from strings. There are already several libraries available in the public domain and I don't feel inclined to add to that. What I provided was meant, as stated in my previous post, as a decent starting point for further development - of which there is a lot left! You can of course ask on the forum if somebody wants to join in - feel free to then use 'ArbInt' as it was intended. Don't know if I'm a "better" programmer than you (a metric for that anyway eludes me), but I give you that I'm more experienced in this particular topic.

Addendum: I timed your pi_chudnovsky program using your big-integer library, and again using my library... yours ran in 0.9 secs, mine ran in 53 secs... x54 faster... I'm very impressed!  Your code makes my big-integer library redundant.

That is in line with the measurement I did on my own machines - around a factor of 50. Whether your library is redundant I can't say. From personal experience, as I have made pretty much every mistake that can be done handling long integers, I can say that your basic design decisions do at least make progress in it hard.

Cheers,
MathMan

[srvaldez]

hello MathMan
conversion from ansiString to tArbInt would be a great addition to ArbInt 

[ad1mt]

From personal experience, as I have made pretty much every mistake that can be done handling long integers, I can say that your basic design decisions do at least make progress in it hard.

From your experience, can suggest why your code runs so much faster than mine?
Or your algorithms faster? Or is it the due to your using pointers to allocated memory vs my using dynamic arrays?
Or maybe it both factors?
Thanks.

[MathMan]

From personal experience, as I have made pretty much every mistake that can be done handling long integers, I can say that your basic design decisions do at least make progress in it hard.

From your experience, can suggest why your code runs so much faster than mine?
Or your algorithms faster? Or is it the due to your using pointers to allocated memory vs my using dynamic arrays?
Or maybe it both factors?
Thanks.

It is a mixture of many things, that add up. The algorithms used are /not/ fundamentally different - it is schoolbook algorithms in both cases. But looking closely at the way they are implemented one can see that in your lib this needs 2-4 times as many instructions to i.e. do add / sub / mul for a single limb (32 or 64 bit basic block). Division is worse - there the difference on the basic level is >10 already I assume.

Then you had some slack carried around, like repeatedly checking how many limbs are actually in use - checking if a dividend / divisor pair entering a division is the same as last time division was activated - various assignments between long integers in the course of calculating an operation ... The last one is a major contributor I now understand, as your computer is very busy shuffling data around instead of working on it. I tried hard to avoid this in my implementation and spent two days just digging into how operator overloads work in Free Pascal.

All this adds up, but to different levels for different operator overloads. You would need to measure operations individually to understand how much - and I'm afraid division will come out last with great distance.

Cheers,
MathMan

[ad1mt]

I've decided I've done about the best I can with this project.
Thanks for the bug reports and suggestions.

if you like playing with big integer libraries and big numbers, I recommend looking at the FNX library for Free Pascal. In my opinion, its the best library I've found so far, apart from the fact that it requires 64bit integers.  Its also easy to use.  Chudnovsky pi calculated to 1 million digits takes 14 seconds!  I haven't checked if all the digits are correct!   

Regards, Mark.