Difference between revisions of "BigInteger"

From Lazarus wiki
Jump to navigationJump to search
Line 29: Line 29:
  
 
Project development was stopped in about 2018. The last found snapshot was put to GitHub.
 
Project development was stopped in about 2018. The last found snapshot was put to GitHub.
 +
 +
Comment by forum user [https://forum.lazarus.freepascal.org/index.php?action=profile;u=55215 MathMan]:
 +
 +
* 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
  
 
==BigInt==
 
==BigInt==

Revision as of 17:19, 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

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

This unit provides a BigDecimal-Type which stores arbitrary precision (BCD) decimal numbers and can be used like any native numeric type.

FNX

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

Project development was stopped in about 2018. The last found snapshot was put to GitHub.

Comment by forum user MathMan:

  • 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

BigInt

Though this is a Pascal source >90% are coded as x86-32 Win32 assembler routines.

HugeInt

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

LongMathForPascal

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

GInt

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

BigIntegers for Delphi

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
Retrieved from "http://wiki.freepascal.org/index.php?title=BigInteger&oldid=152662"