My Arbitrary Precision Arithmetic Libraries

Hello C# code enjoyers. It's been a long time since I updated this blog, but that is going to change. I've been keeping a folder of blog post ideas and typed up thoughts on subjects that I think would fit here. So I have a lot of posts I wanted to make, about cool things I've written and discovered along the way.

For the coding side of things, boy have I been busy. I've written a number of arbitrary precision numeric type libraries, and other maths related projects.

I wanted to share some of these projects with you.

General Number Theory Sieve

The general number field sieve (GNFS) is currently the most efficient algorithm known for factoring very large semiprime numbers. It is the primary algorithm that has been used to set the last several world record factorizations.

• GNFS - This was a long, difficult project that took over a year to develop and required me teaching myself the basics of abstract algebra to be able to finish it. This project was intended to be more of a C# reference implementation of the General Number Field Sieve algorithm for the purpose of better understanding the General Number Field Sieve algorithm better than it was to be anything performant or fast.

Arbitrary Precision Arithmetic Types

• BigDecimal - An arbitrary precision, base-10 floating point number class. This is probably the most popular of my numeric libraries. It's getting quite popular, and may soon become the most downloaded 'big decimal' library on Nuget! One of the features my library has that its competitors do not is Trigonometric functions, Hyperbolic Trigonometric functions, and inverse trigonometric functions. Yes, to arbitrary precision. It accomplishes this by using the taylor series, and for the trig functions where the taylor series converges too slowly, ArcCosine for example, it uses continued fractions. The iteration of the infinite series stops once the difference between two iterations becomes less than some threshold you supply in terms of powers of negative 10, which is the same as saying how many digits past the decimal point do you want it to be accurate to.

• BigRational - Arbitrary precision number with arithmetic, except this one stores the value as an improper fraction under the hood. Actually, thats the fraction class of this library. BigRational represents the value as a mixed fraction. That is: Integer value + Fractional value

• BigComplex - Essentially the same thing as System.Numerics.Complex except that it uses a System.Numerics.BigInteger type for the real and imaginary parts instead of a double.

Polynomials

• Polynomial - The original. A univariate polynomial that uses System.Numerics.BigInteger for the type of the indeterminate (variables/letters).

• ComplexPolynomial - A univariate polynomial library that has System.Numerics.Complex type indeterminates.

And some variations using different underlying types for the variable:

Multivariate

• MultivariatePolynomial - A multivariate polynomial (meaning more than one indeterminate, e.g. 2XY^2) which uses BigInteger as the type for the indeterminates

• ComplexMultivariatePolynomial - A multivariate polynomial library that has System.Numerics.Complex indeterminates.

Generic Arithmetic

Seeing all these Polynomial libraries, you might be thinking: Wouldn't you rather make a class that you write only once and swap out the underlying type? Yes. Yes I would. Unfortunately, inheritance doesnt work. I thought generics would do it, but there is no generic constraints that says 'this is an arithmetic type. allow the +-*/ operators to work on these types in the normal way'. Thus the arithmetic operations are not available and thats kinda the whole point. 

Fortunately, there was a way to call each type's respective operator overload function dynamically at runtime by building a Linq.Expressions LambdaExpression that invokes the appropriate function on the class. This allows for you to specify the type as the generic type T with this generic class library just like you might have expected to be possible natively.

• GenericArithmetic - A core math library. Its a class of static methods that allows you to perform arithmetic on an arbitrary numeric type, represented by the generic type T, who's concrete type is decided by the caller. This is implemented using System.Linq.Expressions and reflection to resolve the type's static overloadable operator methods at runtime, so it works on all the .NET numeric types automagically, as well as any custom numeric type, provided it overloads the numeric operators and standard method names for other common functions (Min, Max, Abs, Sqrt, Parse, Sign, Log, Round, etc.). Every generic arithmetic class listed below takes a dependency on this class.

After writing that, naturally, I had to make:

• GenericPolynomial - A univariate polynomial library that allows the indeterminate to be of an arbitrary type, as long as said type implements operator overloading. This is implemented dynamically, at run time, calling the operator overload methods using Linq.Expressions and reflection.

• GenericMultivariatePolynomial - A multivariate polynomial that allows the indeterminates to be of [the same] arbitrary type. GenericMultivariatePolynomial is to MultivariatePolynomial what GenericPolynomial is to Polynomial, and indeed is implemented using the same strategy as GenericPolynomial (i.e. dynamic calling of the operator overload methods at runtime using Linq.Expressions and reflection).

• GenericVector - A generic Vector numeric type. Supports: Scalar arithmetic, vector arithmetic, square root, dot product, normal, reflection, distance, lerp, sum of squares and cosine similarity.

Miscellaneous

And some miscellaneous and smallish libraries playing around with various types of arithmetic:

• Continued Fraction - A continued fraction class. Arbitrary precision. Supports converting a continued fraction into rational approximations up to precision.

• IntervalArithmetic - Instead of representing a value as a single number, interval arithmetic represents each value as a mathematical interval, or range of possibilities, [a,b], and allows the standard arithmetic operations to be performed upon them too, adjusting or scaling the underlying interval range as appropriate. This is an interesting way of doing things and has some narrow uses. Despite that its sort of feels like a solution in need of a problem. See Wikipedia's article on Interval Arithmetic for further information.