12,997,138 members (74,382 online)
alternative version

#### Stats

74.2K views
22 bookmarked
Posted 11 May 2009

# BigInt

, 8 Mar 2010
 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 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.

## 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.

## About the Author

 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

## Comments and Discussions

 First PrevNext
 division in o(n+m) laurv8-Feb-10 4:00 laurv 8-Feb-10 4:00
 i think something is wrong with this claim. i did not check the source code yet, but if you can do division so fast, then you can do multiplication in o((n+m)log(n+m)/2), that is even much faster than the fft. just consider the next algorithm: to multiply a*b, where a has n digits and b has m, pick x=2^(n+m) and divide it to b. If the result is smaller then a, add x+=x/2, if is bigger subtract x/2, then repeat, divide by b, add/subtract x/4, and so on (like quicksort, every time set one bit right). at the end you get the right x=a*b and made (log(n+m)/2)*(m+n) digit-operations. something is wrong here. if you do paper-division, then the order of that one is not m+n, but m*n.
 Re: division in o(n+m) Stephen Swensen10-Feb-10 22:05 Stephen Swensen 10-Feb-10 22:05
 Fastest BigInt for C# Squat15-Sep-09 20:23 Squat 15-Sep-09 20:23
 Re: Fastest BigInt for C# [modified] Stephen Swensen16-Sep-09 5:13 Stephen Swensen 16-Sep-09 5:13
 Re: Fastest BigInt for C# Squat2-Oct-09 1:07 Squat 2-Oct-09 1:07
 Incorrect Remainder Shaikk15-May-09 8:34 Shaikk 15-May-09 8:34
 Re: Incorrect Remainder Stephen Swensen15-May-09 8:45 Stephen Swensen 15-May-09 8:45
 Re: Incorrect Remainder Stephen Swensen16-May-09 10:03 Stephen Swensen 16-May-09 10:03
 Why not use a fast multiplication algorithm ZTransform15-May-09 4:11 ZTransform 15-May-09 4:11
 Re: Why not use a fast multiplication algorithm Stephen Swensen15-May-09 4:25 Stephen Swensen 15-May-09 4:25
 C# 4.0 big ints darrellp14-May-09 10:12 darrellp 14-May-09 10:12
 Re: C# 4.0 big ints Stephen Swensen14-May-09 14:50 Stephen Swensen 14-May-09 14:50
 No performance nor Memory consumption is minimized at all Gabriel 212-May-09 17:12 Gabriel 2 12-May-09 17:12
 Re: No performance nor Memory consumption is minimized at all Stephen Swensen17-May-09 3:47 Stephen Swensen 17-May-09 3:47
 Performance? torial12-May-09 6:40 torial 12-May-09 6:40
 Re: Performance? Stephen Swensen12-May-09 15:24 Stephen Swensen 12-May-09 15:24
 You can increase performance if you use some larger base, for example 1024 Vadim Shtayura11-May-09 21:33 Vadim Shtayura 11-May-09 21:33
 Re: You can increase performance if you use some larger base, for example 1024 Steve Hansen12-May-09 0:51 Steve Hansen 12-May-09 0:51
 Re: You can increase performance if you use some larger base, for example 1024 Stephen Swensen12-May-09 15:09 Stephen Swensen 12-May-09 15:09
 Re: You can increase performance if you use some larger base, for example 1024 darrellp14-May-09 10:20 darrellp 14-May-09 10:20
 Re: You can increase performance if you use some larger base, for example 1024 Stephen Swensen14-May-09 15:41 Stephen Swensen 14-May-09 15:41
 Re: You can increase performance if you use some larger base, for example 1024 Utah Luxury15-Mar-10 17:21 Utah Luxury 15-Mar-10 17:21
 Re: You can increase performance if you use some larger base, for example 1024 Stephen Swensen16-Mar-10 5:37 Stephen Swensen 16-Mar-10 5:37
 First release Stephen Swensen11-May-09 18:24 Stephen Swensen 11-May-09 18:24
 Re: First release DaveyM6912-May-09 3:09 DaveyM69 12-May-09 3:09
 Last Visit: 31-Dec-99 18:00     Last Update: 22-Jun-17 14:22 Refresh 12 Next »

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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