001: /*
002: * $RCSfile: Rational.java,v $
003: *
004: * Copyright (c) 2005 Sun Microsystems, Inc. All rights reserved.
005: *
006: * Use is subject to license terms.
007: *
008: * $Revision: 1.2 $
009: * $Date: 2005/04/29 23:19:18 $
010: * $State: Exp $
011: */
012: package com.sun.media.jai.util;
013:
014: /**
015: * A class to perform Rational arithmetic.
016: *
017: * @since 1.0
018: */
019: public class Rational {
020:
021: public long num;
022: public long denom;
023:
024: public Rational(long num, long denom) {
025: this .num = num;
026: this .denom = denom;
027: }
028:
029: public Rational(Rational r) {
030: this .num = r.num;
031: this .denom = r.denom;
032: }
033:
034: /**
035: * Returns a Rational defined by a given number of terms
036: * of a continued fraction:
037: *
038: * terms[0] + 1
039: * -------------------------
040: * terms[1] + 1
041: * --------------
042: * terms[2] + ...
043: */
044: public static Rational createFromFrac(long[] terms, int len) {
045: Rational r = new Rational(0, 1);
046: for (int i = len - 1; i >= 0; i--) {
047: r.add(terms[i]);
048: if (i != 0) {
049: r.invert();
050: }
051: }
052:
053: return r;
054: }
055:
056: private static final int MAX_TERMS = 20;
057:
058: /**
059: * Returns a Rational that is within the given tolerance
060: * of a given float value.
061: */
062: public static Rational approximate(float f, float tol) {
063: // Expand f as a continued fraction by repeatedly removing the integer
064: // part and inverting.
065: float rem = f;
066: long[] d = new long[MAX_TERMS];
067: int index = 0;
068: for (int i = 0; i < MAX_TERMS; i++) {
069: int k = (int) Math.floor(rem);
070: d[index++] = k;
071:
072: rem -= k;
073: if (rem == 0) {
074: break;
075: }
076: rem = 1.0F / rem;
077: }
078:
079: // Evaluate with increasing number of terms until the tolerance
080: // has been reached
081: Rational r = null;
082: for (int i = 1; i <= index; i++) {
083: r = Rational.createFromFrac(d, i);
084: if (Math.abs(r.floatValue() - f) < tol) {
085: return r;
086: }
087: }
088:
089: return r;
090: }
091:
092: /**
093: * Returns a Rational that is within the given tolerance
094: * of a given double value.
095: */
096: public static Rational approximate(double f, double tol) {
097: // Expand f as a continued fraction by repeatedly removing the integer
098: // part and inverting.
099: double rem = f;
100: long[] d = new long[MAX_TERMS];
101: int index = 0;
102: for (int i = 0; i < MAX_TERMS; i++) {
103: long k = (long) Math.floor(rem);
104: d[index++] = k;
105:
106: rem -= k;
107: if (rem == 0) {
108: break;
109: }
110: rem = 1.0F / rem;
111: }
112:
113: // Evaluate with increasing number of terms until the tolerance
114: // has been reached
115: Rational r = null;
116: for (int i = 1; i <= index; i++) {
117: r = Rational.createFromFrac(d, i);
118: if (Math.abs(r.doubleValue() - f) < tol) {
119: return r;
120: }
121: }
122:
123: return r;
124: }
125:
126: private static long gcd(long m, long n) {
127: if (m < 0) {
128: m = -m;
129: }
130: if (n < 0) {
131: n = -n;
132: }
133:
134: while (n > 0) {
135: long tmp = m % n;
136: m = n;
137: n = tmp;
138: }
139: return m;
140: }
141:
142: /** Reduces the internal representation to lowest terms. */
143: private void normalize() {
144: if (denom < 0) {
145: num = -num;
146: denom = -denom;
147: }
148:
149: long gcd = gcd(num, denom);
150: if (gcd > 1) {
151: num /= gcd;
152: denom /= gcd;
153: }
154: }
155:
156: /**
157: * Adds an integer to this Rational value.
158: */
159: public void add(long i) {
160: num += i * denom;
161: normalize();
162: }
163:
164: /**
165: * Adds an integer to this Rational value.
166: */
167: public void add(Rational r) {
168: num = num * r.denom + r.num * denom;
169: denom *= r.denom;
170: normalize();
171: }
172:
173: /**
174: * Subtracts an int from this Rational value.
175: */
176: public void subtract(long i) {
177: num -= i * denom;
178: normalize();
179: }
180:
181: /**
182: * Subtracts an integer to this Rational value.
183: */
184: public void subtract(Rational r) {
185: num = num * r.denom - r.num * denom;
186: denom *= r.denom;
187: normalize();
188: }
189:
190: /**
191: * Multiplies an integer to this Rational value.
192: */
193: public void multiply(long i) {
194: num *= i;
195: normalize();
196: }
197:
198: /**
199: * Multiplies a Rational to this Rational value.
200: */
201: public void multiply(Rational r) {
202: num *= r.num;
203: denom *= r.denom;
204: normalize();
205: }
206:
207: /**
208: * Inverts this Rational value.
209: */
210: public void invert() {
211: long tmp = num;
212: num = denom;
213: denom = tmp;
214: }
215:
216: /**
217: * Returns the approximate float value of this Rational.
218: */
219: public float floatValue() {
220: return (float) num / denom;
221: }
222:
223: /**
224: * Returns the approximate double value of this Rational.
225: */
226: public double doubleValue() {
227: return (double) num / denom;
228: }
229:
230: /**
231: * Returns this Rational as a String in the form '###/###'.
232: */
233: public String toString() {
234: return num + "/" + denom;
235: }
236:
237: /**
238: * Returns the ceil (equivalent of Math.ceil())
239: */
240: public static int ceil(long num, long denom) {
241:
242: int ret = (int) (num / denom);
243:
244: if (num > 0) {
245: if ((num % denom) != 0) {
246: ret += 1;
247: }
248: }
249:
250: return ret;
251: }
252:
253: /**
254: * Returns the floor (equivalent of Math.floor())
255: */
256: public static int floor(long num, long denom) {
257:
258: int ret = (int) (num / denom);
259:
260: if (num < 0) {
261: if ((num % denom) != 0) {
262: ret -= 1;
263: }
264: }
265:
266: return ret;
267: }
268:
269: /**
270: * Prints out rational approximations of a floating point argument
271: * with 1 to 8 digits of accuracy.
272: */
273: public static void main(String[] args) {
274: float f = Float.parseFloat(args[0]);
275: for (int i = 1; i < 15; i++) {
276: Rational r = Rational.approximate(f, (float) Math.pow(10,
277: -i));
278: System.out.println(r + " = " + r.floatValue());
279: }
280: }
281: }
|