1
$\begingroup$

I wanted to calculate the power of $2$ raised to a number $a$, divided by another number $b$ and then take the modulo $K$ of this quantity.

Meaning, I basically wanted $(2^a/b) \mod K$. Take an example where $a = 4$, $b = 3$ and $K = 98765431$. For this I calculated $3^{-1} \mod K$. Which comes out to be 65843621 *. If this inverse is correct and I now do $(2^4 \cdot 65843621) \mod K$, the answer comes out to be incorrect. I don't know what the problem with my approach is.

*The way I calculated inverse is the following. $3 \cdot x = 98765431 \cdot n + 1$, so I iterated over $n$ to see when $98765431 \cdot n + 1$ is divisible by $3$ and then $x$ is my desired inverse.

  • 0
    What is your result? What do you compare your "incorrect" result to? Where does this number come from?2012-08-31
  • 1
    I got the same inverse for three that you did. That gives $$2^4\cdot 3^{-1}\equiv 65843626\pmod{K}$$ as the result. Did you get the same? If yes, why do think this would not be correct? You can also calculate this as $$\frac{16}3=5+\frac13\equiv 5+65843621=65843626\pmod{K}.$$2012-08-31
  • 0
    Ok, at the risk of sounding stupid, $2^4 = 16$ and $16/3 = 5$ so I should be getting $5%K = 5$, since $5 < K$. And I did get $65843626$ as the result too.2012-08-31
  • 0
    $$\frac{16}3=5.333\ldots=5\frac13\neq5???$$2012-08-31
  • 1
    $\frac {16}{3}=5+3^{-1}$ and $3^{-1}=65843621$2012-08-31
  • 0
    I wanted the floor value of the division..2012-08-31
  • 3
    Floor doesn't mix with modular arithmetic. Sorry. Integer arithmetic is always precise.2012-08-31
  • 0
    Oh, isn't there any other way then, to get the quantity that I wanted? I mean $(2^a/b)\mod K$ ? I need to solve an algorithm problem, and one way to do it demands me to calculate this quantity. You can too, probably take a look at the problem http://www.spoj.pl/problems/SUMSUMS/2012-08-31
  • 0
    Looks like I will have to chuck my current approach and look for a more novel technique. I can actually solve this problem using matrix exponentiation, but I am not able to reduce this matrix size to a constant :(2012-08-31

1 Answers 1

4

Ok. Comments revealed the source of the confusion. As a general philosophy here I want to mention the following. In the ring $R=\mathbb{Z}_K$ the residue class of $3$ has an inverse, namely the residue class of $65843621$. What this means is that we are replacing "division by $3$" with "multiplication by $65843621$". The result of such a multiplication is another integer (or a residue class modulo $K$ to be precise). What this means is that the result is "accurate". There is no rounding error.

Another way of saying the same thing is that because $3$ is a unit in the ring $R$, every other element of the ring is exactly divisible by $3$.

Another thing that newcomers to modular arithmetic often have problems with is the following. In a ring like $R$ here there is no meaningful$^{*)}$ concept of a size of an element, nor a meaningful way of saying that one element is larger than another. For example, if we assume that $0<1$, then we probably want to accept as a consequence that $1=0+1<1+1=2$, and as another consequence that $0<1<2$, so $0<2$. Continuing in this way we would have to accept as a consequence that $0. But here $K-1\equiv -1$, so we end up with $0<-1$. This renders the order relation useless.

The floor function ultimately depends on a sense of "betweenness" (a real number between two consequtive integers), so it, too, becomes meaningless in rings of modular integers.

$^{*)}$ Ok, some meaningful metrics can sometimes be defined, but they follow somewhat different rules than the familiar absolute value.


The problem that OP linked to is about the following. Let $J$ be the all ones $n\times n$ matrix, and let $I$ be the identity matrix with $n$ rows. A calculation by $n$ "cows" is to be carried out $T$ times. A single round of the calculation amounts to multiplying a certain vector with $n$ components, all from the ring $R$, with the matrix $-I+J$ (obviously modulo $K$). Altogether the task at hand is to efficiently compute the matrix power $$ A_T=(-I+J)^T, $$ where $T$ is a large integer.

Here we have the "atomic" rules $I\cdot I$, $I\cdot J=J$ and $J\cdot J=nJ$. As always, when computing large powers in a ring of modular integers, the so called square-and-multiply method works. As a consequence of the above rules we get the formula $$ (aI+bJ)(cI+dJ)=acI+(ad+bc+bdn)J, $$ all the coefficients are to be reduced modulo $K$. That's all we need! By induction we see that for all natural numbers $k$ $$ A_k=f(k)I+g(k)J, $$ and the task at hand is to compute the integers $f(T)$ and $g(T)$. All you need to do is to first compute $A_2$, $A_4$, $A_8$, $\ldots$ by repeated squaring $\log_2(T)$ squarings. Then you need to multiply the appropriate ones together using the above rule. Shouldn't take too long. Edit: Observe that you only need to compute and store the integers $f(k)=(-1)^k$ and $g(k)$ for the relevant integers $k$.

  • 0
    @nonChun: I added my take of the cow problem. Didn't double check anything, but it seems to me that this is what is required.2012-08-31
  • 0
    I understand this method, and I wanted to use it too, but if n is large say 50000, then the matrix sizes $O(n^2)$ become huge!2012-08-31
  • 0
    @nonChun: If I understood correctly, you don't have to store the matrices. Only the numbers $f(k)$ and $g(k)$. You only need the "full" matrix at the end, when computing the cows total output. Also, it seems to me that $f(k)=(-1)^k$, so there is only $g(k)$ to worry about.2012-08-31
  • 0
    Hey jyrki, I was able to reduce the problem of finding the coefficients of I and J to finding the exponentiation of a 2x2 matrix and my solution got accepted! Thanks for the pointers :) btw, why did you think of breaking the problem into I - J , and not the original matrix?2012-09-01
  • 0
    @nonChun: Congrats! Well done. As you said, computing the power of a 50000x50000 matrix is kind of difficult for reasons of storage alone. About $I-J$? Well, that seemed to be a simple way of making progress, and codifying the fact that all the cows were following the same algorithm. I seem to have accumulated some experience in seeing things like that right away?2012-09-01
  • 0
    Wonderful! This seems like a cool trick. Thanks to you, I learned something new :)2012-09-01