-
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 :)
-
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?
-
You're right :D 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?
-
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? :)
-
It just so happens that I wrote a library to deal with fractions. I took the struct approach, using longs to represent a whole number, a numerator and a denominator. I added the whole number in there so I could represent mixed fractions easily.
I also wrote some basic functions (frac_add, frac_sub, frac_mult, frac_div, frac_power) to manipulate them. I just got into programming about a month ago, so I'm sure there are things that could be improved - but the library works well with positive and negative numbers, and has error checking for a zero denominator.
Anyway, I know the code is longer that what I should probably post in a thread, so here's the link. All the goodies are in the fraction.h file, the fraction.cpp file just shows how to use it.
Index of /prog/c/fraction