1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Jul 8, 2015 #1

    chakr

    User Avatar
    Gold Member

    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. jcsd
  3. Jul 8, 2015 #2

    Mark44

    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.
     
  4. Jul 8, 2015 #3

    chakr

    User Avatar
    Gold Member

    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.
     
  5. Jul 8, 2015 #4

    Mark44

    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.
     
  6. Jul 8, 2015 #5

    chakr

    User Avatar
    Gold Member

     
  7. Jul 8, 2015 #6

    chakr

    User Avatar
    Gold Member

    Thank you for your help.
     
  8. Jul 8, 2015 #7

    jbriggs444

    User Avatar
    Science Advisor

    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?
     
  9. Jul 8, 2015 #8
    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
     
  10. Jul 8, 2015 #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 ?
     
  11. Jul 8, 2015 #10

    jbriggs444

    User Avatar
    Science Advisor

    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.
     
  12. Jul 9, 2015 #11

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  13. Jul 10, 2015 #12

    jbriggs444

    User Avatar
    Science Advisor

    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




Similar Discussions: An algorithm to find values m, x, and b for y = m x + b
  1. (x^a)^b = x^(ab)? (Replies: 18)

  2. Y=mx+b Solving for m (Replies: 7)

Loading...