Enough with imprecise floating point datatypes called float
anddouble
. I present to you Rational. Of course, Rational number arithmetic is easy, so I took up a much more interesting challenge: Rational Number Approximation. This is what I have implemented in my code. I have employed a technique similar to binary search, the only difference being that I am the mediant in place of the middle element.
Rational.java
/**
* This class encapsulates a <em>Rational</em> number. Any rational number
* {@code R} can be represented as a quotient of two whole numbers,
* {@code p}, and {@code q}. Provided a decimal number,
* this class can approximate the numerator and denominator to precision of
* 1E-11 (the default). It is also a handy implementation for approximating
* irrational values like that of {@link java.lang.Math#PI Math.PI},
* or {@link java.lang.Math#E Math.E}, or the golden ratio: φ.
*
* @author Subhomoy Haldar (ambigram_maker)
* @version 1.1
*/
public class Rational {
/**
* A public constant that defines the rational value of 0.
*/
public static final Rational ZERO = new Rational(0, 1);
/**
* A public constant that defines the rational value of 1.
*/
public static final Rational ONE = new Rational(1, 1);
/**
* A public constant that defines the rational value of 0.5.
*/
public static final Rational HALF = new Rational(1, 2);
/*
* The Lowest and the Highest levels of precision allowed.
*/
private static final double LWST_PREC = 1E-3;
private static final double HIST_PREC = 1E-16;
private static double precision = 1E-10;
private final long num;
private final long den;
private final double result;
/**
* Creates a new {@code Rational} with the given numerator and
* denominator. It has special cases for Positive Infinity
* ({@link java.lang.Double#POSITIVE_INFINITY Double.POSITIVE_INFINITY}),
* Negative Infinity ({@link java.lang.Double#NEGATIVE_INFINITY
* Double.NEGATIVE_INFINITY}) and Not A Number
* ({@link java.lang.Double#NaN Double.NaN}.
*
* @param numerator The numerator.
* @param denominator The denominator.
*/
public Rational(long numerator, long denominator) {
// for dealing with "infinities" and "NaN":
if (denominator == 0) {
den = 0;
if (numerator > 0) {
num = 1;
result = Double.POSITIVE_INFINITY;
} else if (numerator < 0) {
num = -1;
result = Double.NEGATIVE_INFINITY;
} else {
num = 0;
result = Double.NaN;
}
return;
}
if (denominator < 0) {
numerator = 0L - numerator;
denominator = 0L - denominator;
}
num = numerator;
den = denominator;
result = (double) numerator / denominator;
}
/**
* Creates a new {@code Rational} object that approximates the value of
* the decimal to the set level of {@link #getPrecision() precision}. It
* is also capable of approximating irrational values like
* {@link java.lang.Math#PI Math.PI}, {@link java.lang.Math#E Math.E} or
* the golden ratio, φ.
*
* @param decimal The value to approximate.
*/
public Rational(double decimal) {
// Exit clauses:
if (decimal == Double.NaN) {
num = 0;
den = 0;
result = Double.NaN;
return;
}
if (decimal == Double.POSITIVE_INFINITY) {
num = 1;
den = 0;
result = Double.POSITIVE_INFINITY;
return;
}
if (decimal == Double.NEGATIVE_INFINITY) {
num = -1;
den = 0;
result = Double.NEGATIVE_INFINITY;
return;
}
long nu, de;
long whole = 0; // fail-safe value
boolean negative = decimal < 0;
decimal = Math.abs(decimal);
boolean hasWhole = decimal >= 1;
if (hasWhole) { // keep fractional part.
whole = (long) decimal;
decimal -= whole;
}
if (decimal == 0) { // no fractional part present or 0 input
num = negative ? 0L - whole : whole;
den = 1;
result = negative ? 0D - whole : whole;
return;
}
// initially, the extreme points are 0 and 1.
// decimal always lies in the interval: (n1/d1, n2/d2)
long n1 = 0, d1 = 1;
long n2 = 1, d2 = 1;
double epsilon; // the error amount in the approximation.
while (true) {
long n = n1 + n2, d = d1 + d2;
double result = (double) n / d;
epsilon = Math.abs(result - decimal);
if (epsilon <= precision) { // goal reached
nu = n;
de = d;
break;
} else if (result < decimal) { // increase lower bound
n1 = n;
d1 = d;
} else { // increase upper bound
n2 = n;
d2 = d;
}
}
if (hasWhole) { // add the whole part to the fraction
nu += de * whole;
}
num = negative ? 0L - nu : nu;
den = de;
result = (double) num / den;
}
/**
* Returns the set level of precision. The <i>default</i> level of
* precision is {@code 1.0E-10}, unless changed.
*
* @return The level of precision.
*/
public static double getPrecision() {
return precision;
}
/**
* Changes the set level of precision. However, the maximum and minimum
* levels of precision are defined and the value of precision
* <i>snaps</i> to these values if the parameter is <i>more</i> or
* <i>less</i> than them, respectively.
*
* @param precision The level of precision to set.
*/
public static void setPrecision(double precision) {
if (precision < 0) precision = 0D - precision;
if (precision < HIST_PREC) precision = HIST_PREC;
else if (precision > LWST_PREC) precision = LWST_PREC;
Rational.precision = precision;
}
// public long getNum() {
// return num;
// }
// public long getDen() {
// return den;
// }
/**
* Returns the Highest Common Factor of two integers. It employs the
* Euclidean division method.
*
* @param a One of the two numbers.
* @param b The other number.
* @return The H.C.F of {@code a} and {@code b}.
*/
private static long hcf(long a, long b) {
if (a == 0 || b == 0) {
return 0; // ???
}
// turn all the negative arguments to positive.
if (a < 0) a = 0L - a;
if (b < 0) b = 0L - b;
if (a < b) {
long t = a;
a = b;
b = t;
}
long r;
do {
r = a % b;
a = b;
b = r;
} while (r > 0);
return a;
}
// Demo
public static void main(String[] args) {
Rational PI = new Rational(Math.PI);
System.out.println("Pi = " + PI);
}
/**
* This method returns the {@code Rational} object that is the reduced
* form of {@code this Rational}. (More specifically,
* the numerator and denominator have no common factor.)
*
* @return The reduced form of {@code this Rational}.
*/
public Rational reduce() {
long hcf = hcf(num, den);
if (hcf == 0) { // infinities and NaN
return this;
} else {
long n = num / hcf;
long d = den / hcf;
return new Rational(n, d);
}
}
/**
* Returns the <i>sum</i> of {@code rational} with {@code this}.
*
* @param rational The {@code Rational} to add.
* @return Their sum.
*/
public Rational add(Rational rational) {
if (this.result == Double.NaN) {
return this;
} else //noinspection ConstantConditions
if (rational.result == Double.NaN) {
return rational;
}
Rational o = reduce();
long n1 = o.num, d1 = o.den;
o = rational.reduce();
long n2 = o.num, d2 = o.den;
return new Rational(n1 * d2 + n2 * d1, d1 * d2).reduce();
}
/**
* Returns the <i>difference</i> of {@code rational} with {@code this}.
*
* @param rational The {@code Rational} to subtract.
* @return Their difference.
*/
public Rational subtract(Rational rational) {
return add(new Rational(0L - rational.num, rational.den));
}
/**
* Returns the <i>product</i> of {@code rational} and {@code this}.
*
* @param rational The {@code Rational} to multiply with.
* @return Their product.
*/
public Rational multiply(Rational rational) {
return new Rational(
this.num * rational.num,
this.den * rational.den)
.reduce();
}
/**
* <i>Divides</i> {@code this} with {@code rational}.
*
* @param rational The divisor.
* @return The required quotient.
*/
public Rational divide(Rational rational) {
return multiply(rational.reciprocate());
}
/**
* Returns the reciprocal of {@code this}.
*
* @return the reciprocal of {@code this}.
*/
public Rational reciprocate() {
return new Rational(den, num);
}
/**
* Returns the {@code double} representation of tis {@code Rational}.
*
* @return the {@code double} representation of tis {@code Rational}.
*/
public double toDouble() {
return result;
}
/**
* Returns the {@code String} representation of tis {@code Rational}.
*
* @return the {@code String} representation of tis {@code Rational}.
*/
@Override
public String toString() {
return Long.toString(num).concat("/").concat(Long.toString(den));
}
/**
* Compares {@code this} object with another with respect to class and
* then the values of the numerator and denominator.
*
* @param another The {@code Object} to compare with.
* @return {@code true} if the objects are equal, {@code false} otherwise.
*/
@Override
public boolean equals(Object another) {
if (another instanceof Rational) {
Rational oldF = reduce();
Rational newF = ((Rational) another).reduce();
return (oldF.num == newF.num) &&
(oldF.den == newF.den);
}
return false;
}
/**
* Returns {@code this} to the power {@code p}.
*
* @param p The power to be raised to.
* @return {@code this} to the power {@code p}.
*/
public Rational pow(int p) {
Rational result = ONE;
Rational n = new Rational(num, den);
boolean neg = p < 0;
if (neg) p = 0 - p;
while (p > 0) {
if ((p & 1) == 1) {
result = result.multiply(n);
p--;
}
n = n.multiply(n);
p >>>= 1;
}
return neg ? result.reciprocate() : result;
}
/**
* Returns {@code this} to the <i>fractional</i> power {@code p}.
*
* @param p The power to be raised to.
* @return {@code this} to the power {@code p}.
*/
public Rational pow(Rational p) {
return new Rational(Math.pow(this.result, p.result));
}
}
RationalTest.java
import junit.framework.TestCase;
public class RationalTest extends TestCase {
public void testAdd() {
Rational r1, r2;
r1 = new Rational(10, 20);
r2 = new Rational(20, 30);
assertEquals(new Rational(7, 6), r1.add(r2));
}
public void testSubtract() {
Rational r1, r2;
r1 = new Rational(20, 30);
r2 = new Rational(10, 20);
assertEquals(new Rational(1, 6), r1.subtract(r2));
}
public void testMultiply() {
Rational r1, r2;
r1 = new Rational(0.5);
r2 = new Rational(2);
assertEquals(Rational.ONE, r1.multiply(r2));
}
public void testDivide() {
Rational r1, r2;
r1 = new Rational(0.5);
r2 = new Rational(0.0625);
assertEquals(new Rational(8), r1.divide(r2));
}
public void testPow() {
assertEquals(Rational.ONE, new Rational(2).pow(Rational.ZERO));
assertEquals(new Rational(1, 64), new Rational(1, 4).pow(3));
}
}
This is the first version and more tests are needed (this is where I would really appreciate suggestions and illustrations). Inspite of that, my code works really well. Using the default settings, the following result is obtained:
Pi = 312689/99532
This evaluates to 3.1415926536189366233975003014106. Now, the real π is 3.1415926535897932384626433832795 and is only 2.9143384934856918131098731363655e-11 away from the result. I would request everyone to go on and experiment with my code, find out any flaws in my code and suggest ways for improvement.
java.lang.Number
\$\endgroup\$