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

2. 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?

3. 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?

4. 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?

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

Popular pages Recent additions