🚀 go-pugleaf

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.
>
>-- 
>The Crow - thecrow@iconn.net
>"It can't rain all the time"
>-Kryptology
>

One article in this thread was recently posted to sci.math where I responded.
I don't know why it didn't show up here, but here was my response.


I don't see this as a hard problem. Of course, you don't need to work
with n!. In fact, you only need to keep a few bytes of data.

=========================================================================

One can keep track of rightmost nonzero digit by storing two things:

A) the number of factors of 2 which have not been ``canceled'' by a 5.

                               *
B) The relavant unit in (Z/10Z)  .

=========================================================================

Here is some simple code:

int foo(n)
int n;   /* the input is n for n! */
{
int i,j,u=1,t=0;
for(i=1;i<=n;i++)
  {
    j=i;
    while(!(j&1)) {j>>=1;t++;}
    while(!(j%5)) {j/=5;t--;}
    u=(u*(j%10))%10;
  }
if(t) {t&=3;if(!t) t=4;}          /* if t>0, only need t mod 4 */
for(i=0;i<t;i++) u=(u<<1)%10;     /* include factors of 2 */
return(u); /* The rightmost non-zero digit of n! is u */
}


For very large n you might have to be more careful about overflow in t.
But you only really need to keep track of t mod 4 once t is positive (but
you need to be able to distinguish t=0 for when n<2 or take care of these
few cases separately).

It would seem that faster methods could be achieved by looping over 
the primes p<n instead of all numbers <n. Indeed, primes congruent to
1 (mod 10) could be skipped altogether (this is 25% of primes). I'll
elaborate on this idea if someone wants to hear it.

One thing, I usually read sci.math and not these comp.* groups. So e-mail
any questions. Thanks.

--Bruce Kaskel
kaskel@math.berkeley.du