Is there such a thing for FPC?
I need it for my project and I have found is this:

http://pauillac.inria.fr/~quercia/cdrom/bibs/numerix.tar.gz

Which seems unmaintained, in french, has horrible API, and is actually a wrapper around C library.

Seeing as FPC contains at least three expression-parsing-and-evaluation libraries, I think one "long arithmetic" unit would not hurt.

So, should I write one or did I just not searched in the right place?

There is one in the contributed units:
mpcalc from Franco Milano. It has been around for quite some time.

Michael.

Michael Van Canneyt wrote

> So, should I write one or did I just not searched in the right place? There is one in the contributed units: mpcalc from Franco Milano. It has been around for quite some time.

Oh, indeed, thanks. I missed it when I looked there. However, this unit has non-standard non-free license, and both the interface and source is, to put it mildly, not beautiful ;-)

There is my NX library (still alpha) at

htpp://www.ellipsa.net/

I recently added units that allow to work with elliptic curves over gf(3**n) fields.

There is also the library of W. Ehrhardt at

http://home.netsurf.de/wolfgang.ehrhardt/mp_intro.html

Best,
mm

m2 wrote

htpp://www.ellipsa.net/

http://www.ellipsa.net/

I've missed the beginning of the thread, so ignore if not relevant.

There is a very nice library: GNU MP (multiple precision arithmetic library) which supports arbitrary precision floats, arbitrary size integers and arbitrary size rational numbers. Also, the API is really well done:

http://gmplib.org/index.html

I've used it for years and it is really reliable. It is written in pure C, so you can compile it on whatever machine you have. I am not sure if it is optimized for GPU cards, etc.

If anyone needs native compilation on NT, I have adapted an older version for compilation with Visual Studio, along with pascal interface. It goes standard on most linux distributions (libgmp.so)

Cheers,
Peter Popov

Now, this code is much more pleasant to read ;-)
A few questions:
1) The license seems to be LGPL, but there is gpl-3.0.txt file in the doc folder.
Are some parts under the GPL?
2) Why no operator overloading?
3) Finally, and relevantly for this list,
should something like this be included into FPC?

Also

http://www.delphiforfun.org/Programs/Library/big_integers.htm http://www.delphiforfun.org/Programs/big_factorials.htm http://www.delphiforfun.org/Programs/Library/BigFloat.htm http://speleotrove.com/decimal/
http://www.mpfr.org/
http://gmplib.org/

and links obtainable from these pages .

Thank you very much

Mehmet Erol Sanliturk

3) Finally, and relevantly for this list, should something like this be included into FPC?

Imo in principle, yes, but:
- simpler than NX library in the sense of less functionally, putting something like NX library in FPC is too much imo.
- cross platform
- FPC rtl compatible license

BTW: Maybe such an effort can improve fmtbcd as well. Or is it fundamentally flawed?

Agree. But perhaps NX author would be willing to produce 'NX lite' library?

- cross platform

This should not be a problem for such code.

BTW: Maybe such an effort can improve fmtbcd as well. Or is it fundamentally flawed?

Wow, so FPC does contain an arbitrary-precision arithmetic unit after all. No wonder I did not find it under such obscure name. I do not think it is "fundamentally" flawed, just, as noted in the comments, suitable more for compiler debugging then for it's primary purpose. It can be improved by removing 50% of code and 99% of ifdefs, but I guess it is easier to just rewrite it.

Dear Alexander S. Klenin ,

3) Finally, and relevantly for this list, should something like this be included into FPC?

I think , in the long run such a facility may be very useful , because some times it is becoming necessary to resort such techniques .

In those days I am working on my Fortran programs to improve them .

There is a test matrix : Finite segments H ( n ) of Infinite Hilbert matrix : h ( i , j ) = 1 / ( i + j -1 ) , i = 1 ,, n , j = 1 ,, n .

This is a very ill-conditioned matrix . In double precision it is not possible to invert around H ( 20 ) because determinant becomes very small .

In Free Pascal , by using Extended arithmetic , epsilon as 1.0E-777 , it is not possible to reach H ( 25 ) .

This means that in such situations it is necessary to resort multiple precision arithmetic .

Personally , I will use an existing multiple precision Fortran package ( I will study contents of www.netlib.org ) , or
If I can not find a suitable one , I will write such a Fortran set of subroutines .

For the Free Pascal community , having such a facility at hand during solving numerical analysis problems would be very useful .

