Thread: Fractions

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    68

    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. #2
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    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.

  3. #3
    Registered User
    Join Date
    Feb 2009
    Posts
    68
    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. #4
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    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.

  5. #5
    Registered User
    Join Date
    Jun 2010
    Location
    Bakersfield, California
    Posts
    22
    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 subscribe to a feed

Similar Threads

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