Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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? –  Gerry Myerson May 24 '11 at 23:50
1  
What do you really mean with "less than linear time"? –  M.B. May 25 '11 at 1:21
1  
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. –  Brandon Carter May 25 '11 at 1:49
2  
@Brandon Carter: I believe that is the correct interpretation as well. –  M.B. May 25 '11 at 1:53

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.