Possible to Solve for a Variable Using Equation with Integer Division and Modulus?

Question

Quick summary: I am a programmer who has an equation using integer division and modulus operators, and just need to solve it for a variable.

I'm working on a C++ program to distribute a matrix across several computers, and the matrix is split up by columns based on the number of computers and the size of the matrix. I have an equation for determining the start and end columns that should be on a given computer. The parameters are:

$\;\;\;\;n$ $-$ the number of columns or rows of an $n \times n$ matrix,

$\;\;\;\;id$ $-$ the id of a computer (e.g. $0, 1, 2, \cdots$)

$\;\;\;\;c$ $-$ the number of computers.

The equations for start and end columns are

$$startColumn(id, n, c) = id \times\left(\frac{n}{c}\right)+\min\left(id, n\%c \right)$$ $$endColumn(id, n, c) = startColumn(id+1, n, c) - 1$$

Note that division in this case is integer division in C++, e.g. 7/4=1, and $\%$ represents the modulus operator.

What I want to do is solve these equations for $id$. That is, given a column (called col), n, and c, you can find which id (computer) that column belongs to. I'm having trouble with the mathematics of this given the min function, modulus, and integer division involved. Perhaps it is quite simple, the closest I've gotten is this very simple formula, but it seems to be off by 1 in some cases.

$$id(col, n, c ) = \frac{col\times \min(c,n)}{(n)}$$

Of course I could solve experimentally, by generating the $startColumn$ and $endColumn$ for each computer until I find the computer that holds the column I'm looking for, but I'm trying to do this directly, using a single equation.

Answer 1

In your setup, the first $n\%c$ blocks of columns have width $\frac nc+1$, and the remainder have width $\frac nc$. So one can write $$ id(col,n,c) = \begin{cases} \displaystyle \frac{col}{\frac nc+1} , & \text{if } \displaystyle 0 \le col < (n\%c)\bigg( \frac nc+1 \bigg) , \\ \displaystyle n\%c + \frac{col - (n\%c)\big( \frac nc+1 \big)}{\frac nc} , & \text{if } \displaystyle (n\%c)\bigg( \frac nc+1 \bigg) \le col < n .\end{cases} $$

Answer 2

I'm going to be a jerk and not answer the question you asked ... but hopefully in a helpful way!

To me, the most natural way to accomplish this task is actually to define the $id$-finding function first, as a function of $col$, $n$, and $c$. And a natural definition that splits the columns up as equally as possible among the $c$ computers is $$ id(col,n,c) = \frac{c\times col}n $$ (integer division). Like in your setup, each computer receives either $\frac nc$ or $\frac nc+1$ columns; but unlike in your setup, where the $1$-extra-column blocks all went to the smallest $id$s, here those blocks are spread pretty uniformly throughout the $id$s.

The reason I like this is that it is mathematically easier to invert: $$ startColumn(id,n,c) = \frac{id\times n}c $$ (with your definition of $endColumn$ in terms of $startColumn$). Note this is very close to your original definition, but again with the $1$-extra-column blocks spread uniformly through the $id$s.