# Simultaneous equations for more unknowns than equations

I have a system of equations. This system is 8 equations for 16 unknowns. Is it possible to solve the equations for some answer? By that, I mean, it's highly likely that they will have several possible answers, but I only need one. I have only ever covered solving simultaneous equations for exact answers where the number of equations is equal to the number of variables.

All of the equations probably involve all of the unknowns. But since each one is 15MB to express, I didn't check.

As an aside, the equations are guaranteed to contain only relatively simple operations, specifically, addition (modulo 2^32), binary rotation (by constant only), right shift (by constant only), exclusive or, negation, and binary AND. No squares or exponentials or anything like that.

Edit: We are talking about something like this. But bigger. A lot bigger. Where h[7] means that this corresponds to the 8th input, and c[i] corresponds to the ith output. I reduced the complexity a lot, so it's more digestible. The real thing is a lot bigger. And there's 8 of them.

Edit: I eventually determined that the reason the final equations are so large is because there are many, many intermediate variables. If expressed as these variables, then it becomes much more managable- the whole kaboodle in only 64kb, and shown here.

Now, given h[0] - h[7], I definitively solved for 113 of the 2271 states. However, going further than that gave me problems- there are so many states that I can't identify any simultaneous equations to attempt to solve, or any other method of proceeding.

I identified 24 equations where one term is known (one of the 113) and the other two are unknown variables. Is this the part where I start adding in information?

• What kind of equations? Linear equations? Polynomial equations? If they are linear equations, then there is a standard method to generate all solutions: Gaussian elimination. – Arturo Magidin May 17 '12 at 5:11
• @Arturo: I'm not entirely familiar with the kinds of equation, but they are not polynomial in that the only power any variable is raised to is 1. I think it's non-linear, the Wiki page only ever suggests multiplication and addition, whereas I have addition and a bunch of binary operations. – DeadMG May 17 '12 at 5:14
• A "linear equation" is one of the form $a_1x_1+a_2x_2+\cdots+a_nx_n=c$, where $x_1,\ldots,x_n$ are the unknowns, and $a_1,\ldots,a_n,c$ are constants. What kind of operations do you have? – Arturo Magidin May 17 '12 at 5:16
• @Arturo: I listed them at the bottom of the question. Only addition and binary rotation, shift, xor, and negation. Not even multiplication (although arguably, a shift could be expressed as a multiplication). – DeadMG May 17 '12 at 5:17
• @DeadMG If you suspect, that you might get more than one solution i.e. if you have degrees of freedom, you can set some of the variables to take some specific value so that you can find 'a' solution to your problem. – user17762 May 17 '12 at 5:19

How can the equations be 15 MB each? Given the edit, the equation for h(7) is only 2582 characters. But if you want to solve for more unknowns than equations you need special constraints. For example $x^2+y^2+z^2=0$ is one equation in three unknowns, but has only one solution. This can be harder to detect in a system. You can introduce an error term into each equation, sum the squares and feed it to a multidimensional minimizer. Change each $a=b$ to $a=b-e_i$ and then say $error = \sum e_i^2$ and minimize $error$ over the variables. This is a numeric solution, not an algebraic one. If the equations are easy, this will work.
• What kind of special constraints are we talking about, exactly? I can guarantee at least one solution. Indeed, the equations more resemble the form x + y + z = c; for some c, which yields many solutions. – DeadMG May 17 '12 at 6:51