News for hackers. Stuff that matters.
Re:Helping a stranger, and why you should understand NP-comp... by fjwolski on Monday November 04, 2013 @02:30PM (#6670611)
There're few other things you can do to possibly speed up the second code snippet, by reducing dimensionality:

1) recognize q1 * q2 = 2^p1 * 2^p2 = 2^(p1 + p2), so instead of iterating over q1 then q2, iterate over p = p1 + p2

2) memorize some of the combinations; e.g. if you iterate over p, r1 & r2, then you know that all you're trying to find is two integers f1 & f2 that are equal to output * r1 * r2 * 2^p / input; so before you start solving the problem, calculate table T:

  for (int f1 = 1; f1 <= 256; ++f1)
    for (int f2 = 1; f2 <= 256; ++f2)
      T[f1 * f2] = f1
now you can check whether integer pair (f1,f2) exists, you can just check whether T[output * r1 * f2 * 2^p / input] is non-zero. Also, output * r1 * r2 * 2^p has to be divisible by input, so after you iterate over p & r1, you can iterate only over r2's being multiples of input / gcd(input, output * r1 * 2^p)

There could be possibly some more tricks found.

Re:Helping a stranger, and why you should understand NP-comp... by bazzargh on Monday November 04, 2013 @04:12PM (#6671201)
Another way to reduce the number of loops:

          for (int q2 = 1; q2 <= 256; q2 <<= 1)
            if (output * r1 * r2 * q1 * q2 == input * f1 * f2)
This doesn't need a loop. Set q2 directly and test if it is a power of 2.

     n2 = input * f1 * f2;
     d2 = output * r1 * r2 * q1;
     q2 = n2/d2;
     if (__builtin_popcount(q2) == 1 && q2 * d2 == n2) {
... taking advantage of the fact that calculating the Hamming weight of q2 doesn't need a loop.

http://en.wikipedia.org/wiki/Hamming_weight