Here's unit that will perform basic arithmetic operations on arbitrarily large integers.

(Or, for the sake of the search engines, we could call it big,
or very large, or huge integer arithmetic.)

Operations supported are: ** Assign, Add, Subtract, Multiply, Divide, Modulo, Compare, Factorial,
**and** ConvertToDecimalString. **

**Factorial** is arbitrarily limited to inputs less than or equal to 1000
(2568 digits in result), which will calculate in a second or two. Run times
could become a problem for larger inputs.

All operations are methods of a ** Tinteger** class and replace the value with the
result. For binary operations (i.e. all except **Factorial** and **ConvertToDecimalString**
), the second operand is passed as a parameter of the procedure.

This is a "quick and dirty" implementation - values are kept as
dynamic byte arrays, each byte containing one decimal digit. All
operations are performed pretty much the way you would do them with pencil and
paper. The major exception is that low order digits appear first in
the array (on the left), just the reverse of the way we normally write
them. But it is much easier to extend digits to higher index values
than to shift things around to keep them on the left. It just
takes a few more mental gymnastics while debugging to juggle the the
digits.

I suspect that things could be speeded up by orders of magnitude if arrays
were maintained as ** integer** or ** int64** types with each entry containing an exact
number of decimal digits. Actually, bytes are large enough to
contain 2 decimal digits and 32 bit integers could hold 9 decimal digits
each. Additional code would be required to maintain the appropriate number
of digits per entry as they are manipulated. The really interesting
problem that I haven't solved yet is the conversion of large numbers from one base
to another. Given hexadecimal integer 1X16^{100}, what is
the decimal equivalent? I don't know, but I suppose, having thought of it, I'll be working
on it one of these
days.

This is first time I have used "**overloaded**"
procedures. The same procedure name can be defined multiple times with
different parameter lists by adding the keyword **overload** after it's
declaration. So, for example, there are three **Assign**
procedures to set **Tinteger** values. You can call **Assign**
with another **Tinteger** type, a **int64** integer type or a **string**
representation of a number. Delphi is smart enough to figure which
version of **Assign** to call based on what kind of parameter you
passed. Cool!

A simple test project is included with the downloads below, just to exercise
the unit. If you find any errors, let me know. I did eyeball check a few
operations against the Windows calculator and against the 999! value from my Big
Factorials program (well, not all 2565 digits, but the answer is the same
length and starts out the same).

**Jan 30, 2005 Addendum: ** Version2 of the Big Integers unit, **UBigIntsV2,**
was posted today. It combines, into one unit, the integer procedures
that had been added in support of the Big
Floats floating point unit for large real number arithmetic and a few other
minor corrections. The Divide procedure (specifically **DivideRem**
which returns quotient and remainder) has been rewritten and is now many times
faster - 3 times to 1000s of times faster depending on the
problem.

While working on these changes, viewer Hans Klein sent me several additions
he had made to UBigInts. Most of his additions are to support his
"for fun" projects - identifying large primes and encryption.
You can download the code to try or examine ModPow and InvMod methods.
Here is Hans's response to my
inquiry about ModPow and InvMod.

