AngouriMath
GreatestCommonDivisors
Description
Summary
The greatest common divisor of two integers, and a fraction in lowest terms by it: the
numerator and the denominator divided by their greatest common divisor. Both answer
exactly what PeterO's Gcd(PeterO.Numbers.EInteger) and
ToLowestTerms answer, and every greatest common divisor and
reduction in the library goes through them instead.
numerator and the denominator divided by their greatest common divisor. Both answer
exactly what PeterO's Gcd(PeterO.Numbers.EInteger) and
ToLowestTerms answer, and every greatest common divisor and
reduction in the library goes through them instead.
Remarks
when the divisor itself is large: on a pair of 2658 and 2249 bits sharing a factor of
1117 bits it takes 1.5 s, where Euclid's algorithm takes 1.6 ms and the BCL's
GreatestCommonDivisor(System.Numerics.BigInteger,System.Numerics.BigInteger) 14 µs; a shared factor of 5000 bits does
not finish in 30 s. A sum of two fractions with a large common denominator is exactly
such a pair, and every Rational is reduced on creation, so an
integrand evaluated at a sample point whose fractions grew to a few thousand bits spent
nearly all its time reducing them.
fractions the simplifier makes in about half PeterO's time. Larger ones are converted to
BigInteger by their two's-complement bytes, which both types read and write,
and the BCL's Lehmer algorithm answers: faster than PeterO's at every size measured, from
64 bits to 100,000, coprime or not, conversion included. Euclid's algorithm on
EInteger is not an alternative: its divisions make it 500 ms on a coprime
pair of 10,000 bits, where PeterO takes 3 ms and the BCL 0.1 ms.
Members
Angouri © 2019-2023 · Project's repo · Site's repo · Octicons · Transparency · 4862 pages online