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.
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:
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.