Recent

Author Topic: Large/Big Integer Library in pure Pascal  (Read 8995 times)

MathMan

  • Sr. Member
  • ****
  • Posts: 325
Re: Large/Big Integer Library in pure Pascal
« Reply #30 on: July 29, 2022, 02:13:14 pm »
I can maybe also provide some comments on capabilities of individual packages (if this is desired), as I took a look at each of them over time.

That would be appreciated.

Here we go - first some additional Pascal implementations I am aware of

BigInt: v1.8 - Franco Milani
http://spazioinwind.libero.it/frm/software

Though this is a Pascal source >90% are coded as x86-32 Win32 assembler routines - memory served me badly on ths one.

-----------

HugeInt: v5.34 - David J Butler
https://github.com/fundamentalslib/fundamentals5

Part of a much larger library but the unit can be used self-contained.

-----------

LongMathForPascal: Zsolt Szakaly
https://github.com/zsoltszakaly/longmathforpascal

A quite recent contribution (2021) - unfortunately it does not support any efficient algorithms and becomes slow very fast.

-----------

GInt - Walied Othman
https://github.com/SnakeDoctor/FGInt

Again part of a larger library but can be used self-contained.

-----------

I also promised to provide some comments on the packages. I'll start with BigIntegers and MP-ARITH today and will cover more in the coming days - I have to ressurect some old tools and buried knowledge, so it takes a bit of time. Of course the following is subjective, and I'm explicitely not going into the topic of licenses ...

BigIntegers - Velthuis

- Functionality
  - supports 32/64 bit, little- & big-endian
  - class implementation with operators & functional replicants
  - dynamic sizing and immutability
  - late binding
  - solid error handling
  - solid set of operators - arith, bitops, comparisons, expl & impl conversions
  - some number theory - gcd, modinv, mulmod, pow, powmod, sqrt+remainder, n-root+remainder
 
- Algorithms
  - basecase multiplication only 33% slower than best known pure Pascal
  - efficient multiplication: Karatsuba, Toom3
  - efficient squaring: Karatsuba
  - efficient division: Burnikel-Ziegler
  - div&cong base conversion (from binary to arb base only)
  - euclidean GCD
 
- Issues
  - tricky to convert to FPC
  - memory management degrades efficient algs on larger sizes (speed reduced by 5)
  - default thresholds & missing tool for auto detection
  - sqr-schoolbook = mul-schoolbook
  - missing efficient GCD algorithm
  - missing efficient mod algorithms (Montgomery, Barrett)
  - the way asm-enhancements are integrated could be improved (subjective)
  - testing depth & breadth could be improved (subjective)
 
- Nice things
  - there is also BigDecimals, BigRationals & BigFloats

-----------

MPArith - Wolfgang Erhardt
 
- Functionality
  - supports 16/32/64 bit, little- & big-endian
  - pure functional implementation
  - dynamic sizing
  - solid error handling (function results or exceptions)
  - extensive set of functions - arith, bitops, comparisons, type conversion, base conversion
  - extensive number theory - gcd, modinv, mulmod, pow, powmod, sqrt+remainder, n-root+remainder, and a lot more

- Algorithms
  - basecase multiplication only 33% slower than best known pure Pascal
  - efficient multiplication: Karatsuba, Toom3
  - efficient squaring: Karatsuba, Toom3
  - efficient division: Burnikel-Ziegler
  - div&cong base conversion (both ways)
  - efficient GCD
  - efficient modular ops: based on Montgomery & Barrett reductions
  - efficient roots: quadratically converging

- Issues
  - default thresholds & missing tool for auto detection
  - Burnikel-Ziegler efficiency degrades on large sizes
  - no class implementation

- Nice things
  - simple to activate under FPC
  - accompanied by a good manual
  - extensive test coverage
  - there is also rationals, reals & complex available with large set of functions

-----------

@SymbolicFrank - does the above help you or is there something I should add, take into closer focus, from your perspective?

Regards,
MathMan

AlexTP

  • Hero Member
  • *****
  • Posts: 2386
    • UVviewsoft
Re: Large/Big Integer Library in pure Pascal
« Reply #31 on: July 29, 2022, 05:20:41 pm »
@MathMan,
Good information, great. I stored all new information to the wiki -
https://wiki.freepascal.org/BigInteger

Thaddy

  • Hero Member
  • *****
  • Posts: 14205
  • Probably until I exterminate Putin.
Re: Large/Big Integer Library in pure Pascal
« Reply #32 on: July 29, 2022, 05:55:19 pm »
The late Velthuis code takes a bit of trouble, but it is not difficult or cumbersome: It just needs a fake D version. He himself documented that when he was still alive. (We had some exchanges about FPC support)
See his comments here: http://www.rvelthuis.de/programs/bigintegers.html
I got it working.
Specialize a type, not a var.

MathMan

  • Sr. Member
  • ****
  • Posts: 325
Re: Large/Big Integer Library in pure Pascal
« Reply #33 on: July 30, 2022, 10:16:08 am »
The late Velthuis code takes a bit of trouble, but it is not difficult or cumbersome: It just needs a fake D version. He himself documented that when he was still alive. (We had some exchanges about FPC support)
See his comments here: http://www.rvelthuis.de/programs/bigintegers.html
I got it working.

Thaddy - I can understand that from your perspective it is like you stated. But just to give you an idea how things look from my perspective:

When I got hold of MP-ARITH it didn't compile out of the box. It took me roughly 15 min to understand where I had to change the source and then 2 changes in a single include file. After that it compiled and all tests passed.

When I got hold of BigIntegers it didn't compile out of the box. Of course I read the comments. But on the one side the whole statement reads more like "if you do this and that it might work (partially) under FPC" and not "do this and that and then it works, period". On the other side I have exactly 0-knowledge about Delphie or compiler compatibilities, modes, OOP etc. My strenghts are algorithmics and asm-optimisation. So after reading the comments I still gave it a try with the conversion tools supplied with Laz/FPC - after a full day I gave up, as it still didn't even compile. That for me makes the difference between "straightforward" & "tricky"!

But, Thaddy, you are in a unique position to change this. The moment you provide a fully working FPC variant I'll change my verdict to "there is an FPC port available here" (whereever here then will be) and be done with it.

Cheers,
MathMan

440bx

  • Hero Member
  • *****
  • Posts: 3946
Re: Large/Big Integer Library in pure Pascal
« Reply #34 on: July 30, 2022, 10:29:29 am »
- Algorithms
  - basecase multiplication only 33% slower than best known pure Pascal

<snip>

Regards,
MathMan
Just curious... which one is the "best known pure Pascal" ?
(FPC v3.0.4 and Lazarus 1.8.2) or (FPC v3.2.2 and Lazarus v3.2) on Windows 7 SP1 64bit.

MathMan

  • Sr. Member
  • ****
  • Posts: 325
Re: Large/Big Integer Library in pure Pascal
« Reply #35 on: July 30, 2022, 11:04:42 am »
- Algorithms
  - basecase multiplication only 33% slower than best known pure Pascal

<snip>

Regards,
MathMan
Just curious... which one is the "best known pure Pascal" ?

Unfortunately a non-public big integer lib, of which I happen to know the author. It was more thought of as a reference to what is possible with pure Pascal ...

If you'd like to know more detail, like performance of algorithms across number ranges on individual libs, just PM me.
« Last Edit: July 30, 2022, 11:08:58 am by MathMan »

440bx

  • Hero Member
  • *****
  • Posts: 3946
Re: Large/Big Integer Library in pure Pascal
« Reply #36 on: July 30, 2022, 11:13:51 am »
Unfortunately a non-public big integer lib, of which I happen to know the author. It was more thought of as a reference to what is possible with pure Pascal ...

