🚀 go-pugleaf

In article <4fv74c$chq@gatekeeper.alcatel.no>
           Sven.Pran@alcatel.no "Sven Pran" writes:

> In article <31224679.6193@born.com>, John Cleland <clelaj@born.com> wrote:
> >The Crow 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 
> >> multiplying 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.
> >
> >Don't just strip the trailing zeros, remove all digits except the last 
> >non-zero digit (which is your output) and then multiply by the next number in 
> >your sequence. This keeps the numbers down to a managable level and gives the 
> >correct answer as no more significant digit can affect the value of the LSD.
> >
>  . . . .
> 
> No, it is obviously not sufficient to keep the last single non-zero digit, and 
> the problem appears to be a very interesting and intriguing one:
> 
> A new trailing zero is 'created' every time the next multiplier is divisible 
> by 5, and how can we then calculate the next 'rightmost significant' digit?
> 
> Example when a multiplier ends in 05:
> 
> If the 'previous' factorial ended in 02 then the new factorial will end in 1 
> while if it ended in 12 then the new factorial will end in 6 (after removal of 
> trailing zeroes).
> 
> Thus the SINGLE rightmost significant digit in the new factorial depends upon 
> the TWO rightmost significant digits both in the previous factorial and in the 
> multiplier.
> 
> This means that we must keep track of the last TWO digits to calculate the new 
> SINGLE rightmost significant digit whenever a zero is 'created'. For similar 
> reasons we must track THREE digits to calculate the new TWO rightmost 
> significant digits - and so on.
> 
> How many zeroes have been 'removed' when we reach 1000! ? The answer is 249, 
> which means that in order to maintain the precision needed we must track the 
> last 250 digits less the number of zeroes already 'removed' when N! reaches a 
> number with that many digits.

Yes, but these digits are the rightmost when we throw them away as we go along.
Remember that our running total is not affected by itself, so we can throw away
the bits we don't want.  This includes a trailing 0.

Using this method would give simple to program results for n up to the maximum
size of a long integer / 9.  More if you do your own multiplication:

let t be 1.
Run a loop for variable r from 2 to n.  (for loop...)
  Multiply t by r.
  Strip trailing zeros.
  Take rightmost digit, and put it in t.
loop round.

t is your answer.

(Crossposted to C and Pascal, so written in English :)

Basically, you must remember that all the other information stored in t is
irrelevant.  It is only ever the last digit which determines what the next
last digit will be.

In fact, you could just sum the digits of r and multiply t by that.  You could
then perhaps store the digits of r in an array, allowing for large values
of n.  (Multiply, add, trim; Multiply, add, trim; through the digits)

I suspect there will be a flaw in my reasoning, so feel free to point it out :)
-- 
* TQ 1.0 * The 'Just So Quotes'.
Sic Biscuitus Disintegrat.
    	-- Adrian Ogden