Sign in to follow this  

Making ratios whole numbers

This topic is 2546 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello GameDev, how would I go about converting ratios of non-whole numbers to equal ratios of whole-numbers?
Example: "[b]2.5 : 1.5[/b]" should be "[b]5 : 3[/b]"

Basically, I wrote a function to convert monitor resolutions into ratios (like 640 x 480 = 4:3)), and it works, but sometimes it reduces the ratios to fractional components. I want them to always be whole numbers. (For example: 1280 x 768)

Here's my ratio function: (The comments in it, especially the math-terminology comments, are for my own benefit)
[code]std::string RatioAsString(float ratio)
{
float percentage = (100 * ratio); //For example, 100 * 0.75 = 75 percent.
float leftOver = 100 - percentage; //For example, 75% out of 100% = 25%.

//antecedent = mathematical name for left-hand 'term'. (Term 'A' in A:B)
//consequent = mathematical name for the right-hand 'term'. (Term 'B' in A:B)
float antecedent = 100 / leftOver; //For example, 100% / 25% = 4
float consequent = percentage / leftOver; //For example, 75% / 25% = 3

//Result: antecedent : consequent = 4:3
return FloatToString(antecedent) + ":" + FloatToString(consequent);
}[/code][size="1"](I'm aware that this function doesn't do well with ratios greater than 1.0, I just realized that and came up with a fix - but that's not my problem)[/size]

How would I even check in C++ if a float is a whole number or not? A quick google suggests that if "floor(n) == n" then it's a whole number, but surely floating point precision may give false positives (is 3.0 equal to 3.0000000001)?

Once I [i]do[/i] know that is non-whole, then what do I do?

Share this post


Link to post
Share on other sites
[url="http://mathforum.org/library/drmath/view/51886.html"]http://mathforum.org/library/drmath/view/51886.html[/url]

Read Dr. Peterson's algorithm.

<div><br></div><div>edit:</div><div><br></div><div>And in case it's not obvious, what this will do is convert your two rationals into fractions. So you might have 2.5 and 1.5 and now you'll have 5/2 and 3/2. A more difficult example would have you finding fractions with unequal denominators like 7/6 and 1/17. At this point you can apply Euclid's algorithm and multiply out the denominators to get the reduced common factor integers you were looking for.</div>

Share this post


Link to post
Share on other sites
It looks like what you really want to do is reduce a fraction (640 / 480) into its lowest terms (4/3). I stole the following from here: [url="http://www.cplusplus.com/src/"]http://www.cplusplus.com/src/[/url] (first "Fraction" example) and modified it to work with 1 fraction at a time (untested):

[code]std::string Reduce(int Num, int Denom)
{
a = Denom;
b = Num;

for (i = a * b; i > 1; i--)
{
if ((a % i == 0) && (b % i == 0))
{
a /= i;
b /= i;
}
}
return IntToString(a) + ":" + IntToString(B);
}[/code]

Hope this helps/works.

Share this post


Link to post
Share on other sites
That code snippit is actually pretty dumb now that I look at it. i = a * b? The loop will effectively do nothing until i = a or b, whichever is less. So, a simple optimization would be to int i = min(a, B);

Another (possible) optimization would be to start at i = 2 and do something like:

[code]int j = sqrt(min(a,B));
for (int = 2; i < j; i++) {
while((a % i == 0) && (b % i == 0)) {
a /= i;
b /= i;
}
}[/code]

Again, completely untested.

edit: I finally got home to test my code. Final version:

[code]std::string Reduce(int Num, int Denom)
{
int j = std::min(Num,Denom);
for (int i = 2; i <= j; i++) {
while((Num % i == 0) && (Denom % i == 0)) {
Num /= i;
Denom /= i;
}
}
return IntToString(Num) + ":" + IntToString(Denom);
}[/code]

Share this post


Link to post
Share on other sites
Thanks sooner123, read that link and it looks interesting, but as nobodynews pointed out, I can skip that step, and instead of reducing it to a decimal number and then transforming that into a whole number, I can just reduce it to the lowest common denominator. Though you provided the right answer, I was asking the wrong questions.[img]http://public.gamedev.net/public/style_emoticons/default/unsure.gif[/img]

Nobodynews: Thank you, I was completely thinking about it the wrong way. I thought several times about reducing it to the lowest common denominator, but didn't realize my original two numbers (640 by 480, or whatever) was a fraction or ratio all along. I missed that twist of thought that would've saved me a bit of time and googling.
I appreciate the code (and the optimization, which I wouldn't have thought of), and have walked through it a few times in the debugger to see how it works. Grr, my math skills fail. But yea, now that you pointed out that it's already a fraction, reducing it to the lowest fraction isn't a problem.

Thanks guys, I truly appreciate the help! [img]http://public.gamedev.net/public/style_emoticons/default/smile.gif[/img]

Share this post


Link to post
Share on other sites
I think there is another optimization: The outer loop need to run only to the [i]current[/i] minimum of Num and Denom:
[code]std::string Reduce(int Num, int Denom)
{
int j = std::min(Num,Denom);
for (int i = 2; i <= j; i++) {
while((Num % i == 0) && (Denom % i == 0)) {
Num /= i;
Denom /= i;
j /= i; // or j = std::min(Num,Denom);
}
}
return IntToString(Num) + ":" + IntToString(Denom);
}[/code]
And to be precise: It need to run only up to the half current minimum if it is guaranteed that max(Num,Denom) % min(Num,Denom) != 0, e.g.
[code]std::string Reduce(int Num, int Denom)
{
int j = std::min(Num,Denom);
int k = std::max(Num,Denom);
if( k % j == 0)
{
Num /= j;
Denom /= j;
}
else
{
j /= 2;
for (int i = 2; i <= j; i++) {
while((Num % i == 0) && (Denom % i == 0)) {
Num /= i;
Denom /= i;
j = std::min(Num,Denom) / 2;
}
}
}
return IntToString(Num) + ":" + IntToString(Denom);
}[/code]
(but still needs testing)

Share this post


Link to post
Share on other sites
[quote name='sooner123' timestamp='1295991440' post='4764692']
[url="http://mathforum.org/library/drmath/view/51886.html"]http://mathforum.org...view/51886.html[/url]

Read Dr. Peterson's algorithm.
[/quote]My, that was a very pretty algorithm. Thanks, I was unaware of that one.

Share this post


Link to post
Share on other sites
[quote name='haegarr' timestamp='1296031181' post='4764952']
j /= i; // or j = std::min(Num,Denom);
}[/code][/quote]
I did come up with the sd::min in the while loop after posting but I did *not* think of doing j/=i; I think j/=i might be better compared to std::min, but that's actually moot because I just thought "why have j at all?" If you swap Num and Denom before the calculation such that Num is always the minimum you can have this:

[code]bool swapped = false;
if(Num > Denom) {
std::swap(Num, Denom); swapped = true;
}

for (int i = 2; i <= Num; i++) {
while((Num % i == 0) && (Denom % i == 0)) {
Num /= i;
Denom /= i;
}
}

if(swapped) {
std::swap(Num, Denom);
}[/code]

Share this post


Link to post
Share on other sites
@haegarr: Heheh, I only call this function a dozen times or so during when the game starts up - the speed isn't critical. [img]http://public.gamedev.net/public/style_emoticons/default/biggrin.gif[/img]

I'm slightly confused about your optimization though:
[code]std::string Reduce(int Num, int Denom)
{
int j = std::min(Num,Denom); //This part I understand fine - an early out if the input meets a certain requirement (if max is divisible by min).
int k = std::max(Num,Denom);
if( k % j == 0)
{
Num /= j;
Denom /= j;
}
else
{
//The red text I don't get. Doesn't that just reduce the maximum amount of iterations? But if I've hit the maximum, wouldn't it be because I'm needing to, to reduce the fraction?
// I don't see how this speeds it up. Rather, it looks like it'll cost an extra divide and a std::min(), every iteration, while only getting rid of some mods if the number happens
//to be a large one. That is to say, you'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'm misunderstanding what's happening here...
j /= 2;
for (int i = 2; i <= j; i++) {
while((Num % i == 0) && (Denom % i == 0)) {
Num /= i;
Denom /= i;
j = std::min(Num,Denom) / 2;
}
}
}
return IntToString(Num) + ":" + IntToString(Denom);
}
[/code]

Share this post


Link to post
Share on other sites
Final thoughts for the OP: First, most of these 'optimizations' are completely useless for your project. The CPU is fast enough at this kind of thing that you need some large numbers, or a large amount of numbers, to ever notice a delay. Second, some of these optimizations might not be that great or may even harm the algorithm in real-world usage. It may depend on the size of the numbers you are working with before you notice any benfits, with numbers under 10,000 behaving differently from numbers over a billion. The only real way to tell if an optimization works is by profiling your program and seeing precisely how much time the program actually spends in the area you optimized.

Share this post


Link to post
Share on other sites
[quote name='nobodynews' timestamp='1296071301' post='4765216']
[quote name='haegarr' timestamp='1296031181' post='4764952']
j /= i; // or j = std::min(Num,Denom);
}[/code][/quote]
I did come up with the sd::min in the while loop after posting but I did *not* think of doing j/=i; I think j/=i might be better compared to std::min, but that's actually moot because I just thought "why have j at all?" If you swap Num and Denom before the calculation such that Num is always the minimum you can have this:

[i]code snippet removed[/i]
[/quote]
Yes. Nevertheless, when incorporating the other optimization, namely that no Num/2 < i < Num (assuming Num is the minimum, as suggested) need to be investigated, another variable for Num/2 still makes sense.

Share this post


Link to post
Share on other sites
[quote name='nobodynews' timestamp='1296073403' post='4765244']
Final thoughts for the OP: First, most of these 'optimizations' are completely useless for your project....[/quote]
But it makes fun to think about ;) Although it is done already a thousand times before...

Share this post


Link to post
Share on other sites
[quote name='Servant of the Lord' timestamp='1296073234' post='4765242']
[font="Courier New"][color="#ff0000"]//The red text I don't get. Doesn't that just reduce the maximum amount of iterations? But if I've hit the maximum, wouldn't it be because I'm needing to, to reduce the fraction?[/color]
[color="#ff0000"] // I don't see how this speeds it up. Rather, it looks like it'll cost an extra divide and a std::min(), every iteration, while only getting rid of some mods if the number happens[/color]
[color="#ff0000"] //to be a large one. That is to say, you'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)[/color][color="#ff0000"] prime number. Unless I'm misunderstanding what's happening here...[/color]
[color="#ff0000"]j /= 2; [/color]
for (int i = 2; i <= j; i++) {
while((Num % i == 0) && (Denom % i == 0)) {
Num /= i;
Denom /= i;
[color="#ff0000"]j = std::min(Num,Denom) / 2;[/color]
}
}
}
return IntToString(Num) + ":" + IntToString(Denom);
[/font][/quote]I don't entirely understand the extra divide by 2 so I won't explain why that saves time. I will explain why the idea of recalculating j makes sense. Lets add up exactly what'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'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's 15 'divides' compared to 2000. If the above optimization with the extra / 2 works... you would save more!

