New Big Integer library is almost finished

[MathMan]

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

Sorry to hear - that definitely was not what I intended. If you should feel belittled in your effort by me I /sincerely/ apologise.

As I promised to provide a finalised version of ArbInt, please find attached. There is some uncertainty on my side regarding the conversion to/from floating point, as this is bit-fiddlery and I don't have a big-endian machine to test on. On little-endian it seems to work though.

Kind regards,
MathMan

[ad1mt]

Sorry to hear - that definitely was not what I intended. If you should feel belittled in your effort by me I /sincerely/ apologise.

My decision is not caused by you, I had been getting tired of the project for several weeks.
Before your contribution, I already knew that FNX was a much better and faster library than mine.

I believe I could get close to the speed of your code or the FNX code, if I made a big effort to study it & experiment. But at my age I'm not really interested in the doing the amount of work that would be necessary. I have other projects that I want to work on.

Regards, Mark.

[ad1mt]

that definitely was not what I intended...

I'm curious to know what your intention was. You said earlier that you were not interested in making your own big integer library.

I think that the Free Pascal project still needs a basic big integer library that is fast, and easy to use.  I think you would be the best person for that job!

regards, Mark.

[MathMan]

that definitely was not what I intended...

I'm curious to know what your intention was. You said earlier that you were not interested in making your own big integer library.

I think that the Free Pascal project still needs a basic big integer library that is fast, and easy to use.  I think you would be the best person for that job!

regards, Mark.

My intention was to provide a decent base for an arb int library that has been designed/prepared to allow easy integration of advanced algorithms on a base of very fast core routines. You mentioned the timing of Pi calculation with FNX - ArbInt only needs x8 the time of that while still only using schoolbook algorithms! With minimal work Karatzuba multiplication and Jebelan division could be integrated and it would beat FNX hands down.

I had hoped that somebody take it up to do that, if the base had been cleared. But it looks like the interest in a pure Pascal arb int package is not that big.

regards,
MathMan

[ad1mt]

My intention was to provide a decent base for an arb int library that has been designed/prepared to allow easy integration of advanced algorithms on a base of very fast core routines.

So... I will ask directly... why don't you create a basic big integer library for Free Pascal?  It seems like you have already much of the work needed.

The main reason I can't do it is because I don't understand your code (or the code in FNX). I had this same problem when translating the the Henry Warren C version of the Knuth division algorithm. I did a line-by-line translation of the C code, which should have worked, but didn't. Stepping through the failing Pascal code didn't help me understand why the C code worked. I did try to install the MinGW C compiler and debug/step the Warren code, but I couldn't get the MingW compiler to work (it does not help that I absolutely loathe C - but that is a different conversation entirely!)

To understand the Knuth algorithm, I had to "dry-run" it with paper & pencil. (I don't know if "dry-running" is a term that is still in use). And only then was I able to get it working.

You cannot debug code that you don't understand, so I would not be able to debug extra code I wrote that extended yours.

[MathMan]

My intention was to provide a decent base for an arb int library that has been designed/prepared to allow easy integration of advanced algorithms on a base of very fast core routines.

So... I will ask directly... why don't you create a basic big integer library for Free Pascal?  It seems like you have already most of the work needed.

And... answered frankly... I don't want. A more elaborate answer I already tried to give - there are several Pascal-based libraries available and then there also is the FPC binding for GMP. It would be a waste of time from my perspective... And, also frankly, if you consider the feedback in this thread (and the other two on that topic started by you) it indicates the request for such a library within the wider Pascal community is a less then enthusiastic one.

Providing ArbInt as it is was a minimal effort on my side - and the maximum I will invest.

The main reason I can't do it is because I don't understand your code (or the code in FNX). I had this same problem when translating the the Henry Warren C version of the Knuth division algorithm. I did a line-by-line translation of the C code, which should have worked, but didn't. Stepping through the failing Pascal code didn't help me understand why the C code worked. I did try to install the MinGW C compiler and debug/step the Warren code, but I couldn't get the MingW compiler to work (it does not help that I absolutely loathe C - but that is a different conversation entirely!)

To understand the Knuth algorithm, I had to "dry-run" it with paper & pencil. (I don't know if "dry-running" is a term that is still in use). And only then was I able to get it working.

You cannot debug code that you don't understand, so I would not be able to debug extra code I wrote that extended yours.

Fair enough. It then remains as is unless you can convince other people to chime in.

Regards,
MathMan

[ad1mt]

...indicates the request for such a library within the wider Pascal community is a less then enthusiastic one.

That is one of the reasons I'm not going to put more work into this project.

I made the library to solve a problem I had, where I needed big integers to run in a 32bit environment, with a non-Intel CPU, and where I had a substantial amount of code already written which I did not want to totally rewrite. Many of the libraries I looked at required a separate function call for every operation, which is makes it very difficult to use with existing code that uses complex expressions. Some libraries use Intel assembly language, which would not work on my non-Intel CPU.

So I wrote a basic library to serve my needs, and I've now finished it to make it useable by others, if they wish to.

It is not the fastest library available. But it is relatively easy to use, and should run on any CPU and any operating system.

[ad1mt]

I've just made version 5.00 available.
This has each big integer type in a separate unit.
This is likely to be the final version.
The library is available on Github, here:
 https://github.com/ad1mt/Multi-Word-Int-5
Or on my webpage, here:
 https://mark-taylor.me.uk/index.php?page=Software

[srvaldez]

thanks 

[ad1mt]

thanks 

@srvaldez - have you looked at FNX?

[srvaldez]

yes, but it's 64-bit only and uses assembler

[ad1mt]

uses assembler

No... assembly language is optional and can be turned-off.
In fact, I think its turned-off out-of-the-box, and you have set a define to turn it on.

[srvaldez]

thanks, I will give a try 

[srvaldez]

I just tried on the RPI 5 and it works, on the other hand Mparith didn't work

[ad1mt]

checking if a dividend / divisor pair entering a division is the same as last time division was activated

The reason for that is to enable existing code to work without changes... in my experience code like this is quite common:

Code: Pascal  [Select][+][-]

1. d:= (x div y);
2. m:= (x mod y);

And I wanted that code run as fast as possible and not have to be rewritten by the user. The overhead will be small.

I ran some tests comparing your code to mine. Add, subtract & multiply all take approximately the same time (my code is about 25% slower but I'm happy with that).

I did some tests of dynamic arrays vs new/free of pointer to array. It looks to me like dynamic arrays are faster, and they get more faster as the size of the array increases (if that makes sense). The main reason for this is that new of pointer to array requires the memory to be initialised, whereas a dynamic array has its memory zero'd automagically. (There might be a trick to fix this that I'm not aware of). So I don't think my dynamic arrays are a problem.

As you point out, my division routine is my biggest bottleneck.  Can you explain in a nutshell why your division runs so much quicker, please?

I looked at your code, and the only thing I could see is a reference to doing each calculation loop on 2 or 3 limbs/words instead just one (as I am doing). Is that the essence of what you are doing?

I am considering attempting to steal your code and translate it line-by-line to work with my data structures.  But am a bit uneasy about this because of the difficulties I had translating the standard Knuth algorithm from C. Also, would you object if I did this?

Thanks.