🚀 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.
>
>--

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 works because 5 always follows 4, 4 x 5 = 20 (2),
and 2 is half of 4.

You can make a multiplication table:

    old  1  2  3  4  5  6  7  8  9
new
1        1  2  -  4  -  6  -  8  -
2        2  4  -  8  -  2  -  6  -
3        -  6  -  2  -  8  -  6  -
4        -  8  -  6  -  4  -  2  - 
5        -  4  -  8  -  2  -  6  - 
6        -  2  -  4  -  6  -  8  -
7        -  4  -  8  -  2  -  6  -
8        -  6  -  2  -  8  -  6  -
9        -  8  -  6  -  4  -  2  - 

The only factorials whose last non-zero digit is odd are 0! and 1!

    static int table[9][9] =
    {{1, 2, 0, 4, 0, 6, 0, 8, 0 },
     {2, 4, 0, 8, 0, 2, 0, 6, 0 },
     {0, 6, 0, 2, 0, 8, 0, 6, 0 },
     {0, 8, 0, 6, 0, 4, 0, 2, 0 }, 
     {0, 4, 0, 8, 0, 2, 0, 6, 0 }, 
     {0, 2, 0, 4, 0, 6, 0, 8, 0 },
     {0, 4, 0, 8, 0, 2, 0, 6, 0 },
     {0, 6, 0, 2, 0, 8, 0, 6, 0 },
     {0, 8, 0, 6, 0, 4, 0, 2, 0 }}; 

    int last_non_zero_digit_of_factorial(n) {
      digit = 1;
      for (int i = 2; i < n ; ++i) {
	while (i % 10 == 0) i /= 10;
	digit = table[digit-1][i-1];
      }
      return digit;
    }

This solution runs in O(n).  With a bit more thought a log(n) solution
is possible.  Each cycle from 1-9 multiplies the last digit
of the factorial by 8, so the last digit in 30! is equal to the 
last digit of
  8 [for 1-9] x 8 [for 11-19] x 8 [for 21-29] x 2 [20] x 3 [30] = 2.

The last digit of 427! is equal to the last digit of
  8**41 [1-9,11-19,...,411-419] x 8**4 [10-90,110-190,210-290,310-390]
   x 1 [410] x 2 [420] x 1 [100] x 2 [200] x 3 [300] x 4 [400]   	

  = 8 x 6 x 2 x 2 x 3 x 4 (mod 10)
  = 4 (mod 10)

The code is left as an exercise for the reader.
-- 
Kevin Cline