Big Integers

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math Topics]   [Library]   [Utilities]

 

Search

 

Search DelphiForFun.org only

Support DFF

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

In Association with Amazon.com

 

Support DFF

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

 

 

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

 

Search DelphiForFun.org only

 

 

 

 

 

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.

 Added AbsoluteValue: make negative number positive
Fixed  DigitCount: Now correctly counts digits...
Enhanced Assign: Now works with different bases ...
Enhanced ShiftLeftBase10: ensure digits Array is set...
Fixed ShiftRightBase10: correctly count digits...
Optimized Square and Mult: faster:

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. 

bulletIn addition to some general cleanup, a new scratchpad facility  provides a faster handling of large integer work variables by retrieving and returning them from a stack.  Procedures GetNextScratchPad and ReleaseScratchpad replace the Create and Free calls for these temporary work variables.
bulletSeveral "shift" procedures originally added here for use in our TBigFloat class have been relocated to that unit
bulletNew procedures explore alternative definitions for divide and modulo operations: Traditional integer division truncates the quotient, Q, of a divide operation (D/d) towards zero by dropping the fractional part. The remainder, R, is defined as R=D - d*Q. There are other possible definitions of Q which retain this definition of R. (R is frequently defined without the quotient as the "Modulo" function of D and d.   The best discussion I've run across is by Daan Leijen and available at  this Microsoft research site   or here.  The new procedures which define 3 alternatives are:
bulletDivideRemTrunc defined for consistency, calls the existing Dividerem procedure to perform truncated division (quotient rounded towards zero).
bulletDivideRemFloor returns a quotient and remainder where the quotient has been rounded toward toward minus infinity.
bulletDivideRemEuclidean returns a quotient and remainder where the quotient has been rounded in whichever direction produces a positive remainder

The test program includes a new button which compares results for all 3 procedures.

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:

bulletfunction ConvertToHexString:String;  Converts TInteger value to a hexadecimal string.
bulletfunction AssignHex(HexStr:String):Boolean;  Assigns hexadecimal string "HexStr" to TInteger.  Returns False if HexStr is not a valid hexadecimal number.
bulletprocedure RandomOfSize(Size:integer);  Set TInteger value to a random number with "Size" digits.
bulletprocedure Random(MaxInt:TInteger); Set TInteger to a random number greater than or equal to zeros and less than MaxInt.
bulletprocedure GetNextPrime; Set TInteger to the next "probable" prime greater than the current 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  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)!          

 

Download Source or Executable 

bulletDownload source
bulletDownload DFF Library Source  (Current version DFFLibV14_24Mar2014
bulletDownload executable 
bulletDownload Lazarus Source
bulletDownload current DFF Lazarus Library Source(DFFLazLib01)

 
Created:  January 19, 2003

Modified: February 06, 2014

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2013, Gary Darby    All rights reserved.