[Home] [Puzzles & Projects] [Delphi Techniques] [Math Topics] [Library] [Utilities]
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 1X16100, 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.
April 4, 2006: Added FastMult and FastSquare methods written by Charles Doumar which are faster versions of Mult and Square for very large integers. 12 times faster for 250,000 digit integers but still 11 seconds on my 1.8Ghz laptop.
February 7, 2007: A new version of TInteger was posted today with a unit version update from UBigIntsV2 to UBigIntsV3. To ease the transition, both versions are contained in the new library zip file DFFLibV10. UBigIntsV2 will disappear with the next update.
May 12, 2009: DFF Library unit DFFLibV13 was posted today and includes several new routines added to unit UBigIntsV3. I've decided that changing the names of units with each change is not a good idea. Each unit name change requires a change in the source code of every program which uses the unit without much benefit.
BigIntsTest, also reposted today, includes buttons for testing the new TInteger methods in unit UBigIntsV3:
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 big 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
Copyright © 2000-2016, Gary Darby
All rights reserved.