• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Servant of the Lord

Making ratios whole numbers

18 posts in this topic

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?
0

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

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.

0

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]
1

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]
0

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

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

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]
0

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]
0

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

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

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

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!
0

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

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!
0

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

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!
0

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

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

Share this post


Link to post
Share on other sites

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  
Followers 0