Big Factorials

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

 

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 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.

Mensa® Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa® 365 Puzzlers  Calendar 2017

Mensa® 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

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

Search DelphiForFun.org only

 

 

 

 

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 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}
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 

bulletDownload source
bulletDownload  executable

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 kN (e.g. 2N or 10N)   are said to grow exponentially (as the exponent I suppose).  How does the growth of N! compare to  kN ?    One clue is that 23! is 23 digits long.  Coincidentally, this also  is approximately the number of kilometers across  the known universe.
 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright © 2000-2018, Gary Darby    All rights reserved.