Share this post


Link to post
Share on other sites
Just since no one seems to have mentioned it yet.. this is a [url="http://en.wikipedia.org/wiki/Greatest_common_divisor"]Greatest common divisor[/url] problem. Google gave me the following code for it, if shorter is better.
[code]
unsigned b_gcd(unsigned a, unsigned B) {
while (B) b ^= a ^= b ^= a %= b;
return a;
}
[/code]

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

Share this post


Link to post
Share on other sites
[quote name='Erik Rufelt' timestamp='1296075959' post='4765270']
Just since no one seems to have mentioned it yet.. this is a [url="http://en.wikipedia.org/wiki/Greatest_common_divisor"]Greatest common divisor[/url] problem. Google gave me the following code for it, if shorter is better.
[code]
unsigned b_gcd(unsigned a, unsigned B) {
while (B) b ^= a ^= b ^= a %= b;
return a;
}
[/code]

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 :)
[/quote]

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

Anyway, nice thread, thanks guys!

Share this post


Link to post
Share on other sites
[font="Courier New"][color="#ff0000"]But if I've hit the maximum, wouldn't it be because I'm needing to, to reduce the fraction?[/color][/font]

You are correct that if you hit the maximum it is because you need to to reduce the fraction. However, what you are missing is that when you reach the inside of that while loop you are reducing the fraction (just not completely) causing the maximum to be lower than it was originally! 1000:2500 becomes 500:1250 becomes 250:625, etc. If you kept 'j' the same you would get to the point where i = 5, j=1000, Num=2 and Denom=5. If you kept going until i == j you would be waiting a looong time to finish even though the fraction was already reduced as far as it could go.

