Algorithms

Luc Pattyn wrote:

countN tells me how many factors of n! end on digit N

count5 += count10;	
if (count5 != 0) 
   {
   result = (result * rightmostNonzeroInFactorial(count5)) % 10;
   count2 -= count5;
   }

if (count5 != 0) 
   {
   result = (result * rightmostNonzeroInFactorial(count5)) % 10;
   count2 -= count5;
   }
if (count10 != 0) 
   {
   result = (result * rightmostNonzeroInFactorial(count10)) % 10;
   }

cp9876 wrote:

...

There is a little known fact (don't ask me how I know it!) that

if n = 5q+r with 0 <= r < 5

then n! has the same rightmost non-zero digit as 2^n x q! x r!

def f(n):
    result = 1
    while n > 1:
        n, r = divmod(n, 5)
        result = result * (6, 2, 4, 8)[n & 3] * (1, 1, 2, 6, 4)[r] % 10
    return result

and that can be simplified a bit by using a larger table:

FACTAB = 6, 6, 2, 6, 4, 2, 2, 4, 2, 8, 4, 4, 8, 4, 6, 8, 8, 6, 8, 2

def f(n):
    result = 1
    while n > 1:
        result = result * FACTAB[n % 20] % 10
        n //= 5
    return result

bool nonzerodigit(const unsigned int& n, unsigned int& result)
{
   if (n > 100000) return false;
   unsigned int result = 1;
   for (unsigned int i = 1; i <= n; ++i)
   {
      unsigned int f = i;
      while (0 == (f % 5))
      {
         f /= 5;
         result /= 2;
      }
      result = (result % 100000) * f;
   }
   result %= 10;
   return true;
}

Edmundisme wrote:

Thanks!

beko wrote:

Just translating the edges with the offset distance will not work.

beko wrote:

I have found an algorithm not tested throughly, but it is working at least for my very simple 3 points polyline test