Difference between revisions of "BigInteger"
Line 64: | Line 64: | ||
Code can be adapted for Free Pascal with a little effort. | Code can be adapted for Free Pascal with a little effort. | ||
+ | |||
+ | Comment by forum user [https://forum.lazarus.freepascal.org/index.php?action=profile;u=55215 MathMan]: | ||
+ | |||
+ | * 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 |
Revision as of 17:16, 29 July 2022
There are several (free) Pascal libraries for BigInteger (and sometimes Big Decimals like 1.23) functionality. Note: the C-based GMP library can also be used in Free Pascal, it's not listed here.
TForge
- By: Sergey Kasandrov
- Homepage: https://github.com/Alexey-T/TForge-Pascal
Modern cryptographic library for Delphi and Lazarus/FPC implemented as a set of runtime packages. Project development was stopped, the last found snapshot v0.76 was put to GitHub.
Big Decimal Math
- By: Benito van der Zander
- Homepage: https://benibela.de/sources_en.html#bigdecimalmath
This unit provides a BigDecimal-Type which stores arbitrary precision (BCD) decimal numbers and can be used like any native numeric type.
FNX
- By: Marcel Martin
- Homepage: https://www.ellipsa.eu/public/fnx/fnx.html
Library of multi-precision numbers (currently, only big integers) written for Free Pascal and Linux. The assembler code that can be enabled with a compiler directive, is for x86-64 processors only.
MPArith
- By: Wolfgang Ehrhardt
- Homepage: https://github.com/Alexey-T/Wolfgang_Ehrhardt_codes/tree/master/Misc/MPArith
Project development was stopped in about 2018. The last found snapshot was put to GitHub.
BigInt
- By: Franco Milani
- Homepage: http://spazioinwind.libero.it/frm/software
Though this is a Pascal source >90% are coded as x86-32 Win32 assembler routines.
HugeInt
- By: David J Butler
- Homepage: https://github.com/fundamentalslib/fundamentals5
Part of a much larger library but the unit can be used self-contained.
LongMathForPascal
- By: Zsolt Szakaly
- Homepage: https://github.com/zsoltszakaly/longmathforpascal
A quite recent contribution (2021) - unfortunately it does not support any efficient algorithms and becomes slow very fast.
GInt
- By: Walied Othman
- Homepage: https://github.com/SnakeDoctor/FGInt
Again part of a larger library but can be used self-contained.
BigIntegers for Delphi
- By: Rudy Velthuis
- Homepage: https://github.com/rvelthuis/DelphiBigNumbers
Code can be adapted for Free Pascal with a little effort.
Comment by forum user MathMan:
- 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