All posted programs that use Big Integers or Big Float units have been
recompiled with the new units. They are: (Big
Float test, Pell's
Equation and Continued fractions, Big
Combos, and the recently posted Divide
test program which compares results and timings for the old and new big
integer divide methods.

**Addendum April 12, 2005: ** UBigIntsV2 has been added to the
DFFLibrary unit. For the user, this means that in order to recompile BigIntsTest you
will need to download both the program and the library unit.

**Addendum August 29, 2005: ** A small update to UBigIntsV2 in
DFFLibV03 was implemented today. By definition, **f
=Invmod(x,y) **implies that **(f * x) mod y =1** The** Invmod** function is only
defined when the operands are relatively prime (no common divisor greater than
1), but that restriction was not enforced. Invalid operands now
return **0** as an error indication.

Also the **GCD** function looped if the second parameter was **0**.
**GCD(x,0) **now returns** 0.**

**Addendum September 7, 2005: ** DFF regular Charles Doumar has
been busy fixing bugs and enhancing the **TInteger** control. Library
file DFFLibV03 has been updated with a new version of UBigIntsV2.pas
which contains the TInteger class. The main improvements include faster
multiply. I see 3 -7 times faster for exponentiation (Pow function)
which uses repetitive multiply. Also a new Nroot function
which returns the integer part of the Nth root of a number. **BigIntsTest** itself has added a test button for **NRoot** and
the "**Move Result to X**" button, which previously
transferred only one line results, now transfers results regardless of
length.

**Addendum January 10, 2006: ** Charles has been at it again
and fix a few bugs and has made a few enhancements to UBigIntsV2 unit.

**January 31, 2006: ** A minor bug in in the modulo function was
corrected today. In** x mod y**, if **x<y** and **x<0** the
returned value returned should be **x**. The old version returned **-x**,
the positive value.

**August 12, 2012:** Small correction to **IsProbablyPrime** function
fixed a potential memory leak under some conditions when 4 scratchpad memory
fields were not released at exit time.

**November 10, 2013:** A viewer recently wrote asking about how the
**TInteger** class handles arbitrarily large integers. Version 2.1
posted today includes a **Verbose** option which will display the **Digits**
property array for each input and output for the four basic operations (+, -,
*,and /). Each entry in the **Digits** array contains a number of
digits determined by the Base value, a number between 10 and 1,000,000.
The default value 10,000 packs 5 digits into each Digits array member.
A new spin edit allows you to change the Base value and thus the number if
integer digits in each Digits array entry. DFFLibV14 has been reposted
with a small change to **UBigIntsV3** unit to allow compilation with all
versions of Delphi after Delphi 5. UtBigIntsV3 is also included in
the **BigIntstest** source download for this update only. Lazarus code has
not been updated.

**November 17, 2013: BigIntegertest V2.2 **and the** UBigIntsV4
b**ig integers unit were posted today**. **"**Operator overloading**"
is a Delphi feature available for versions after Delphi 7. It allows user
defined classes (such as the **TInteger **class for big integers used here),
to use predefined operators such as** +, -, *, Div, =, <>, >,>=, <,
<=, Inc, **and** Dec**. When encountered , these operators will call the
function necessary to return the result. So as an example to make TInteger
**c** equal to the sum of Tintegers **a** and **b**, previously took
code like **c.assign(a); c.add(b).** With operator support we
write **c:= a + b; ** just like adding two normal integer values.
For various memory management reasons, operators must be applied to
records, not classes, but records now support much of the same attributes as
classes so the conversion was fairly easy. Conditional compilation tests allow
me to keep a single source code file version for both D7 and earlier without
operators) and after D7 (with operators). BigIntegerTest
V2.2 posted today includes new buttons to test operator overloads as well as
unit UBigIntsV4 with the revised TInteger definitions. Cool stuff, but I'm
still learning so let me know what I missed.

**February 6; 2014: ** An error in the **FastMult** procedure in
unit **UBigIntsV4** was inadvertently introduced with the November update.
The corrected version was posted today in library zip file
**DFFVLibV14_6Feb2014.zip.** I have included the revised **UBigIntsV4** unit in
the **BigIntsTestSource** file so reloading the full library file is
recommended but not required for testing this program. As a
matter of interest, **FastMult** requires about 0.5 second to multiply two
random 50,000 digit integers compared to 2.1 seconds for the **Mult**
Procedure (and the results now agree)!

**May 11, 2015: ** UBigIntsV4 was updated today to correct a memory
leak (not all memory was released when a big integer was freed). The
BigintsTest program was modified to report total bytes of memory allocated after
each test operation as a way to check today's fix as well in the future.
Programmers can avoid re-downloading the library zip file by adding the line **
inherited; **as the last statement of **TInteger.Free** method in
UBigIntsV4.

Download Source or Executable