1
$\begingroup$

Does anyone know of any formular or algorithm (that runs sub-linear time) for computing the product of all odd integers in an interval in (mod M), or a similar product?

  • 2
    That would depend on the interval (and of course on $M$). What kind of formula is going to give you the product of all the odd integers in the interval $10000\le n\le 10006$, modulo 123456?2011-05-24
  • 1
    What do you *really* mean with "less than linear time"?2011-05-25
  • 1
    @M.B.: http://en.wikipedia.org/wiki/Sublinear_time_algorithm#Sub-linear_time2011-05-25
  • 0
    @Brandon Carter: Yes, it was meant as a question for the OP to think of (with respect to Gerry's reply).2011-05-25
  • 2
    @M.B.: The obvious interpretation (to me, at least) is that the OP is looking for an algorithm which is sublinear in the length of the interval.2011-05-25
  • 2
    @Brandon Carter: I believe that is the correct interpretation as well.2011-05-25
  • 1
    Note that if the interval is too long, then the result is not going to be interesting. So if $M$ is thought of as a constant, we do get a sublinear algorithm...2011-05-25
  • 0
    So let us interpret the problem this way; compute efficiently the product of the odd integers between $\sqrt M$ and $2\sqrt M$, mod $M$. I have no reason to think there's a better way than the direct approach of doing $O(\sqrt M)$ multiplications and reductions.2011-05-25

1 Answers 1

2

I also believe that in general there is no solution that has sublinear complexity. However, here are a few ideas and theorems which can prove useful:

  1. It might be resonable to assume that $M$ is (a power of) a prime. Supposing that you know how to factor $M$ (for instance, the $M$ in the input is guaranteed to be prime or you have a number of different products to compute modulo a given $M$) you can get the answer for $M$ by using Chinese Remainder Theorem for the answers modulo powers of primes dividing $M$.

  2. If $M$ is odd, you may just as well try to compute the product of all numbers in an interval, not just the odd ones. Indeed, working modulo $M$ you get: \begin{align} \prod_{k=a}^b (2k+1) = \prod_{k=a}^b (M+1 + 2k) = 2^{b-a+1} \prod_{k=a}^b (\frac{M+1}{2} + k) = 2^{b-a+1} \prod_{k=a + \frac{M+1}{2}}^{b+\frac{M+1}{2}} k \end{align} and it's easy to compute $2^x$ modulo $M$.

  3. If $M$ is prime, then it suffices to be able to compute factorials. Indeed, you can always assume that the interval you want to multiply is in $[0,M]$ and then the product form of numbers from $a$ to $b$ is just $b! (a!)^{-1}$ and computing inverses is fast.

  4. You can get a slight improvement using the identity $(p-1)! = -1 \pmod{p}$ for $p$ prime. In particular, if $a > \frac{p-1}{2}$ you get $$ -1 = (p-1)! = a! (a+1)(a+2) \dots (p-1) = $$ $$a! (p - (p - a - 1)) (p - (p - a - 2)) \dots (p - 1) = a! (-1)^{p-a} (p-a-1)!$$ so you can easily compute $a!$ knowing $(p-a-1)!$. Thus, it's enough to know factorials from $1$ to $\frac{p-1}{2}$.

All in all, my suggestion is that it might be best to factor $M$, compute and store the factorials modulo prime factors of $M$ and then be able to give answers for any interval in a reasonably short time (but at the price of a lot preprocessing).

I know it's not much, but I'm afraid that there is no solution in the general case.