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

[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.

 

[Mark44]

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.

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.

 

[chakr]

Thank you Mark, if I understand right:

<< Code tags added for readability by Moderator >>

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.

 

[Mark44]

Thank you Mark, if I understand right:

<< Code tags added for readability by Moderator >>

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.

A few changes:

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.

 

[chakr]

A few changes:

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.

 

[chakr]

Thank you for your help.

 

[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?

 

[geoffrey159]

There is a solution that saves you 1 inner loop

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

 

[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 ?

 

[jbriggs444]

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 ?

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.

 

[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.

 

[jbriggs444]

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?

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.