|
[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:
Download Source or Executable
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2009, Gary Darby
All rights reserved.
|
