# An algorithm to find values m, x, and b for y = m x + b

1. Jul 8, 2015

### chakr

Hi, is there away to find values of m, x, and b for a given value of y. For example, if I have y = 10000, my 'm' could be 100, x = 100, and b = 0, or it could be m = 250, x = 40, and b = 0 or any other combination of m, x, and b. I need to write a C code for my microcontroller. I will be given various values of 'y' all of them are integers, my C code will have to compute values of m, x, and b. One restriction is that the maximum value of y, m, and b is 255 and minimum is 0. How can I approach this problem?
Thank you.

2. Jul 8, 2015

### Staff: Mentor

One way would be to use a "brute force" approach with three nested loops, where the loop indexes range over the x, m, and b values of 0, 1, 2, ..., 255. Statements in the innermost loop would execute 256 * 256 * 256 times (16,777,216 times). In the innermost loop compare the given y value with the computed value of m*x + b. If the two are equal, either print the m, x, and b values, or store them in some way.

3. Jul 8, 2015

### chakr

Thank you Mark, if I understand right:

<< Code tags added for readability by Moderator >>
Code (Text):

for(m=1; m<256; m++){
for (x=1; x<256; x++){
for (b = 0; b<256; b++){
y' = m * x + b;
if (y == y')
// save m, x, b and exit the loop
}
}
}
I think it will work, thank you.

4. Jul 8, 2015

### Staff: Mentor

A few changes:
Code (Text):

for(m=0; m<256; m++){
for (x=0; x<256; x++){
for (b = 0; b<256; b++){
if (y == m * x + b)
// save m, x, b and exit the loop
}
}
}
I changed the starting values of the loop variables to 0, based on your first post. Also, if all you need to find is one set of values for m, x, and b, then your comment about exiting the loop is fine. It's possible, though, that there will be multiple sets of values that work, so you would want to let all of the loops run to termination.

5. Jul 8, 2015

6. Jul 8, 2015

### chakr

Thank you for your help.

7. Jul 8, 2015

### jbriggs444

Given a working "brute force" solution, can you think of any ways to optimize it? For instance, could the innermost loop be converted into something more efficient?

8. Jul 8, 2015

### geoffrey159

There is a solution that saves you 1 inner loop

Code (Text):
for(b=0; b<256; b++){
for (x=1; x<256; x++){
if ( ( (y-b) mod x) == 0)
// then m = (y-b)/x
// save m, x, b and exit the loop
}
}
}
But you will get better help posting this question in a computer science forum

9. Jul 8, 2015

### geoffrey159

Could it be more efficient to generate an auxiliary table of prime numbers less than 256, there are 54 of them, and try to find the prime factors of $y-b$ for all b's with their multiplicity ?

10. Jul 8, 2015

### jbriggs444

Before one goes to that trouble, the problem should be clarified. If the task is to find a single (m, x, b) tuple that fits a given y then there is a much simpler approach available.

11. Jul 9, 2015

### WWGD

I am not sure I understand, why not start with y=10,000, m=10,000 , x=1, b=0, increase x, and then do the Euclidean Algorithm if x does not divide 10,000 and select b to be the remainder. Maybe I am missing something obvious?

10,000 = 10,000(1)+0
10,000 = 5,000(2)+0
10,000 = 3,333(3)+1.....

But apply it to your values:
10,000 =255(39)+55
10,000=254(39)+94
10,000=253(39)+133
........

Euclidean algorithm guarantees all will be less than 255.
Sorry if I am missing something obvious.

12. Jul 10, 2015

### jbriggs444

If you are simply after a 3-tuple (m, x, b) that satisfies y = mx + b with the constraint that m, x and b are all between 0 and 255 inclusive then there is a simpler algorithm.

Hint: Is there a single value for m that works for all values of y for which a solution is possible at all?

Edit: missed the thrust of WWGD's post -- he is describing an approach to find all solutions, not just one.

But it is not clear how x is to be handled. Is it to be optionally increased for each successive m? If so, that's a problem.

Take y = 200. Then solutions include:

m = 10, x = 20, b = 0
m = 10, x = 19, b = 10
m = 10, x = 18, b = 20
...
m = 10, x = 0, b = 200
m = 9, x = 22, b = 2
m = 9, x = 21, b = 11
...

A sweep over all of the m's and x's cannot take place in an easy determined, monotone increasing pattern for both parameters. But... The range of plausible x's for a given m is determinable.

Last edited: Jul 10, 2015
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook