Best Way to Represent a Fraction in Java

Best way to represent a fraction in Java?

It just so happens that I wrote a BigFraction class not too long ago, for Project Euler problems. It keeps a BigInteger numerator and denominator, so it'll never overflow. But it'll be a tad slow for a lot of operations that you know will never overflow.. anyway, use it if you want it. I've been dying to show this off somehow. :)

Edit: Latest and greatest version of this code, including unit tests is now hosted on GitHub and also available via Maven Central. I'm leaving my original code here so that this answer isn't just a link...


import java.math.*;

/**
* Arbitrary-precision fractions, utilizing BigIntegers for numerator and
* denominator. Fraction is always kept in lowest terms. Fraction is
* immutable, and guaranteed not to have a null numerator or denominator.
* Denominator will always be positive (so sign is carried by numerator,
* and a zero-denominator is impossible).
*/
public final class BigFraction extends Number implements Comparable<BigFraction>
{
private static final long serialVersionUID = 1L; //because Number is Serializable
private final BigInteger numerator;
private final BigInteger denominator;

public final static BigFraction ZERO = new BigFraction(BigInteger.ZERO, BigInteger.ONE, true);
public final static BigFraction ONE = new BigFraction(BigInteger.ONE, BigInteger.ONE, true);

/**
* Constructs a BigFraction with given numerator and denominator. Fraction
* will be reduced to lowest terms. If fraction is negative, negative sign will
* be carried on numerator, regardless of how the values were passed in.
*/
public BigFraction(BigInteger numerator, BigInteger denominator)
{
if(numerator == null)
throw new IllegalArgumentException("Numerator is null");
if(denominator == null)
throw new IllegalArgumentException("Denominator is null");
if(denominator.equals(BigInteger.ZERO))
throw new ArithmeticException("Divide by zero.");

//only numerator should be negative.
if(denominator.signum() < 0)
{
numerator = numerator.negate();
denominator = denominator.negate();
}

//create a reduced fraction
BigInteger gcd = numerator.gcd(denominator);
this.numerator = numerator.divide(gcd);
this.denominator = denominator.divide(gcd);
}

/**
* Constructs a BigFraction from a whole number.
*/
public BigFraction(BigInteger numerator)
{
this(numerator, BigInteger.ONE, true);
}

public BigFraction(long numerator, long denominator)
{
this(BigInteger.valueOf(numerator), BigInteger.valueOf(denominator));
}

public BigFraction(long numerator)
{
this(BigInteger.valueOf(numerator), BigInteger.ONE, true);
}

/**
* Constructs a BigFraction from a floating-point number.
*
* Warning: round-off error in IEEE floating point numbers can result
* in answers that are unexpected. For example,
* System.out.println(new BigFraction(1.1))
* will print:
* 2476979795053773/2251799813685248
*
* This is because 1.1 cannot be expressed exactly in binary form. The
* given fraction is exactly equal to the internal representation of
* the double-precision floating-point number. (Which, for 1.1, is:
* (-1)^0 * 2^0 * (1 + 0x199999999999aL / 0x10000000000000L).)
*
* NOTE: In many cases, BigFraction(Double.toString(d)) may give a result
* closer to what the user expects.
*/
public BigFraction(double d)
{
if(Double.isInfinite(d))
throw new IllegalArgumentException("double val is infinite");
if(Double.isNaN(d))
throw new IllegalArgumentException("double val is NaN");

//special case - math below won't work right for 0.0 or -0.0
if(d == 0)
{
numerator = BigInteger.ZERO;
denominator = BigInteger.ONE;
return;
}

final long bits = Double.doubleToLongBits(d);
final int sign = (int)(bits >> 63) & 0x1;
final int exponent = ((int)(bits >> 52) & 0x7ff) - 0x3ff;
final long mantissa = bits & 0xfffffffffffffL;

//number is (-1)^sign * 2^(exponent) * 1.mantissa
BigInteger tmpNumerator = BigInteger.valueOf(sign==0 ? 1 : -1);
BigInteger tmpDenominator = BigInteger.ONE;

//use shortcut: 2^x == 1 << x. if x is negative, shift the denominator
if(exponent >= 0)
tmpNumerator = tmpNumerator.multiply(BigInteger.ONE.shiftLeft(exponent));
else
tmpDenominator = tmpDenominator.multiply(BigInteger.ONE.shiftLeft(-exponent));

//1.mantissa == 1 + mantissa/2^52 == (2^52 + mantissa)/2^52
tmpDenominator = tmpDenominator.multiply(BigInteger.valueOf(0x10000000000000L));
tmpNumerator = tmpNumerator.multiply(BigInteger.valueOf(0x10000000000000L + mantissa));

BigInteger gcd = tmpNumerator.gcd(tmpDenominator);
numerator = tmpNumerator.divide(gcd);
denominator = tmpDenominator.divide(gcd);
}

/**
* Constructs a BigFraction from two floating-point numbers.
*
* Warning: round-off error in IEEE floating point numbers can result
* in answers that are unexpected. See BigFraction(double) for more
* information.
*
* NOTE: In many cases, BigFraction(Double.toString(numerator) + "/" + Double.toString(denominator))
* may give a result closer to what the user expects.
*/
public BigFraction(double numerator, double denominator)
{
if(denominator == 0)
throw new ArithmeticException("Divide by zero.");

BigFraction tmp = new BigFraction(numerator).divide(new BigFraction(denominator));
this.numerator = tmp.numerator;
this.denominator = tmp.denominator;
}

/**
* Constructs a new BigFraction from the given BigDecimal object.
*/
public BigFraction(BigDecimal d)
{
this(d.scale() < 0 ? d.unscaledValue().multiply(BigInteger.TEN.pow(-d.scale())) : d.unscaledValue(),
d.scale() < 0 ? BigInteger.ONE : BigInteger.TEN.pow(d.scale()));
}

public BigFraction(BigDecimal numerator, BigDecimal denominator)
{
if(denominator.equals(BigDecimal.ZERO))
throw new ArithmeticException("Divide by zero.");

BigFraction tmp = new BigFraction(numerator).divide(new BigFraction(denominator));
this.numerator = tmp.numerator;
this.denominator = tmp.denominator;
}

/**
* Constructs a BigFraction from a String. Expected format is numerator/denominator,
* but /denominator part is optional. Either numerator or denominator may be a floating-
* point decimal number, which in the same format as a parameter to the
* <code>BigDecimal(String)</code> constructor.
*
* @throws NumberFormatException if the string cannot be properly parsed.
*/
public BigFraction(String s)
{
int slashPos = s.indexOf('/');
if(slashPos < 0)
{
BigFraction res = new BigFraction(new BigDecimal(s));
this.numerator = res.numerator;
this.denominator = res.denominator;
}
else
{
BigDecimal num = new BigDecimal(s.substring(0, slashPos));
BigDecimal den = new BigDecimal(s.substring(slashPos+1, s.length()));
BigFraction res = new BigFraction(num, den);
this.numerator = res.numerator;
this.denominator = res.denominator;
}
}

/**
* Returns this + f.
*/
public BigFraction add(BigFraction f)
{
if(f == null)
throw new IllegalArgumentException("Null argument");

//n1/d1 + n2/d2 = (n1*d2 + d1*n2)/(d1*d2)
return new BigFraction(numerator.multiply(f.denominator).add(denominator.multiply(f.numerator)),
denominator.multiply(f.denominator));
}

/**
* Returns this + b.
*/
public BigFraction add(BigInteger b)
{
if(b == null)
throw new IllegalArgumentException("Null argument");

//n1/d1 + n2 = (n1 + d1*n2)/d1
return new BigFraction(numerator.add(denominator.multiply(b)),
denominator, true);
}

/**
* Returns this + n.
*/
public BigFraction add(long n)
{
return add(BigInteger.valueOf(n));
}

/**
* Returns this - f.
*/
public BigFraction subtract(BigFraction f)
{
if(f == null)
throw new IllegalArgumentException("Null argument");

return new BigFraction(numerator.multiply(f.denominator).subtract(denominator.multiply(f.numerator)),
denominator.multiply(f.denominator));
}

/**
* Returns this - b.
*/
public BigFraction subtract(BigInteger b)
{
if(b == null)
throw new IllegalArgumentException("Null argument");

return new BigFraction(numerator.subtract(denominator.multiply(b)),
denominator, true);
}

/**
* Returns this - n.
*/
public BigFraction subtract(long n)
{
return subtract(BigInteger.valueOf(n));
}

/**
* Returns this * f.
*/
public BigFraction multiply(BigFraction f)
{
if(f == null)
throw new IllegalArgumentException("Null argument");

return new BigFraction(numerator.multiply(f.numerator), denominator.multiply(f.denominator));
}

/**
* Returns this * b.
*/
public BigFraction multiply(BigInteger b)
{
if(b == null)
throw new IllegalArgumentException("Null argument");

return new BigFraction(numerator.multiply(b), denominator);
}

/**
* Returns this * n.
*/
public BigFraction multiply(long n)
{
return multiply(BigInteger.valueOf(n));
}

/**
* Returns this / f.
*/
public BigFraction divide(BigFraction f)
{
if(f == null)
throw new IllegalArgumentException("Null argument");

if(f.numerator.equals(BigInteger.ZERO))
throw new ArithmeticException("Divide by zero");

return new BigFraction(numerator.multiply(f.denominator), denominator.multiply(f.numerator));
}

/**
* Returns this / b.
*/
public BigFraction divide(BigInteger b)
{
if(b == null)
throw new IllegalArgumentException("Null argument");

if(b.equals(BigInteger.ZERO))
throw new ArithmeticException("Divide by zero");

return new BigFraction(numerator, denominator.multiply(b));
}

/**
* Returns this / n.
*/
public BigFraction divide(long n)
{
return divide(BigInteger.valueOf(n));
}

/**
* Returns this^exponent.
*/
public BigFraction pow(int exponent)
{
if(exponent == 0)
return BigFraction.ONE;
else if (exponent == 1)
return this;
else if (exponent < 0)
return new BigFraction(denominator.pow(-exponent), numerator.pow(-exponent), true);
else
return new BigFraction(numerator.pow(exponent), denominator.pow(exponent), true);
}

/**
* Returns 1/this.
*/
public BigFraction reciprocal()
{
if(this.numerator.equals(BigInteger.ZERO))
throw new ArithmeticException("Divide by zero");

return new BigFraction(denominator, numerator, true);
}

/**
* Returns the complement of this fraction, which is equal to 1 - this.
* Useful for probabilities/statistics.

*/
public BigFraction complement()
{
return new BigFraction(denominator.subtract(numerator), denominator, true);
}

/**
* Returns -this.
*/
public BigFraction negate()
{
return new BigFraction(numerator.negate(), denominator, true);
}

/**
* Returns -1, 0, or 1, representing the sign of this fraction.
*/
public int signum()
{
return numerator.signum();
}

/**
* Returns the absolute value of this.
*/
public BigFraction abs()
{
return (signum() < 0 ? negate() : this);
}

/**
* Returns a string representation of this, in the form
* numerator/denominator.
*/
public String toString()
{
return numerator.toString() + "/" + denominator.toString();
}

/**
* Returns if this object is equal to another object.
*/
public boolean equals(Object o)
{
if(!(o instanceof BigFraction))
return false;

BigFraction f = (BigFraction)o;
return numerator.equals(f.numerator) && denominator.equals(f.denominator);
}

/**
* Returns a hash code for this object.
*/
public int hashCode()
{
//using the method generated by Eclipse, but streamlined a bit..
return (31 + numerator.hashCode())*31 + denominator.hashCode();
}

/**
* Returns a negative, zero, or positive number, indicating if this object
* is less than, equal to, or greater than f, respectively.
*/
public int compareTo(BigFraction f)
{
if(f == null)
throw new IllegalArgumentException("Null argument");

//easy case: this and f have different signs
if(signum() != f.signum())
return signum() - f.signum();

//next easy case: this and f have the same denominator
if(denominator.equals(f.denominator))
return numerator.compareTo(f.numerator);

//not an easy case, so first make the denominators equal then compare the numerators
return numerator.multiply(f.denominator).compareTo(denominator.multiply(f.numerator));
}

/**
* Returns the smaller of this and f.
*/
public BigFraction min(BigFraction f)
{
if(f == null)
throw new IllegalArgumentException("Null argument");

return (this.compareTo(f) <= 0 ? this : f);
}

/**
* Returns the maximum of this and f.
*/
public BigFraction max(BigFraction f)
{
if(f == null)
throw new IllegalArgumentException("Null argument");

return (this.compareTo(f) >= 0 ? this : f);
}

/**
* Returns a positive BigFraction, greater than or equal to zero, and less than one.
*/
public static BigFraction random()
{
return new BigFraction(Math.random());
}

public final BigInteger getNumerator() { return numerator; }
public final BigInteger getDenominator() { return denominator; }

//implementation of Number class. may cause overflow.
public byte byteValue() { return (byte) Math.max(Byte.MIN_VALUE, Math.min(Byte.MAX_VALUE, longValue())); }
public short shortValue() { return (short)Math.max(Short.MIN_VALUE, Math.min(Short.MAX_VALUE, longValue())); }
public int intValue() { return (int) Math.max(Integer.MIN_VALUE, Math.min(Integer.MAX_VALUE, longValue())); }
public long longValue() { return Math.round(doubleValue()); }
public float floatValue() { return (float)doubleValue(); }
public double doubleValue() { return toBigDecimal(18).doubleValue(); }

/**
* Returns a BigDecimal representation of this fraction. If possible, the
* returned value will be exactly equal to the fraction. If not, the BigDecimal
* will have a scale large enough to hold the same number of significant figures
* as both numerator and denominator, or the equivalent of a double-precision
* number, whichever is more.
*/
public BigDecimal toBigDecimal()
{
//Implementation note: A fraction can be represented exactly in base-10 iff its
//denominator is of the form 2^a * 5^b, where a and b are nonnegative integers.
//(In other words, if there are no prime factors of the denominator except for
//2 and 5, or if the denominator is 1). So to determine if this denominator is
//of this form, continually divide by 2 to get the number of 2's, and then
//continually divide by 5 to get the number of 5's. Afterward, if the denominator
//is 1 then there are no other prime factors.

//Note: number of 2's is given by the number of trailing 0 bits in the number
int twos = denominator.getLowestSetBit();
BigInteger tmpDen = denominator.shiftRight(twos); // x / 2^n === x >> n

final BigInteger FIVE = BigInteger.valueOf(5);
int fives = 0;
BigInteger[] divMod = null;

//while(tmpDen % 5 == 0) { fives++; tmpDen /= 5; }
while(BigInteger.ZERO.equals((divMod = tmpDen.divideAndRemainder(FIVE))[1]))
{
fives++;
tmpDen = divMod[0];
}

if(BigInteger.ONE.equals(tmpDen))
{
//This fraction will terminate in base 10, so it can be represented exactly as
//a BigDecimal. We would now like to make the fraction of the form
//unscaled / 10^scale. We know that 2^x * 5^x = 10^x, and our denominator is
//in the form 2^twos * 5^fives. So use max(twos, fives) as the scale, and
//multiply the numerator and deminator by the appropriate number of 2's or 5's
//such that the denominator is of the form 2^scale * 5^scale. (Of course, we
//only have to actually multiply the numerator, since all we need for the
//BigDecimal constructor is the scale.
BigInteger unscaled = numerator;
int scale = Math.max(twos, fives);

if(twos < fives)
unscaled = unscaled.shiftLeft(fives - twos); //x * 2^n === x << n
else if (fives < twos)
unscaled = unscaled.multiply(FIVE.pow(twos - fives));

return new BigDecimal(unscaled, scale);
}

//else: this number will repeat infinitely in base-10. So try to figure out
//a good number of significant digits. Start with the number of digits required
//to represent the numerator and denominator in base-10, which is given by
//bitLength / log[2](10). (bitLenth is the number of digits in base-2).
final double LG10 = 3.321928094887362; //Precomputed ln(10)/ln(2), a.k.a. log[2](10)
int precision = Math.max(numerator.bitLength(), denominator.bitLength());
precision = (int)Math.ceil(precision / LG10);

//If the precision is less than 18 digits, use 18 digits so that the number
//will be at least as accurate as a cast to a double. For example, with
//the fraction 1/3, precision will be 1, giving a result of 0.3. This is
//quite a bit different from what a user would expect.
if(precision < 18)
precision = 18;

return toBigDecimal(precision);
}

/**
* Returns a BigDecimal representation of this fraction, with a given precision.
* @param precision the number of significant figures to be used in the result.
*/
public BigDecimal toBigDecimal(int precision)
{
return new BigDecimal(numerator).divide(new BigDecimal(denominator), new MathContext(precision, RoundingMode.HALF_EVEN));
}

//--------------------------------------------------------------------------
// PRIVATE FUNCTIONS
//--------------------------------------------------------------------------

/**
* Private constructor, used when you can be certain that the fraction is already in
* lowest terms. No check is done to reduce numerator/denominator. A check is still
* done to maintain a positive denominator.
*
* @param throwaway unused variable, only here to signal to the compiler that this
* constructor should be used.
*/
private BigFraction(BigInteger numerator, BigInteger denominator, boolean throwaway)
{
if(denominator.signum() < 0)
{
this.numerator = numerator.negate();
this.denominator = denominator.negate();
}
else
{
this.numerator = numerator;
this.denominator = denominator;
}
}

}