Share this post


Link to post
Share on other sites
[quote name='nobodynews' timestamp='1296076922' post='4765281'][font="Courier New"] [/font]You are correct that if you hit the maximum it is because you need to to reduce the fraction. However, what you are missing is that when you reach the inside of that while loop you are reducing the fraction (just not completely) causing the maximum to be lower than it was originally![/quote]
Yeah, I understood that the fraction was getting reduced inside the loop. My own mind was exitting the loop as soon as the correct fraction was found, because I knew the correct fraction. I forgot that the loop will need to keep iterating until it exhausts it's possibilities, to be certain that it's the most reduced form. Oops.

@Erik: [img]http://public.gamedev.net/public/style_emoticons/default/blink.gif[/img] I think I'll go with the slower but understandable code than the lightning fast alien gibberish. [img]http://public.gamedev.net/public/style_emoticons/default/wink.gif[/img] But thanks anyway!

Share this post


Link to post
Share on other sites
[quote name='szecs' timestamp='1296076457' post='4765279']
[quote name='Erik Rufelt' timestamp='1296075959' post='4765270']
Just since no one seems to have mentioned it yet.. this is a [url="http://en.wikipedia.org/wiki/Greatest_common_divisor"]Greatest common divisor[/url] problem. Google gave me the following code for it, if shorter is better.
[code]
unsigned b_gcd(unsigned a, unsigned b) {
while (B) b ^= a ^= b ^= a %= b;
return a;
}
[/code]

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 :)
[/quote]

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

Anyway, nice thread, thanks guys!
[/quote]

I guess that every body understands a %= b, so the critical part is the b^=a^=b^=a.

So let's rewrite this as the compiler will rewrite it
[code]
while (b)
{
a %= b;
b ^= a; // XOR
a ^= b; // XOR
b ^= a; // XOR
}
[/code]

Those who know the shortcut might understand that the 3 last lines is a swap(a,B). For those who don't, remember that XOR is

* associative : a XOR b XOR c = (a XOR b) XOR c = a XOR (b XOR c)
* commutative : a XOR b = b XOR a

Let's restart from the begining:
[code]
b1 = b0 XOR a0
a1 = a0 XOR b1 => a1 = a0 XOR (b0 XOR a0) => a1 = (a0 XOR a0) XOR b0 ==> a1 = b0
b2 = b1 XOR a1 => b2 = b1 XOR (a0 XOR b1) => b2 = (b1 XOR b1) XOR a0 ==> b2 = a0
[/code]

So what we effectively do is:

[code]
while (b)
{
a %= b;
std::swap(a,b)
}
[/code]

Which is, in essence, [url="http://en.wikipedia.org/wiki/Greatest_common_divisor#Using_Euclid.27s_algorithm"]Euclid's recursive algorithm[/url] written as an iterative loop. In a single, cryptic line of code :)

PS: the b which becomes B is not a bug in the source view ; it's a feature (emoticon's replacement). Which is even more annoying.

Can't this be removed? Emoticons are better when they are used on purpose.

Share this post


Link to post
Share on other sites
[quote name='Emmanuel Deloget' timestamp='1296084567' post='4765327']
PS: the b which becomes B is not a bug in the source view ; it's a feature (emoticon's replacement). Which is even more annoying.

Can't this be removed? Emoticons are better when they are used on purpose.
[/quote]
This one's [url=http://www.gamedev.net/tracker/issue-846-code-snippet-bug-in-forums/]been sitting in the tracker[/url] for more than a week already. Who knows when or if it'll be fixed.

Share this post


Link to post
Share on other sites

This topic is 2546 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this