C Board  

Go Back   C Board > General Programming Boards > C Programming

Reply
 
LinkBack Thread Tools Display Modes
Old 02-10-2010, 02:24 AM   #1
Registered User
 
Join Date: Feb 2009
Posts: 58
Fractions

I'm in Data Structures & Algorithms II. I just started thinking about how one would store a fraction. I'm going out on a limb here and saying that the only possibility would be to store it in a string, unless 2 variables are used - 1 for the numerator & 1 for the denominator. I tried "googling" it and there was no talk of this. I suppose you could also store a fraction in a struct, but that would also take 2 variables.

Any other input on this would be appreciated (fyi, this is my 3rd semester of programming in C, the only other programming class I had was Java..) It's sort of a pretty broad topic, so go wherever you would like with this
madmax2006 is offline   Reply With Quote
Old 02-10-2010, 03:01 AM   #2
Registered User
 
Join Date: Jan 2010
Posts: 231
Depends on how much precision you need. You could use the upper and lower half of an int or a long long for each part of the fraction for example, and use a bit shifting/masking to store/retrieve the parts.

I also find your reasoning a bit strange..
You say that a struct with 2 members is more than 1 variable, but a string (which is an array of multiple characters) is only 1 variable?

Last edited by _Mike; 02-10-2010 at 03:05 AM.
_Mike is offline   Reply With Quote
Old 02-10-2010, 03:34 AM   #3
Registered User
 
Join Date: Feb 2009
Posts: 58
You're right I do have strange reasoning. I never really gave much thought to it. When you say "upper and lower half of an int", what exactly do you mean? I haven't gotten very deep into a particular subject of C, only Algorithms & "Big-O"/"Big-Oh" whatever you call it. I'm really interested in other parts of C like you're talking about. We glanced at shifting/masking when we were using MARS(MIPS), but that was it. Do you know of any tutorials that go deeper into shifting/masking?
madmax2006 is offline   Reply With Quote
Old 02-10-2010, 04:47 AM   #4
Registered User
 
Join Date: Jan 2010
Posts: 231
Don't really know of any specific tutorials but wikipedia has a pretty good explanation on how it works.
Bitwise operation - Wikipedia, the free encyclopedia

And here's a short example
Code:
// This code assumes an int is 32 bits for simplicity.
// In real code you might want to check sizeof(int)
// and adjust the mask and shift values unless you know
// it will only be run on machines with 32 bit ints.
int main()
{
	// Initial values
	// These can be read from a file or the command line or whatever :)
	int numerator = 13;
	int denominator = 45;

	// Store the fraction
	// First we mask (bitwise AND) with 0xFFFF (16 bits of all 1's, half of a 32-bit int)
	// to make sure the inputted numbers aren't bigger than 16 bits.
	// Then we shift the numerator 16 bits to the left
	// and bitwise OR it with the denominator.
	// numerator is now in the upper half of fraction,
	// and denominator is in the lower half.
	int fraction = ((numerator & 0xFFFF) << 16) | (denominator & 0xFFFF);


	// Retrieve the fraction parts
	// For n we use a bitmask to get only the upper half,
	// and then shift it back 16 bits to the right.
	// For d we just grab the lower half directly.
	int n = (fraction & 0xFFFF0000) >> 16;
	int d = fraction & 0x0000FFFF;

	printf("numerator = %d\n", n);
	printf("denominator = %d\n", d);
}
Or you can use preprocessor macros like
Code:
#define MAKEFRACTION(num,den)  (((num & 0xFFFF)<<16) | (den & 0xFFFF))
#define LOWPART(f)  (f & 0xFFFF)
#define HIGHPART(f) ((f>>16)&0xFFFF)

fraction = MAKEFRACTION(numerator,denominator);
numerator = HIGHPART(fraction);
denominator = LOWPART(fraction);
Since we are using 16 bit numbers the maximum range for the numerator and denominator is 0 to 65535. If you want to be able to handle negative numbers you would have to use 1 bit as a sign bit and the range would be -32768 to 32767
Of course if you used a 64bit data type for the fraction, for example long long, you would get a much bigger range. (0 to 2^32 for unsigned)

Edit:
Although is it worth all the extra trouble just to avoid using a struct or an array of 2 ints?

Last edited by _Mike; 02-10-2010 at 04:49 AM.
_Mike is offline   Reply With Quote
Reply

Thread Tools
Display Modes

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
fractions zdream8 C Programming 2 05-21-2008 09:54 PM
Algebraic Fractions treenef C++ Programming 8 12-20-2005 05:10 AM
Greatest Common Factors of Fractions sonict C++ Programming 1 01-15-2003 04:33 AM
Fractions Unregistered C++ Programming 2 04-01-2002 07:51 AM
Decimals to Fractions ToasterPas C++ Programming 4 12-28-2001 12:58 PM


All times are GMT -6. The time now is 02:13 PM.


Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2010, Jelsoft Enterprises Ltd.
Search Engine Optimization by vBSEO 3.3.2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22