[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionHere's a program to calculate really large factorials - up to 999! which contains more than 2500 digits! Probably not very practical, but it is a good exercise simulating pencil and paper long multiplication. Background & TechniquesFor any integer N, N factorial, usually written N!, is the product of all integers from 1 through N. So 3!=1*2*3=6, 10!=1*2*3*4*5*6*7*8*9*10=3,628,800. As you can see, N! increases very rapidly with increasing N. Delphi integer types occupy 32 bits, long integer, denoted as int64, occupy 64 bits. The max value of these types is 231-1 and 263-1, large enough to contain only 15! and 20! respectively. BigFactorials overcomes this size limitation by multiplying almost the way we would do it with pencil and paper. Numbers are kept as an array of bytes, each byte representing one digit. The array is dynamic, so sizes can be changed as required. As a result, the number of digits in the result is limited only by the amount of memory available and the time you are willing to wait. I've limited the maximum input integer here to 999 here just to keep calculation times to 1 or 2 seconds. When the user presses the "Compute " button we call the the Factorial procedure with the input value. A loop running from 2 to N is executed, each time through we'll multiply the previous answer by the loop control variable I. The digits in the number are kept with the units digit on the left and the high order digit on the right. This puts any leading zeros at the end of the array where they are easier to trim. The mod and div functions are used to get the units and carry part of each intermediate result. M1 and m2 are the two multiplicand arrays, result is array where the product is being accumulated. Shift is j-1, the amount we are shifting over for the jth digit. Again, just like long multiplication except we are shifting further left each time instead of further right. Here is the key code inside of a loop on j and k. c:=m2[j]*m1[k]; {multiply the jth digit
of m2 by the kth digit of m1}
Running/Exploring the Program
Suggestions for Further Explorations
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |