# BigInt

, 8 Mar 2010 CPOL
 Rate this:
A general-purpose unbounded integer implementation

## Overview

`BigInt` is a general-purpose unbounded integer implementation consistent with C# and .NET numeric type conventions: it's an immutable `ValueType`, implements `IComparable<BigInt>`, `IEquatable<BigInt>`, and `IConvertable` interfaces, and supplies arithmetic operators and various implicit and explicit conversion operators.

To date, there are very few options available for C# .NET developers in need of "Big" numbers. Chew Keong TAN's C# BigInteger[^] is very fast, but specialized for cryptology at the neglect of memory considerations (implemented with a constant length `Array`, memory is quickly exhausted, and performance degraded when the length is set even moderately high). Microsoft's J# BigInteger[^] is also available, but is awkward to use (reference type, no operators, Camel-case), and also requires distributing the J# runtime with your applications.

`BigInt` is implemented with a `LinkedList<byte>` in base-10. Hence, memory consumption and performance are not as optimal as may be achieved with an `Array` in a higher base. That being said, `BigInt` is reasonably performing and light enough on memory that it should be suitable for many applications.

## Arithmetic

Standard pencil and paper algorithms are implemented for addition, subtraction, multiplication, and division. Hence, addition and subtraction yield m + n complexity where m and n are the number of digits in each operand, respectively. And multiplication and division are order m * n. Multiplication uses mutation internally for performance gains (the addition steps are accumulated in the result with `AddTo`, sparing repeated large memory allocation we'd otherwise incur for temporary states).

## Common Algorithms

Beyond basic arithmetic, several common algorithms are provided for `BigInt` including min, max, mod, pow, and truncated square root, to name a few.

## Operators

All binary and unary operators traditionally associated with numeric types are provided; however, bitwise operations and operators have yet to be implemented.

## Conversion

To avoid redundancy, while risking incompatibility across all .NET languages, we refrain from using non-default constructors as a method of conversion to `BigInt`; instead, we rely on implicit conversion operators for lossless conversions from numeric .NET System types, and explicit conversion operators for other useful types. `BigInt.Parse` and `BigInt.TryParse` are preferable methods for constructing `BigInt`s from `string`s, but we also make an exception and implement an explicit `string `to `BigInt` conversion operator to accommodate `Enumerable.Cast<string>(BigInt)`. In addition, several lossy explicit conversion operators paralleling `IConvertable` are provided for conversion from `BigInt` to other types.

## Serialization

`BigInt` is suitable for both binary and XML serialization. Marked with the `Serializable` attribute, only the `private `fields of `BigInt` (`digits` and `isneg`) participate in binary serialization, as is appropriate. Default XML serialization, whereby `public `fields and properties are serialized, is wholly inappropriate; therefore, we implement the `IXmlSerializable` interface, representing the `BigInt` via `BigInt.ToString` for `WriteXml`, and deserializing via `BigInt.Parse` for `ReadXml`.

## Properties

`Divisors`, `ProperDivisors`, `DigitsLeftToRight`, and `DigitsRightToLeft` are implemented as object streams (`IEnumerable<BigInt>`) and were selected for their ability to describe fundamental aspects of integers. The first two expose the integer intrinsics. The latter support manipulating integers on the structural level. A `PrimeFactorization` property is pending implementation.

## Big Calculator

The sample application provided is driven by `BigInt`'s `static Eval` method. `Eval` can parse and evaluate many simple binary and unary `BigInt` expressions. `Eval` / `BigCalculator` may be extended in the future to support processing complex expression trees and typical calculator features such as variable assignment.

## History

 Version Date Description 1.00 May 10, 2009 First release 1.01 May 11, 2009 Improved performance of `Pow` by using exponentiation by squaring. Improved performance of `Gcd` (and therefore `Lcm`) by using the Euclidean algorithm. Modified `Range` to accept reverse ranges. 1.02 May 16, 2009 Fixed remainder bug. 1.03 May 17, 2009 Improved division memory usage.

## Share

United States
I'm developing Unquote, a library for writing unit test assertions as F# quoted expressions: http://code.google.com/p/unquote/

I am working through Project Euler with F#: http://projecteulerfun.blogspot.com/

I participate in Stack Overflow: http://stackoverflow.com/users/236255/stephen-swensen

 First Prev Next
 division in o(n+m) laurv 8-Feb-10 5:00
 Re: division in o(n+m) Stephen Swensen 10-Feb-10 23:05
 Fastest BigInt for C# Squat 15-Sep-09 21:23
 Re: Fastest BigInt for C# [modified] Stephen Swensen 16-Sep-09 6:13
 Re: Fastest BigInt for C# Squat 2-Oct-09 2:07
 You should not change it to a struct because then you would have to do copying or reference counting of the underlying GMP resource. Unlike Int32's, BigInt's can be large (thousands of bits long) and you would not want to be making copies every time you pass them to a function or do an assignment.   I agree that unsafe operations can be a problem, especially if you want to use BigInt's on a platform like Silverlight. But if you're running it outside of the browser and you just want to get the fastest possible operations, unsafe code and interop is the way to go. If you run the speed comparison, you will see that interoping with GMP is about 10 times faster than a heavily optimized purely C# version.   As for type conversion, I just followed the .NET type conversions for Int32, which allow you to implicitly cast from Int32 to double, but require explicit casting for double to Int32.
 Incorrect Remainder Shaikk 15-May-09 9:34
 Re: Incorrect Remainder Stephen Swensen 15-May-09 9:45
 Re: Incorrect Remainder Stephen Swensen 16-May-09 11:03
 Why not use a fast multiplication algorithm ZTransform 15-May-09 5:11
 Re: Why not use a fast multiplication algorithm Stephen Swensen 15-May-09 5:25
 C# 4.0 big ints darrellp 14-May-09 11:12
 Re: C# 4.0 big ints Stephen Swensen 14-May-09 15:50
 No performance nor Memory consumption is minimized at all Gabriel 2 12-May-09 18:12
 Performance? torial 12-May-09 7:40
 Re: Performance? Stephen Swensen 12-May-09 16:24
 First release Stephen Swensen 11-May-09 19:24
 Re: First release DaveyM69 12-May-09 4:09
 Re: First release Stephen Swensen 12-May-09 14:56
 Last Visit: 31-Dec-99 19:00     Last Update: 20-Dec-14 12:27 Refresh 1