[picomancer]

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.