[font="Courier New"]//The red text I don&#39;t get. Doesn&#39;t that just reduce the maximum amount of iterations? But if I&#39;ve hit the maximum, wouldn&#39;t it be because I&#39;m needing to, to reduce the fraction?<br /> // I don&#39;t see how this speeds it up. Rather, it looks like it&#39;ll cost an extra divide and a std::min(), every iteration, while only getting rid of some mods if the number happens<br /> //to be a large one. That is to say, you&#39;re trading some speed of the majority of the cases, for optimized speed if the numerator or denominator is a multiple of a large (3 digit or more) prime number. Unless I&#39;m misunderstanding what&#39;s happening here…<br /> j /= 2; <br /> for (int i = 2; i &lt;= j; i++) {<br /> while((Num % i == 0) &amp;&amp; (Denom % i == 0)) {<br /> Num /= i;<br /> Denom /= i;<br /> j = std::min(Num,Denom) / 2;<br /> }<br /> }<br /> }<br /> return IntToString(Num) + &quot;:&quot; + IntToString(Denom);<br /> </blockquote>I don&#39;t entirely understand the extra divide by 2 so I won&#39;t explain why that saves time. I will explain why the idea of recalculating j makes sense. Lets add up exactly what&#39;s going on. First, if we assume the std::min is useless (because the effect of branching on speed is hard to quantify; it might be faster for all I know) and we did j /= i instead. Second, a mod is about as expensive as a divide, maybe more so since a mod is the remainder *after* divide. If Num is 1000 and Denom 2500 then j is 1000. If you didn&#39;t do this optimization you would perform a total of 2000 mods(2 for every j). If you did perform this optimization you would perform something like 10 mods *total* (mod by 2 three times, mod by 5 two times) for the cost of 5 divides. Again, if a mod is as expensive as a divide that&#39;s 15 &#39;divides&#39; compared to 2000. If the above optimization with the extra / 2 works… you would save more&#33;

Just since no one seems to have mentioned it yet.. this is a Greatest common divisor problem. Google gave me the following code for it, if shorter is better.

unsigned b_gcd(unsigned a, unsigned {
while ( b ^= a ^= b ^= a %= b;
return a;
}


So if you have Width x Height, just divide them both by GCD(Width, Height).

(Guess we found another bug in the source view.. cause those B's were entered as lower case b's

'Erik said:

Just since no one seems to have mentioned it yet.. this is a Greatest common divisor problem. Google gave me the following code for it, if shorter is better.

unsigned b_gcd(unsigned a, unsigned b) {
while (B) b ^= a ^= b ^= a %= b;
return a;
}


So if you have Width x Height, just divide them both by GCD(Width, Height).

(Guess we found another bug in the source view.. cause those B's were entered as lower case b's :)

That code blows my mind. I thought I understand C pretty well, but I don't understand that.

Anyway, nice thread, thanks guys!