Okay, so here's an example of where dropping out of math classes after Differential Equations is coming back to bite me a bit. I'm working on a kind of puzzle, mostly for fun, but possibly to incorporate into a future software product.
At its most basic, the solution process for the puzzle turns out to be solving a system of simultaneous equations. Which is something I learned how to do way back in High School, and for linear equations, I can even find off-the-shelf algorithms and libraries for doing so.
The catch, of course, is that these aren't linear equations. They use modular arithmetic, which is something I understand at a basic level, like anybody who programs for a living probably does, but I don't know where to even start breaking this down to solve a non-trivial version, and Google isn't helping me.
Let's start with a simple linear example:
5x + 7y + 4 = 0
4x + 3y + 1 = 0
Use whatever method you like, and you get:
x = 0.3846
y = -0.846
Piece of cake. Now, what if the equation looks like this?
5x + 7y + 4 = 0 (modulo 16)
4x + 3y + 1 = 0 (modulo 16)
If we want to find a few integer solutions for x and y, how do we find them? I could write a program to just guess every integer between 1 and 1,000,000 for each of the coefficients, and that'd find me a solution, but it doesn't scale well if I have a large number of variables. In the example equations given, there are rather a lot of solutions ([9,9],[9,25],[25,25]...), but I suspect that some other (carefully chosen?) sets of coefficients would have a much smaller set of solutions. Actually, that's kind of the point of the whole exercise.
Anyone out there got some hints for me?
Googling "simultaneous modular equations" got me:
http://en.wikibooks.org/wiki/Discrete_mathematics/Modular_arithmetic#Simultaneous_equations
and
http://www.nada.kth.se/~johanh/rsalowexponent.ps
,both of which are interesting, but not quite what I'm looking for.
For the case where the modulus is 2, addition is equivalent to XOR, and so logic minimization techniques from EE can be used, but it's not clear to me how to move those up to work in a higher modulus.
2 comments:
Try a MIP solver like Xpress-MP at www.dashoptimization.com.
Formulate your problem as a mixed integer program by adding auxiliary variables z1 and z2 and make the right hand sides 16*z1 and 16*z2 to your equations.
Examples like this, with the same modulus for all equations, seem soluble via variable elimination and back-substitution. You just have to remember that in modular arithmetic you can't really "divide" the way we can for reals.
In your example, multiply equations by (4, 5) so we have the same x multiplier:
20x + 28y +16 = 0
20x + 15y + 5 = 0
Subtract eq 2 from eq 1:
13y + 11 = 0.
Find the modular inverse of 13 (mod 16), which is 5:
5(13y + 11) = 0
y + 55 = 0
y = -55 = 9
Now back-substitute to find x:
5x + 7*9 + 4 = 0
5x + 67 = 5x + 3 = 0
Now multiply by the inverse of 5, which we happily know is 13:
x + 39 = 0
x = -39 = 9
So the solution is x = 9, y = 9. Of course, you can add multiples of 16 to either variable!
Some notes:
* You can look at this process as Gaussian elimination on matrices, if you prefer. Just don't divide, multiply by inverses!
* To find modular inverses, you can use the extended Euclidean algorithm, the wikipedia page is OK: http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
* If your equations have different moduli, I think you can just convert them all to the LCM modulus.
* If you write code to do this, it will have to deal with a number of cases.
- Just as with real systems of equations, there will sometimes be no solutions, "one" solution, or many solutions. I put "one" in quotes, because you can always add multiples of the modulus.
- There is also the new case where even a single equation is non-soluble because no modular inverse exists, eg: 2x = 5 (mod 16).
Post a Comment