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!

Number of operations required to reach value.

  1. Jan 15, 2013 #1

    trollcast

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data
    Given a limited set of operators, specifically increment and bitshift left (only 1 bit at a time) Calculate the number of operations required to get from a certain number to another.

    Eg. 9 to 20 = 2 [(9++)LSHIFT]

    2. Relevant equations

    3. The attempt at a solution

    I haven't started to code for it yet but I'm just wondering if my method is going to be far too inefficient at finding solutions.

    If we start off with the lowest number and repeatedly multiply by 2 until it is larger than the higher number. Then Divide by 2 and repeatedly add 1 until you reach the higher number.

    Go back to the lower number add 1 and repeat as above.

    EG. 8 to 36

    attachment.php?attachmentid=54766&stc=1&d=1358280661.png

    The only thing is for very large numbers I don't think this wouldn't be very efficient?

    PS. Just to clarify the code isn't restricted to only those 2 operators.
     

    Attached Files:

  2. jcsd
  3. Jan 15, 2013 #2

    rcgldr

    User Avatar
    Homework Helper

    You're not being asked to create an efficient algorithm, just one that works by producing the smallest total number of shift and increment operations. Your current approach doesn't handle the case where increments should occur between shift operations, such as shift 2, increment 1, shift 2, increment 1, shift ... .

    You'll also need to handle cases like from 9 to 17, which requires 8 increments, 0 shifts.
     
    Last edited: Jan 15, 2013
  4. Jan 15, 2013 #3

    trollcast

    User Avatar
    Gold Member

    Yeah sorry, the problem basically is to work out the lowest number of left shifts and / or increments needed to get from 1 number to another.

    You can use any program functions or operators needed to work that out.
     
  5. Jan 15, 2013 #4

    rcgldr

    User Avatar
    Homework Helper

    After re-reading the problement statement, I updated my previous post, read it again.
     
  6. Jan 15, 2013 #5

    trollcast

    User Avatar
    Gold Member

    Thanks,

    So by extension of my previous method would a binary tree with the left branches being shifts and the right branches being increments at each node with some code to terminate branches if they overshoot the target number or to store the depth of the node if the value of that node is equal to the target.

    The only issue would be if you gave it a small number say 11 and then a very large number such as 10000 as there would be a lot of branches to calculate that won't lead to even the correct answer?
     
  7. Jan 16, 2013 #6

    rcgldr

    User Avatar
    Homework Helper

    Try working the algorithm backwards, start with the larger number, then use right shifts and decrements to get the smaller number. That may be an easier problem to optimize. Some of the steps will be more obvious when starting with the larger number, for example, if the larger number is odd, you need to decrement before right shifting.
     
    Last edited: Jan 16, 2013
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook