Click here to Skip to main content
15,177,535 members
Articles / Programming Languages / C#
Posted 11 May 2009


22 bookmarked


Rate me:
Please Sign up or sign in to vote.
4.58/5 (12 votes)
8 Mar 2010CPOL3 min read
A general-purpose unbounded integer implementation


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.


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.


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


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 BigInts from strings, 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.


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.


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.

BigCalculator screen shot


1.00May 10, 2009First release
1.01May 11, 2009Improved 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.02May 16, 2009Fixed remainder bug.
1.03May 17, 2009Improved division memory usage.


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Stephen Swensen
United States United States
I'm developing Unquote, a library for writing unit test assertions as F# quoted expressions:

I am working through Project Euler with F#:

I participate in Stack Overflow:

Comments and Discussions

Generaldivision in o(n+m) Pin
laurv8-Feb-10 5:00
Memberlaurv8-Feb-10 5:00 
GeneralRe: division in o(n+m) Pin
Stephen Swensen10-Feb-10 23:05
MemberStephen Swensen10-Feb-10 23:05 
NewsFastest BigInt for C# Pin
Squat15-Sep-09 21:23
MemberSquat15-Sep-09 21:23 
GeneralRe: Fastest BigInt for C# [modified] Pin
Stephen Swensen16-Sep-09 6:13
MemberStephen Swensen16-Sep-09 6:13 
GeneralRe: Fastest BigInt for C# Pin
Squat2-Oct-09 2:07
MemberSquat2-Oct-09 2:07 
GeneralIncorrect Remainder Pin
Shaikk15-May-09 9:34
MemberShaikk15-May-09 9:34 
GeneralRe: Incorrect Remainder Pin
Stephen Swensen15-May-09 9:45
MemberStephen Swensen15-May-09 9:45 
GeneralRe: Incorrect Remainder Pin
Stephen Swensen16-May-09 11:03
MemberStephen Swensen16-May-09 11:03 
GeneralWhy not use a fast multiplication algorithm Pin
ZTransform15-May-09 5:11
MemberZTransform15-May-09 5:11 
GeneralRe: Why not use a fast multiplication algorithm Pin
Stephen Swensen15-May-09 5:25
MemberStephen Swensen15-May-09 5:25 
GeneralC# 4.0 big ints Pin
darrellp14-May-09 11:12
Memberdarrellp14-May-09 11:12 
GeneralRe: C# 4.0 big ints Pin
Stephen Swensen14-May-09 15:50
MemberStephen Swensen14-May-09 15:50 
GeneralNo performance nor Memory consumption is minimized at all Pin
Gabriel 212-May-09 18:12
MemberGabriel 212-May-09 18:12 
GeneralRe: No performance nor Memory consumption is minimized at all Pin
Stephen Swensen17-May-09 4:47
MemberStephen Swensen17-May-09 4:47 
QuestionPerformance? Pin
torial12-May-09 7:40
Membertorial12-May-09 7:40 
AnswerRe: Performance? Pin
Stephen Swensen12-May-09 16:24
MemberStephen Swensen12-May-09 16:24 
GeneralYou can increase performance if you use some larger base, for example 1024 Pin
Vadim Shtayura11-May-09 22:33
MemberVadim Shtayura11-May-09 22:33 
GeneralRe: You can increase performance if you use some larger base, for example 1024 Pin
Steve Hansen12-May-09 1:51
MemberSteve Hansen12-May-09 1:51 
GeneralRe: You can increase performance if you use some larger base, for example 1024 Pin
Stephen Swensen12-May-09 16:09
MemberStephen Swensen12-May-09 16:09 
GeneralRe: You can increase performance if you use some larger base, for example 1024 Pin
darrellp14-May-09 11:20
Memberdarrellp14-May-09 11:20 
I'm not sure why you used LinkedList rather than List, though. List is based on an array and can be extended so that takes care of your argument about not knowing the length ahead of time. LinkedList allows you to make insertions/deletions into the middle of the list in constant time and that's it's primary advantage. On the other hand, finding the n'th element in a linked list is super slow compared to arrays. I haven't looked at your code but I'm guessing that you're referencing digits and inserting them at one end more than you're trying to stuff them into the middle of arrays.
GeneralRe: You can increase performance if you use some larger base, for example 1024 Pin
Stephen Swensen14-May-09 16:41
MemberStephen Swensen14-May-09 16:41 
GeneralRe: You can increase performance if you use some larger base, for example 1024 Pin
Utah Luxury15-Mar-10 18:21
MemberUtah Luxury15-Mar-10 18:21 
GeneralRe: You can increase performance if you use some larger base, for example 1024 Pin
Stephen Swensen16-Mar-10 6:37
MemberStephen Swensen16-Mar-10 6:37 
GeneralFirst release Pin
Stephen Swensen11-May-09 19:24
MemberStephen Swensen11-May-09 19:24 
GeneralRe: First release Pin
DaveyM6912-May-09 4:09
professionalDaveyM6912-May-09 4:09 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.