How do you create a fraction in java

You need to create a class that is a wrapper for fractions. For member variables you would want integers Numerator and Denominator. You would need methods for adding, subtracting, multiplying, and dividing the fractions with each other.

Using Java doubles (or anything else) to store simple fractions

Try:

double quarter = 1d/4d;

The division of two integers gives a truncated integer. By putting the d behind the numbers you are casting them to doubles.

Passing the values to the fraction class in java

Your Fraction method is a method which is defined to return an int, but you're calling it as though it were a constructor.

Constructors don't return anything, so don't declare any return type. ( they don't even have a void type so the compiler knows they are constructors rather than methods, and need to be called with new. It's a minor bug that Java lets you declare methods with the same name as the class, IIRC one of the puzzles in Java Puzzlers does that ).

Remove the "int" return type from the definition:

public class Fraction{

private int numerator;
private int denominator;

public Fraction(int num, int denom) {
//...

How will that set both numbers from fraction c in the driver class wich is coming in from the scanner util and also would this, would the c values be replaced by the values that are coming in from fraction d?

You're making two calls to new Fraction(..,..). Each time you use new, it creates a new object of the requested class and then calls the constructor on that object with the values you give it. So c and d will hold references to difference instances of Fraction. As the numerator and denominator fields of Fraction are not marked as static, then each instance of Fraction will have its own copy of those fields, so the values passed to the constructor of the object whose reference will stored in the variable c are stored in the first new object, and those of d in the second new object. As they are different objects, the values won't replace each other.

How to represent mixed fractions in java

You could perhaps do this by extending Fraction: you might want to add a new constructor that takes a whole number in addition to the numerator/denominator new MixedFraction(2,3,4) for 2 3/4, and override toString to display in the desired format.

How are fractions represented in computers?

The most common way to represent numbers other than integers on computers is by using floating point, particularly IEEE 754 floating point. As you may be familiar with, integers are commonly represented by using hardware bits to represent binary numerals, so physical properties (such as charge or lack of charge, high voltage or low voltage, a magnetic field in one direction or another) are used to represent bits (0 and 1), and a sequence of those bits makes a numeral (such as 11010), which we interpret in binary to represent a number (110102 is 16+8+2 = 26). We do not usually think of it, but there is a “radix point” to the right of this numeral: “11010.” We only need the radix point when we have more bits to the right of it, which represent fractions. For example, 11010.112 is 16 + 8 + 2 + 1/2 + 1/4 = 26.75. To change from integers to floating point, we make the radix point float. In addition to the bits representing the numeral, we have some additional bits that tell us where to put the radix point.

So, we might have three bits, say 010, to say where the radix point goes and other bits, say 1101011, to represent the value. The radix-point bits, 010, might say to move the radix point two positions left, changing “1101011.” to “11010.11”.

In single-precision IEEE 754, there is one sign bit (that tells us + or -), eight exponent bits, and 23 value bits (for the “significand” or “fraction”). The values 0 and 255 of the exponent bits are special. For other values of the exponent bits, we subtract 127 to get exponents ranging from -126 (shift the radix point 126 bits left) to 127 (shift the radix point 127 bits right). The significand bits are interpreted as a binary numeral, except that we modify them a little: We write “1”, then a radix point, then the 23 bits of the significand, so we have something like “1.1101011000…”. As an alternative, you can think of this as an integer: “1” then 23 bits with no inserted radix point, making a 24-bit binary numeral, but the exponent is adjusted by an extra 23 (so subtract 150 instead of 127).

In double-precision IEEE 754, there is one sign bit, 11 exponent bits, and 52 significand bits.

There are other floating-point formats, which are less common. Some older ones use hexadecimal as a base (using the exponent to indicate shifts of four bits instead of one). An important type of floating-point format is decimal, where the exponent indicates powers of 10. In decimal floating point, the significand can be a binary integer or it can be a binary-coded decimal number (where each four bits indicates a decimal digit) or it can be a hybrid (groups of bits are used to indicate a small number of decimal digits according to a customized scheme).

An important property of floating-point numbers is that they cannot represent all real numbers (even in a finite range, of course) or even all rational numbers. This compels mathematical operations to return results rounded to representable numbers, which causes no end of problems for people unfamiliar with working with floating point. This property in turn becomes a feature of decimal floating point: It is good for working with currency denominations and other human-associated numbers that are usually manipulated in decimal, because most rounding errors can be eliminated by careful use of decimal floating point. Scientists and mathematicians, who work more with nature-associated or pure numbers instead of human-contaminated numbers, tend to prefer binary floating point, because it is more widely available and is well supported by hardware.

There are other ways to represent non-integer numbers in computers. Another common method is fixed point. In fixed point, a sequence of bits, such as 1101011, is interpreted with a radix point at a known, fixed position. The position would be fixed at a position useful for a specific application. So the bits 1101011 could stand for the number 11010.112. An advantage of fixed point is that it is easily implemented with standard hardware. To add two fixed-point numbers, we simply add them as if they were integers. To multiply two fixed-point numbers, we multiply them as if they were integers, but the result has twice as many positions after the radix point, so we either shift the bits to adjust for this or we write our code so that the results of such operations are interpreted with the known number of bits after the radix point. Some processors have instructions to support fixed point by adjusting multiplications for this effect.

Numbers can also be scaled to integers. For example, to work with United States currency, we simply multiply dollar amounts by 100 and do all arithmetic with integers. The radix point is only inserted when displaying final results (and is interpreted when reading data from humans). Another common scaling is to represent pixel intensities (from 0 to 1) by multiplying by 255, so that fractions from 0 to 1 fit into an eight-bit byte.

There is also software to provide extended precision (use several units of the basic arithmetic type to provide additional precision) or arbitrary precision (use a dynamic number of units to provide as much precision as desired). Such software is very slow compared to hardware-supported arithmetic and is typically used only for special purposes. Additionally, extended precision has essentially the same properties as floating point; it is just that the rounding errors are smaller, not gone. Arbitrary precision has the same flaw except that its dynamic precision may allow you to make the error small enough that you can obtain a final result that is within a necessary interval (possibly with proof that you have done so).

Another way to represent non-integers is by using fractions. You can store a numerator and a denominator, and perform arithmetic in much the same way taught in school: Multiply by multiplying numerators and multiplying denominators. Add by converting both fractions to have a common denominator, then add numerators. This sort of arithmetic is problematic because denominators very quickly become large, so you need extended precision or arbitrary precision to manage them.

You can also represent numbers symbolically or with compound expressions. For example, instead of storing the square root of two as a numerical value, you can store it with a data structure that represents the square root operation applied to the number 2. Performing any but the simplest operations with such representations requires very complicated software to manage expressions, combine them, find reductions, and so on. This sort of representation is used in specialized math software, such as Maple and Mathematica.

Finally, you can represent numbers any way you want. Our modern processors are general-purpose computing devices, up to the limits of their speed and storage capacity, so you can write algorithms that represent numbers with strings or data structures or any other technique.

Adding Fraction to current fraction?

You are combining two different algorithms. One is to perform a/b+c/d=(a*d+b*c)/(bd). The other is to perform a/b+c/d=(a*(lcd(b,d)/b) + c*(lcd(b,d)/d))/lcd(b,d)

numerator = numerator*d2+n2*denominator;
denominator = denominator*d2;

or

int lcd = Fraction.getLCD(denominator, d2);
numerator = numerator*(lcd/denominator)+n2*(lcd/d2);
denominator = lcd;

So in your example it would be:

(1/8) + (16/64) = (1*64+16*8)/(8*64) = 192/512 = 3/8

or

(1/8) + (16/64) = (1*(64/8) + 16*(64/64))/64 = 24/64 = 3/8



Related Topics



Leave a reply



Submit