Another important problem is decimal floating point arithmetic , especially for financial or legally required computations . For example , around 1970 , in IBM System/360 , there was BCD : Binary Coded Decimal . ( I do not know previous state prior that date ) .

Thank you very much .

Mehmet Erol Sanliturk

It is LGPL. The gpl.txt file is needed because the lgpl.txt one modifies some of its parts but not all of them.

2) Why no operator overloading?

Because it is not necessary and it slows a little down computations. Moreover, the ways FPC and DELPHI allow operator overloading are totally different.

mm

Do you need integer or floating point ?

-Michael

Michael Schnell wrote

Do you need integer or floating point ?

Fixed-point, actually.

I think , in the long run such a facility may be very useful , because some times it is becoming necessary to resort such techniques .

Hmm there is a lot other basic mathematical stuff that is equally important and IMHO should be provided in separate Libraries (such as Jedi). (e.g. Primes, Matrix operation, geometry, ...)

-Michael

In the "Deutsches Lazarus Forum" there was a project called "GNURZ" providing this. It was quite promising and I provided some ASM-optimization for it.

Here the original Author implemented a "Karazuba" multiplication, that is a lot faster than the standard Multiplication algorithm, when very long numbers are handled (see Wikipedia on Karazuba).

Combined with the ASM optimization for the basic functions this seems to be a very fast library.

Unfortunately the original Author has stopped to work on the project and nobody seems to be inclined to do some necessary cleaning up of the code to allow a community based development.

The license seems to be no

It is Karatsuba, actually (he is Russian professor). I studied this vaguely remember that although it is asymptotically faster than FFT, implementation
is complicated and the time constant is higher, so FFT is used in practice except
for really large problems.

Unfortunately the original Author has stopped to work on the project and nobody seems to be inclined to do some necessary cleaning up of the code to allow a community based development.

Unfortunately, I do not read German, so I it is hard for me to understand, and this code even uses German procedure names (!). If someone will at least provide an english translation, I might help with code cleanup
to get the code ready for FPC inclusion.

For now, NX library with LGPL license fulfills my needs.

The license seems to be no , although getting explicit license from the author is always preferable.

It is Karatsuba, actually (he is Russian professor).

:) Thanks :)

In this application the make-up of the algorithm (compared to the plain old "school" multiplication) in fact is a little bit similar to how FFT works (compared to doing straight DFT), but regarding to what it results in here it has nothing to do with what a Fourier Transform results in. But like FFT it's speed is O(n), while the speed of plain old "school" multiplication and DFT is O(n²).

In fact it's not very complicated, it's done as recursive function calls that do partial multiplications for half of the word cont. If the word count gets below a predefined limit, normal multiplication is done, as here same is faster (and the recursion level is limited).

If someone is inclined to manage this as an open source project, I'll be happy to help....

Good, although getting explicit license from the author is always preferable.

He certainly will provide this (e.g. LGLP) when the project is out of Alpha.

-Michael

here it has nothing to do with what a Fourier Transform results in. But like FFT it's speed is O(n), while the speed of plain old "school" multiplication and DFT is O(n²).

I suppose in fact it's o(n * ln(n) )

-Michael

It is O(n^log 3) ~ O(n^1.58)

Michael Schnell wrote

see Wikipedia on Karazuba

Perhaps you should do this too ;-)
I would also recommend wolfram's world article, since Wikipedia one is lacking in math details.

Some commercial companies may object to LGPL Version 3.0 because it requires supply of linked program as a linkable library to other programs also .

This issue requires further study .

A separate package is not a problem but inclusion it into FPC RTL is NOT compatible
LGPL Version 2.

Thank you very much .

Mehmet Erol Sanliturk

If it were the only problem, I always could swap two commas and release a LGPL 2 version ;-) but, as Florian said, NX is too complicated for FPC. Moreover, NX can only works with Intel/AMD processors.

mm

As a matter of fact, this is the other way. FFT is asymptotically better than Karatsuba. Karatsuba is good for integers in, say, the range 800..8000 bits. Then Toom-3 is better than FFT up to, say, 80000 bits. (That's why I didn't code FFT in NX, I never needed to work with such monsters. 80000 bits ~ 24000 decimal digits.)

mm

(That's why I didn't code FFT in NX, I never needed to work with such monsters. 80000 bits ~ 24000 decimal digits.)

I don't think > 8000 bits is often used and Karatsuba is not very complicated code in Pascal (provided you do have a decent "simple" multiplication and addition to call from the Karatsuba algorithm.

Does NX have Karatsuba ?

-Michael

Yes, it has. And Toom-3 too.

mm