🚀 go-pugleaf

In article <4g0giv$94s@sun132.spd.dsccc.com>,
   kcline@sun132.spd.dsccc.com (Kevin Cline) wrote:
>In article <4fr8be$ass@news.iconn.net>, 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.
>>
>>--
>
>Since so many people have produced an incorrect solution to this problem,
>I thought it would be worthwhile posting the correct solution.
>
>Everyone had the right idea, which is to keep only the last digit
>and compute the change when multiplying by the next number
>in the factorial, but couldn't figure out what to do
>about the numbers that end in 5, since that introduces a new zero
>in the series.  The answer is simple; when multiplying by five,
>take half of the previous digit +-5 to make an even number.

This was a major step towards the correct solution, but alas still incorrect!

Look what happens when the multiplier ends in 25 or 75 (producing 2 zeroes), 
and even worse when the multiplier is 125 (producing 3 zeroes) and finally 
625 (producing 4 zeroes).

So what is the correct solution? Simple when I finally stumbled across it:

Don't use up the multipliers entirely in the process, but save some factors 2
sufficient in number to match one such factor 2 with each factor 5 whenever a
multiplier divisible by 5 is to be processed! Such couples are then discarded 
before performing the multiplication.

Example:
RSD(4) = 1 * 2 * 3 * 4 = 4    (discarding the leading 2 in the product)
RSD(5) = 1 * 2 * 3 * 2 (!) * (2*5) = 2 (discarding the factor 2*5 etc.)
RSD(6) = 2 * 6 = 2
RSD(7) = 2 * 7 = 4
 . .
RSD(23) = 2 (I hope I calculated this one correct)
RSD(24) = 2 * 24 = 8
RSD(25) = 2 * 6 (!) * (4 * 25) = 2    (discarding the factor 4*25 etc.)

and so on.

Eureka ! (?)

Sven