News for hackers. Stuff that matters.
Re:Helping a stranger, and why you should understand NP-comp... by picomancer on Monday November 04, 2013 @06:47PM (#6672028)
This is actually a number theory problem. You want to have

    input * A = output * B         (1)
where

    A = f1 * f2                    (2)
    B = r1 * r2 * q1 * q2          (3)
where q1, q2 are powers of two.

Any good elementary number theory book will tell you that the smallest solution to (1) is to let M = lcm(input, output) and set A = M / input, B = M / output. Given the further constraint that A <= 2^16, you can compute offline a 2^16 element lookup table which gives values of f1, f2 in the desired ranges for each possible value of A. You can re-use the same table to go from your B value to r1, r2 if you first pull out as many powers of two as you can and put them in q1, q2.

There are no comments on this comment yet.