$x = c + (\lfloor \frac{y}{m} \rfloor \times m) - y$ resulting in negative number

Question

(x + y) mod m = c
or
(x + y) - (floor((x + y)/m) * m) = c

This should be reversible if x is smaller or equal to m so my try is:

x = c + (floor(y/m) * m) - y

Now here is the problem: Sometimes I get negative numbers and I have to say $x = x + m$.

Example:

m = 255, x = 240, y = 111

c = 240 + 1111 mod 255
c = 76

Now I should be able to get $x = 240$ if I know $y$, $m$ and $c$

x = 76 + (floor(1111/255)*255) - 1111
x = 76 + (4 * 255) - 1111
x = 76 - 91
x = -15

Now $-15$ isn't what I wanted to get but $x = 255 - 15$; $x = 240$.

I don't know why and when that happens. I don't see any reasonable explanation here but there has to be one.

Edit:

Since the result is off by m I think the problem is in floor(y/m).

This is where it starts to spit out negative values:

x = m - (y - (floor(y/m) * m))

If $\frac{y}{m} = \lfloor \frac{y}{m} \rfloor$ then it is not going to give any negative values.

Answer 1

Your equation is actually correct, since I noticed it's just your order of operations getting mixed up. In your example, you actually calculated:

m = 255, x = 240, y = 1111
c = (240 + 1111) mod 255
c = 76

To obtain the correct value for c, make sure you do the mod operation first..

c = 240 + (1111 mod 255)
c = 331

Now to check if we can indeed find the original x using your equation:

x = 331 + (floor(1111/255)*255) - 1111
x = 331 + (4 * 255) - 1111
x = 331 - 91
x = 240

What happened is that you ended up calculating (x+y) mod m = c,
is calculating x + (y mod m) = c what you intended instead? I hope this helps.

Answer 2

Thanks to Dr C i know that the revers-function actually belongs to

x + (y mod m) = c

not to

(x + y) mod m = c

The proper if not mathematically perfect revers-function is:

x = c + (floor(y/m) * m) - y
if x <= 0 then
    x = x + m
end

(using lua syntax here, I don't know a mathematical equivalent)

The negative values are because the mod-function "jumps" from m to 1 (or m - 1 to 0) as x exceeds m - (y - (floor(y/m) * m)). Because only the "jump" of the mod-function "breaks" the original revers-function it seems to work (and works when y/m == floor(y/m) because the "jump" is outside the range of the function (x <= m)) for some numbers.