Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


Making ratios whole numbers


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
18 replies to this topic

#1 Servant of the Lord   Crossbones+   -  Reputation: 21166

Like
0Likes
Like

Posted 25 January 2011 - 03:22 PM

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

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)
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:<img src='http://public.gamedev.net/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='B)' />
    //consequent = mathematical name for the right-hand 'term'. (Term 'B' in A:<img src='http://public.gamedev.net/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='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);
}
(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)

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 do know that is non-whole, then what do I do?
It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal

[Fly with me on Twitter] [Google+] [My broken website]

[Need web hosting? I personally like A Small Orange]


Sponsor:

#2 sooner123   Members   -  Reputation: 241

Like
1Likes
Like

Posted 25 January 2011 - 03:37 PM

http://mathforum.org/library/drmath/view/51886.html

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>

#3 nobodynews   Crossbones+   -  Reputation: 2116

Like
0Likes
Like

Posted 25 January 2011 - 04:19 PM

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: http://www.cplusplus.com/src/ (first "Fraction" example) and modified it to work with 1 fraction at a time (untested):

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(<img src='http://public.gamedev.net/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='B)' />;
}

Hope this helps/works.


C++: A Dialog | C++0x Features: Part1 (lambdas, auto, static_assert) , Part 2 (rvalue references) , Part 3 (decltype) | Write Games | Fix Your Timestep!


#4 nobodynews   Crossbones+   -  Reputation: 2116

Like
1Likes
Like

Posted 25 January 2011 - 04:33 PM

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:

int j = sqrt(min(a,<img src='http://public.gamedev.net/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='B)' />);
for (int = 2; i < j; i++) {
  while((a % i == 0) && (b % i == 0)) {
    a /= i;
    b /= i;
  }
}

Again, completely untested.

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

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);
}

C++: A Dialog | C++0x Features: Part1 (lambdas, auto, static_assert) , Part 2 (rvalue references) , Part 3 (decltype) | Write Games | Fix Your Timestep!


#5 Servant of the Lord   Crossbones+   -  Reputation: 21166

Like
0Likes
Like

Posted 26 January 2011 - 12:23 AM

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.Posted Image

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! Posted Image
It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal

[Fly with me on Twitter] [Google+] [My broken website]

[Need web hosting? I personally like A Small Orange]


#6 haegarr   Crossbones+   -  Reputation: 4602

Like
0Likes
Like

Posted 26 January 2011 - 02:39 AM

I think there is another optimization: The outer loop need to run only to the current minimum of Num and Denom:
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);
}
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.
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);
}
(but still needs testing)

#7 Sneftel   Senior Moderators   -  Reputation: 1781

Like
0Likes
Like

Posted 26 January 2011 - 09:37 AM

http://mathforum.org...view/51886.html

Read Dr. Peterson's algorithm.

My, that was a very pretty algorithm. Thanks, I was unaware of that one.

#8 nobodynews   Crossbones+   -  Reputation: 2116

Like
0Likes
Like

Posted 26 January 2011 - 01:48 PM

j /= i; // or j = std::min(Num,Denom);
}[/code]

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:

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);
}

C++: A Dialog | C++0x Features: Part1 (lambdas, auto, static_assert) , Part 2 (rvalue references) , Part 3 (decltype) | Write Games | Fix Your Timestep!


#9 Servant of the Lord   Crossbones+   -  Reputation: 21166

Like
0Likes
Like

Posted 26 January 2011 - 02:20 PM

@haegarr: Heheh, I only call this function a dozen times or so during when the game starts up - the speed isn't critical. Posted Image

I'm slightly confused about your optimization though:
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);
}

It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal

[Fly with me on Twitter] [Google+] [My broken website]

[Need web hosting? I personally like A Small Orange]


#10 nobodynews   Crossbones+   -  Reputation: 2116

Like
0Likes
Like

Posted 26 January 2011 - 02:23 PM

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.

C++: A Dialog | C++0x Features: Part1 (lambdas, auto, static_assert) , Part 2 (rvalue references) , Part 3 (decltype) | Write Games | Fix Your Timestep!


#11 haegarr   Crossbones+   -  Reputation: 4602

Like
0Likes
Like

Posted 26 January 2011 - 02:27 PM


j /= i; // or j = std::min(Num,Denom);
}[/code]

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 snippet removed

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.

#12 haegarr   Crossbones+   -  Reputation: 4602

Like
0Likes
Like

Posted 26 January 2011 - 02:30 PM

Final thoughts for the OP: First, most of these 'optimizations' are completely useless for your project....

But it makes fun to think about ;) Although it is done already a thousand times before...

#13 nobodynews   Crossbones+   -  Reputation: 2116

Like
0Likes
Like

Posted 26 January 2011 - 03:00 PM

//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);

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!

C++: A Dialog | C++0x Features: Part1 (lambdas, auto, static_assert) , Part 2 (rvalue references) , Part 3 (decltype) | Write Games | Fix Your Timestep!


#14 Erik Rufelt   Crossbones+   -  Reputation: 3642

Like
0Likes
Like

Posted 26 January 2011 - 03:05 PM

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 <img src='http://public.gamedev.net/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='B)' /> {
	while (<img src='http://public.gamedev.net/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='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 :)

#15 szecs   Members   -  Reputation: 2185

Like
0Likes
Like

Posted 26 January 2011 - 03:14 PM

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 <img src='http://public.gamedev.net/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='B)' /> {
	while (<img src='http://public.gamedev.net/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='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!

#16 nobodynews   Crossbones+   -  Reputation: 2116

Like
0Likes
Like

Posted 26 January 2011 - 03:22 PM

But if I've hit the maximum, wouldn't it be because I'm needing to, to reduce the fraction?

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.

C++: A Dialog | C++0x Features: Part1 (lambdas, auto, static_assert) , Part 2 (rvalue references) , Part 3 (decltype) | Write Games | Fix Your Timestep!


#17 Servant of the Lord   Crossbones+   -  Reputation: 21166

Like
0Likes
Like

Posted 26 January 2011 - 03:50 PM

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!

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: Posted Image I think I'll go with the slower but understandable code than the lightning fast alien gibberish. Posted Image But thanks anyway!
It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal

[Fly with me on Twitter] [Google+] [My broken website]

[Need web hosting? I personally like A Small Orange]


#18 Emmanuel Deloget   Members   -  Reputation: 1381

Like
1Likes
Like

Posted 26 January 2011 - 05:29 PM


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!


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
  while (b)
  {
    a %= b;
    b ^= a; // XOR
    a ^= b; // XOR
    b ^= a; // XOR
  }

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

So what we effectively do is:

  while (b)
  {
    a %= b;
    std::swap(a,b)
  }

Which is, in essence, Euclid's recursive algorithm 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.

#19 SiCrane   Moderators   -  Reputation: 9674

Like
0Likes
Like

Posted 26 January 2011 - 05:52 PM

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.

This one's been sitting in the tracker for more than a week already. Who knows when or if it'll be fixed.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS