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

  • Thread starter chakr
  • Start date
  • Tags
    Algorithm
In summary, the conversation discusses the problem of finding values for m, x, and b given a value of y in order to write C code for a microcontroller. One approach suggested is to use a "brute force" method with nested loops, but there is a more efficient solution that eliminates one inner loop. The code will have to handle y values ranging from 0 to 255 and the output values for m, x, and b must also fall within this range.
  • #1
chakr
Gold Member
34
2
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.
 
Mathematics news on Phys.org
  • #2
chakr said:
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.
 
  • #3
Thank you Mark, if I understand right:

<< Code tags added for readability by Moderator >>
Code:
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
chakr said:
Thank you Mark, if I understand right:

<< Code tags added for readability by Moderator >>
Code:
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:
Code:
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
Mark44 said:
A few changes:
Code:
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.
 
  • #6
Thank you for your help.
 
  • #7
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?
 
  • Like
Likes rikblok
  • #8
There is a solution that saves you 1 inner loop

Code:
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
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
geoffrey159 said:
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.
 
  • #11
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
WWGD said:
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.
 
Last edited:

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

1. How does the algorithm find the values of m, x, and b?

The algorithm uses a mathematical formula to calculate the values of m, x, and b based on the given equation y = mx + b.

2. What are the inputs for the algorithm?

The inputs for the algorithm are the values of y and x, which are known from the given equation y = mx + b.

3. Is the algorithm accurate?

Yes, the algorithm is accurate as it uses a precise mathematical formula to calculate the values of m, x, and b.

4. Can the algorithm be used for any linear equation?

Yes, the algorithm can be used for any linear equation in the form of y = mx + b, where m and b are constants and x is the variable.

5. How long does it take for the algorithm to find the values of m, x, and b?

The time taken by the algorithm to find the values of m, x, and b depends on the complexity of the given equation. For simple linear equations, the algorithm can find the values quickly, while for more complex equations, it may take longer. However, the algorithm is generally efficient and can find the values in a reasonable amount of time.

Similar threads

  • General Math
Replies
5
Views
999
Replies
1
Views
977
Replies
2
Views
1K
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
17
Views
554
Replies
7
Views
2K
  • General Math
Replies
1
Views
745
Replies
1
Views
838
Replies
3
Views
2K
Replies
1
Views
2K
Back
Top