0

I Have this formula: $$(n-1)!(\frac{n(n-1)}{2} + \frac{(n-1)(n-2)}{4})$$ $2\le n\le 100000$. I would like to modulate the result of this from this formula by any modulus, but for the moment let's assume that it is constant, MOD = 999999997. Unfortunately I can't just calculate the result and modulate it, because unfortunately I don't have variables larger than 2^64 at my disposal, so the main question is. What factors to modulate by MOD to get the results%MOD ? Now let's assume that n=19. What is in brackets is equal to 247.5

18! = 6402373705728000. (6402373705728000 * 247.5)mod999999997 = 921442488. Unfortunately, in case I modulate 18! first, the result will be wrong, because (18!)mod999999997 = 724935119. (724935119 * 247.5)mod9999997 = 421442490. How to solve this problem?

Bill Dubuque
  • 272,048
user94824
  • 1

1 Answers1

0

You should not use floating point operations. Use integer values for your modulo operations. YOu can use decimal representation as long as your calculations are exact (nod rounding errrors) because the decimal fraction are equivalent to integer fractions.

Here the error is that $421442490$ is wrong because $$724935119 \cdot 247.5\pmod{9999997} \\ = 421442489.5\pmod{9999997}\\ =421442489+\frac 1 2\pmod{9999997}$$

But $\frac 1 2\pmod{9999997}$ is the multiplicative inverse of $2\pmod{9999997}$ which is $499999999$ because $$2\cdot 499999999=1\pmod{9999997}$$ Therefore $$421442489+\frac 1 2\pmod{9999997}\\ =421442489+499999999\pmod{9999997}\\ =921442488\pmod{9999997}$$ which is the expected result.

You can avoid decimal fractions by either you making things complicate and by calculation $\frac 1 2 \pmod {999999997}$ and $\frac 1 4 \pmod {999999997}$, which are called the modular multiplicative inverses of $2$ and $4$ or by taking an appropriate factor from the $(n-1)!$-term and multiply it to the $\frac{n(n-1)}{2} + \frac{(n-1)(n-2)}{4}$ term to avoid fractions.

$$(n-1)!(\frac{n(n-1)}{2} + \frac{(n-1)(n-2)}{4})\\ =1\cdot2\cdot3 \cdot(5\cdot\ldots\cdot(n-1))\cdot4\cdot(\frac{n(n-1)}{2} + \frac{(n-1)(n-2)}{4})\\ =6\cdot(5\cdot\ldots\cdot(n-1))(2n(n-1) + (n-1)(n-2))$$

miracle173
  • 11,049
  • Not true. Rational decimals make sense in mod arithmetic as long as the corresponding fraction exists, ie. if the lowest term denominator is coprime to the modulus. But decimal notation is rarely used for modular fractions. – Bill Dubuque Nov 20 '21 at 09:37
  • @BillDubuque I wrote floating point operations – miracle173 Nov 20 '21 at 09:40
  • The floating point operations will still work fine for modular arithmetic as long as one has enough precision (i.e. so that the float result is the correct rational result), and presuming the mod operation has the logic to deal with decimals and fractions (not all computer algebra systems implement such). – Bill Dubuque Nov 20 '21 at 09:42
  • Worth mention: it is not clear if the multiplication will be a floating point product or a modular product. That depends on the computer algebra system. – Bill Dubuque Nov 20 '21 at 09:56