🚀 go-pugleaf

The Crow (thecrow@iconn.net) wrote:
: Here is what I am trying to do, I want to find the last NON-ZERO digit of a 
: given factorial.  For instance,

: 5! = 120

: so the last non-zero digit is 2.  I want to be able to do this up to 1000.  
: Problem is, no matter how huge of a data-type you use, there isn't any way
: for 
: the computer to handle 1000!, it is however possible to find the last non-
: zero 
: digit somehow.  One thing I have tried is as I went through mulitplying the 
: series of numbers in the factorial (5 * 4 * 3 * 2) I would remove all the 
: trailing ZEROS, I got this to work up to 789, but it wont work with 1000 and 
: i
: am not really sure why.  If anyone has a clue how I can do this let me know.

: -- 
: The Crow - thecrow@iconn.net
: "It can't rain all the time"
: -Kryptology


  I don't know a formula for the kth digit of N!, but going ahead and
computing all of N! isn't that hard.  Use multiprecision arithmetic.
Put each digit into an array element.  The base used is usually the word
size of the computer, but for this case base 10 would be easier to
understand.
  Initialize an array U[1]=1 and a variable UL=1 which is the length of
the array.
  
  for j := 2 to N do   
   begin
    for i := 1 to UL do
     U[i] := U[i]*j;
    
     Now Normalize the array.

     for i := 1 to UL do
      begin
       U[i+1] := U[i] div 10;
       if (i=UL) and (U[i+1]<>0) then UL := UL+1;
       U[i] := U[i] mod 10;
      end;

   end;

  This is simple paper and pencil type arithmetic and shouldn't be hard
to follow.  Using Stirling's formula for N! the size of the array needed
for this is approximately log N! = log N + N log(N/exp(1)) for 1000! that
would be 2568 digits or array elements.