🚀 go-pugleaf

In article <4fv74c$chq@gatekeeper.alcatel.no>, Sven.Pran@alcatel.noL says...
>
>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.
>
>This is where I get stuck. Hey - number theory specialists: How do we proceed?
>
>regards Sven
I got it working, it is actually fairly easy, first you remove EVERY zero from 
the number, not just trailing ones (converting the number to a string and back 
again makes this easy) next you remove all but the last 3 digits, and walla. it 
works.



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