If you'd like to know more detail, like performance of algorithms across number ranges on individual libs, just PM me.
I'd love to know more but, since the "reference" is non-public that precludes looking at its source which is what I do when I really want to "know more" ;)

Thank you for the reply, appreciated.

(FPC v3.0.4 and Lazarus 1.8.2) or (FPC v3.2.2 and Lazarus v3.2) on Windows 7 SP1 64bit.

Thaddy

  • Hero Member
  • *****
  • Posts: 14205
  • Probably until I exterminate Putin.
Re: Large/Big Integer Library in pure Pascal
« Reply #37 on: July 30, 2022, 11:14:50 am »
@mathman
I will publish a proper FPC compatible Velthuis version today or next week, just in his honor. Working on it to work away some bad edits by me.
Specialize a type, not a var.

AlexTP

  • Hero Member
  • *****
  • Posts: 2386
    • UVviewsoft
Re: Large/Big Integer Library in pure Pascal
« Reply #38 on: August 09, 2022, 12:11:07 pm »
@Thaddy,
any work on Velthuis library?

@MathMan,
I posted your 2 big comments about 2 libs, to the wiki.
https://wiki.lazarus.freepascal.org/BigInteger
Any other comments about other libs, please?

SymbolicFrank

  • Hero Member
  • *****
  • Posts: 1313
Re: Large/Big Integer Library in pure Pascal
« Reply #39 on: August 09, 2022, 12:42:42 pm »
@SymbolicFrank - does the above help you or is there something I should add, take into closer focus, from your perspective?

Regards,
MathMan

Yes, that's certainly what I was looking for!

I agree with the others: what is the best multi-platform (ie. pure Pascal) one that works well? Especially for encryption, as that's probably what is going to be used for mostly.

On the other hand, to make full use of the hardware, it might be best to chain SIMD units/instructions.
« Last Edit: August 09, 2022, 12:46:14 pm by SymbolicFrank »

af0815

  • Hero Member
  • *****
  • Posts: 1289
Re: Large/Big Integer Library in pure Pascal
« Reply #40 on: August 09, 2022, 01:14:23 pm »
an extra Information for GNURZ, it is LGPL not GPL, because this was complained
regards
Andreas

AlexTP

  • Hero Member
  • *****
  • Posts: 2386
    • UVviewsoft
Re: Large/Big Integer Library in pure Pascal
« Reply #41 on: August 09, 2022, 01:21:18 pm »
What is GNURZ?

af0815

  • Hero Member
  • *****
  • Posts: 1289
Re: Large/Big Integer Library in pure Pascal
« Reply #42 on: August 09, 2022, 01:22:43 pm »
See at
What is GNURZ?
See at the begin of topic, in the first posts
regards
Andreas

AlexTP

  • Hero Member
  • *****
  • Posts: 2386
    • UVviewsoft
Re: Large/Big Integer Library in pure Pascal
« Reply #43 on: August 10, 2022, 08:59:34 am »
GNURZ - Ok, found mention in the 1st posts, but no link! Search also cannot find anything (duck duck go shows only crap).

google can find - https://github.com/afriess/GNURZ
But description in German! Panic. What to write to the wiki???

Edit- solved.
« Last Edit: August 10, 2022, 09:11:52 am by AlexTP »

af0815

  • Hero Member
  • *****
  • Posts: 1289
Re: Large/Big Integer Library in pure Pascal
« Reply #44 on: August 10, 2022, 09:07:38 am »
Quote
google can find - https://github.com/afriess/GNURZ
But description in German! Panic. What to write to the wiki???
The same panic can have german with english too. SCNR
They have to use a translator for all.

This is an old archieved project, which was saved for studies.

« Last Edit: August 10, 2022, 09:10:06 am by af0815 »
regards
Andreas

 

TinyPortal © 2005-2018