0

Possible Duplicate:
Fast way to calculate n! mod m where m is prime?

Let:

int k = 99999989;

k is a prime number.

Given some (32-bit) int x, we want to calculate x factorial mod k. (x! % k)

One way to do this is as follows:

int factmk(int x)
{
    long long t = 1;

    for (long long i = 2; i <= x; i++)
    {
         t *= i;
         t %= k;
    }

    return (int)t;
};

This requires O(x) time, and O(1) space.

Is there an asymptotically faster way to implement factmk in straight C in less than or equal to O(logx) space? If yes, what is it? If no, sketch proof.

Community
  • 1
  • 1
Andrew Tomazos
  • 66,139
  • 40
  • 186
  • 319
  • Possibly move to http://math.stackexchange.com? There are some amazing whizzes over there you could talk too.. – Richard J. Ross III Jun 09 '12 at 20:05
  • 4
    Well, if `n >= k`, then `n! % k == 0`, so it's O(1) ;) – Daniel Fischer Jun 09 '12 at 20:05
  • presumably lookup tables are out of the question :-P – will Jun 09 '12 at 20:07
  • Apart from that, it's a good question, but a duplicate. You can reduce the work, but no way to reduce it much below `k/2` multiplications. – Daniel Fischer Jun 09 '12 at 20:09
  • @DanielFischer: Well technically there are a finite number of inputs, so a lookup-table is O(1) time and O(1) space, but I think you know what I mean. – Andrew Tomazos Jun 09 '12 at 20:11
  • Yes, and the best I can offer is `min(n-1, k-n-1)` modular multiplications, cf. the duplicate. – Daniel Fischer Jun 09 '12 at 20:13
  • @daniel: it is not an exact duplicate. This question in C — the other in Python (some people can't read Python) – jfs Jun 09 '12 at 20:29
  • Given that the question is about the algorithm and barely refers to implementation details (C) then I agree that it's a duplicate and whether it's "exact" is a matter of semantics rather than substance. A straightforward solution in Python should, effectively, be close enough to psuedo-code that anyone skilled in programming should be able to understand the gist of it regardless of whether they know that particular programming language. (A solution implemented using idiomatic Python's list comprehensions, decorators and such might not be quite so clear, of course). – Jim Dennis Jun 10 '12 at 07:51

1 Answers1

0

This isn't a general answer, but as a special case, if x = k-1, you can use Wilson's theorem

(x)! = -1 mod k

or 

(p-1)! = -1 mod p
gliderkite
  • 8,828
  • 6
  • 44
  • 80
Brian
  • 23
  • 4