Big Factorials

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

Search

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.

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

Contact

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

Problem Description

Here'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 & Techniques

For 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 2³¹-1 and 2⁶³-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 j^th 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}
result[k+shift]:=result[k+shift]+ c mod 10; {add in the units part}
result[k+shift+1]:=result[k+shift+1]+ c div 10; {add in the carry part}

Running/Exploring the Program

Suggestions for Further Explorations

	For numbers much higher than 999!, I would search for more efficient techniques.
	It would also be a good idea to add a Stop button and periodically call application.processmessages inside the multiply loop if the max number is increased. (See the article on maintaining responsiveness in Delphi techniques section for more information.)
	The code could be written to work just like manual long multiplication - I'm not sure of the effect on efficiency, but the code would probably be easier to follow.
	I mentioned that factorial values increase very rapidly as N increases. There are mathematical measures of this rate of growth. For example k^N (e.g. 2^N or 10^N) are said to grow exponentially (as the exponent I suppose). How does the growth of N! compare to k^N ? One clue is that 23! is 23 digits long. Coincidentally, this also is approximately the number of kilometers across the known universe.