Difference between revisions of "Rational Number Package"

From CSWiki
Jump to: navigation, search
 
m
Line 7: Line 7:
 
.6666667.
 
.6666667.
  
=== Constructing, destructing operations ===
+
=== Constructing and extraction operations ===
 
* fun static Rational create(int i) -- create Rational with a numerator of n and denominator of 1
 
* fun static Rational create(int i) -- create Rational with a numerator of n and denominator of 1
 
* fun static Rational create(float v) -- create a Rational with max denominator of 10000 (default)
 
* fun static Rational create(float v) -- create a Rational with max denominator of 10000 (default)
Line 15: Line 15:
 
* fun int num() -- return the numerator of the receiver
 
* fun int num() -- return the numerator of the receiver
 
* fun int den() -- return the denominator of the receiver.
 
* fun int den() -- return the denominator of the receiver.
 
 
=== Conversion to other types ===
 
=== Conversion to other types ===
 
* fun float toFloat() -- return a floating point approximation of the receiver
 
* fun float toFloat() -- return a floating point approximation of the receiver
 
* fun string toString() -- return a string representation of receiver, e.g. "2/3"
 
* fun string toString() -- return a string representation of receiver, e.g. "2/3"
 
 
=== Comparison operations ===
 
=== Comparison operations ===
 
* fun int signum() -- return -1, 0, +1 if receiver is less than, equal to or greater than zero.
 
* fun int signum() -- return -1, 0, +1 if receiver is less than, equal to or greater than zero.
 
* fun int cmp(int i) -- return -1, 0, +1 if receiver is less than, equal to or greater than i.
 
* fun int cmp(int i) -- return -1, 0, +1 if receiver is less than, equal to or greater than i.
 
* fun int cmp(Rational other) -- return -1, 0, +1 if receiver is less than, equal to, or greater than other.
 
* fun int cmp(Rational other) -- return -1, 0, +1 if receiver is less than, equal to, or greater than other.
 
+
=== Integer approximation ===
=== Integer approximation
 
 
* fun int trunc() -- return the largest integer no greater in magnitude than the receiver ("round towards zero")
 
* fun int trunc() -- return the largest integer no greater in magnitude than the receiver ("round towards zero")
 
* fun int floor() -- return the largest integer no greater than the receiver ("round towards minus infinity")
 
* fun int floor() -- return the largest integer no greater than the receiver ("round towards minus infinity")
 
* fun int ceil() -- return the smallest integer no less than the receiver ("round towards positive infinity")
 
* fun int ceil() -- return the smallest integer no less than the receiver ("round towards positive infinity")
 
* fun int round() -- return the closest integer to the receiver, rounding to even when the receiver is halfway between two integers.
 
* fun int round() -- return the closest integer to the receiver, rounding to even when the receiver is halfway between two integers.
 
+
=== Div and Mod ===
=== div and mod ===
 
 
* fun int div(Rational other) -- returns receiver divided by other using truncating division
 
* fun int div(Rational other) -- returns receiver divided by other using truncating division
 
* fun int div(int i) -- returns receiver divided by i using truncating division
 
* fun int div(int i) -- returns receiver divided by i using truncating division
 
* fun int mod(Rational other) -- return receiver modulus other using truncating division
 
* fun int mod(Rational other) -- return receiver modulus other using truncating division
 
* fun int mod(int i) -- returns receiver modulus i using truncating division
 
* fun int mod(int i) -- returns receiver modulus i using truncating division
=== unary operations ===  
+
=== Unary operations ===  
 
* fun Rational abs() -- returns a new Rational that is the absolute value of receiver
 
* fun Rational abs() -- returns a new Rational that is the absolute value of receiver
 
* fun Rational abs_() -- destructively modifies receiver to its absolute value and returns it
 
* fun Rational abs_() -- destructively modifies receiver to its absolute value and returns it
Line 44: Line 40:
 
* fun Rational negate(Rational result) -- sets result to the negative of the receiver and returns it.
 
* fun Rational negate(Rational result) -- sets result to the negative of the receiver and returns it.
 
* fun Rational reciprocal() -- returns a new Rational set to 1/receiver
 
* fun Rational reciprocal() -- returns a new Rational set to 1/receiver
* fun Rational reciprocal_() { return reciprocal(this); }
+
* fun Rational reciprocal_() -- destructively modifies the receiver to 1/receiver and returns it.
* fun Rational reciprocal(Rational result) {
+
* fun Rational reciprocal(Rational result) -- set result to 1/receiver and returns it.
 
+
=== Binary operations ===
 
+
* fun Rational add(Rational other) -- return new Rational set to receiver + other
 
+
* fun Rational add_(Rational other) -- return receiver after setting it to receiver + other
  signum(), cmp()
+
* fun Rational add(Rational other, Rational result) -- return result after setting it to receiver + other
 
+
* fun Rational add(int i) -- return new Rational set to receiver + i
=== Arithmetic operations ===
+
* fun Rational add_(int i) -- return receiver after setting it to receiver + i
  div(), mod(), abs(), negate(), reciprocal(), add(), sub(), mul(),
+
* fun Rational add(int i, Rational result) -- return result after setting it to receiver + i
  quo()
+
* fun Rational sub(Rational other) -- return new Rational set to receiver - other
 
+
* fun Rational sub_(Rational other) -- return receiver after setting it to receiver - other
=== Destructive operations ===
+
* fun Rational sub(Rational other, Rational result) -- return result after setting it to receiver - other
Most operations are non-destructive -- they create a new rational
+
* fun Rational sub(int i) -- return new Rational set to receiver - i
rather than modify the receiver -- but a number of operations include
+
* fun Rational sub_(int i) -- return receiver after setting it to receiver - i
versions that explicitly modify the receiver.  These are indicated by
+
* fun Rational sub(int i, Rational result) -- return result after setting it to receiver - i
a trailing '_' in the method name:
 
  
  set_(), norm_(), abs_(), negate_(), reciprocal_(), add_(), sub_(),
+
* fun Rational mul(Rational other) -- return new Rational set to receiver * other
  mul_(), quo_()
+
* fun Rational mul_(Rational other) -- return receiver after setting it to receiver * other
 +
* fun Rational mul(Rational other, Rational result) -- return result after setting it to receiver * other
 +
* fun Rational mul(int i) -- return new Rational set to receiver * i
 +
* fun Rational mul_(int i) -- return receiver after setting it to receiver * i
 +
* fun Rational mul(int i, Rational result) -- return result after setting it to receiver * i
  
== Rational Approximation ==
+
* fun Rational quo(Rational other) -- return new Rational set to receiver / other
 +
* fun Rational quo_(Rational other) -- return receiver after setting it to receiver / other
 +
* fun Rational quo(Rational other, Rational result) -- return result after setting it to receiver / other
 +
* fun Rational quo(int i) -- return new Rational set to receiver / i
 +
* fun Rational quo_(int i) -- return receiver after setting it to receiver / i
 +
* fun Rational quo(int i, Rational result) -- return result after setting it to receiver / i
  
 +
== About Rational Approximation ==
 
Of special note is the internal method that converts a floating point
 
Of special note is the internal method that converts a floating point
 
value to a rational.  We use a modified version of Farey's technique,
 
value to a rational.  We use a modified version of Farey's technique,
 
which is efficient and numerically stable.  The method allows you to
 
which is efficient and numerically stable.  The method allows you to
specify the largest permissable denominator used to approximate the
+
specify the largest permissible denominator used to approximate the
 
floating point value.  Even limiting the denominator to less than 1000
 
floating point value.  Even limiting the denominator to less than 1000
 
produces rational approximations that are very close to their
 
produces rational approximations that are very close to their

Revision as of 14:18, 15 December 2009

Overview

The Rational class lets you represent numbers as a quotient of two integers. One advantage of rational representation is that precicion is mainatained across arithmatic operations: 2/3 is really 2/3 and not .6666667.

Constructing and extraction operations

  • fun static Rational create(int i) -- create Rational with a numerator of n and denominator of 1
  • fun static Rational create(float v) -- create a Rational with max denominator of 10000 (default)
  • fun static Rational create(float v, int dlimit) -- create a Rational with max denominator of dlimit
  • fun static Rational create(Rational other) -- create a copy of the other Rational
  • fun static Rational create(int n, int d) -- create a normalized Rational from numerator n and denominator d.
  • fun int num() -- return the numerator of the receiver
  • fun int den() -- return the denominator of the receiver.

Conversion to other types

  • fun float toFloat() -- return a floating point approximation of the receiver
  • fun string toString() -- return a string representation of receiver, e.g. "2/3"

Comparison operations

  • fun int signum() -- return -1, 0, +1 if receiver is less than, equal to or greater than zero.
  • fun int cmp(int i) -- return -1, 0, +1 if receiver is less than, equal to or greater than i.
  • fun int cmp(Rational other) -- return -1, 0, +1 if receiver is less than, equal to, or greater than other.

Integer approximation

  • fun int trunc() -- return the largest integer no greater in magnitude than the receiver ("round towards zero")
  • fun int floor() -- return the largest integer no greater than the receiver ("round towards minus infinity")
  • fun int ceil() -- return the smallest integer no less than the receiver ("round towards positive infinity")
  • fun int round() -- return the closest integer to the receiver, rounding to even when the receiver is halfway between two integers.

Div and Mod

  • fun int div(Rational other) -- returns receiver divided by other using truncating division
  • fun int div(int i) -- returns receiver divided by i using truncating division
  • fun int mod(Rational other) -- return receiver modulus other using truncating division
  • fun int mod(int i) -- returns receiver modulus i using truncating division

Unary operations

  • fun Rational abs() -- returns a new Rational that is the absolute value of receiver
  • fun Rational abs_() -- destructively modifies receiver to its absolute value and returns it
  • fun Rational abs(Rational result) -- sets result to the absolute value of receiver and returns it
  • fun Rational negate() -- returns a new Rational that is the negative of the receiver
  • fun Rational negate_() -- destructively modifies the receiver to its negative and returns is
  • fun Rational negate(Rational result) -- sets result to the negative of the receiver and returns it.
  • fun Rational reciprocal() -- returns a new Rational set to 1/receiver
  • fun Rational reciprocal_() -- destructively modifies the receiver to 1/receiver and returns it.
  • fun Rational reciprocal(Rational result) -- set result to 1/receiver and returns it.

Binary operations

  • fun Rational add(Rational other) -- return new Rational set to receiver + other
  • fun Rational add_(Rational other) -- return receiver after setting it to receiver + other
  • fun Rational add(Rational other, Rational result) -- return result after setting it to receiver + other
  • fun Rational add(int i) -- return new Rational set to receiver + i
  • fun Rational add_(int i) -- return receiver after setting it to receiver + i
  • fun Rational add(int i, Rational result) -- return result after setting it to receiver + i
  • fun Rational sub(Rational other) -- return new Rational set to receiver - other
  • fun Rational sub_(Rational other) -- return receiver after setting it to receiver - other
  • fun Rational sub(Rational other, Rational result) -- return result after setting it to receiver - other
  • fun Rational sub(int i) -- return new Rational set to receiver - i
  • fun Rational sub_(int i) -- return receiver after setting it to receiver - i
  • fun Rational sub(int i, Rational result) -- return result after setting it to receiver - i
  • fun Rational mul(Rational other) -- return new Rational set to receiver * other
  • fun Rational mul_(Rational other) -- return receiver after setting it to receiver * other
  • fun Rational mul(Rational other, Rational result) -- return result after setting it to receiver * other
  • fun Rational mul(int i) -- return new Rational set to receiver * i
  • fun Rational mul_(int i) -- return receiver after setting it to receiver * i
  • fun Rational mul(int i, Rational result) -- return result after setting it to receiver * i
  • fun Rational quo(Rational other) -- return new Rational set to receiver / other
  • fun Rational quo_(Rational other) -- return receiver after setting it to receiver / other
  • fun Rational quo(Rational other, Rational result) -- return result after setting it to receiver / other
  • fun Rational quo(int i) -- return new Rational set to receiver / i
  • fun Rational quo_(int i) -- return receiver after setting it to receiver / i
  • fun Rational quo(int i, Rational result) -- return result after setting it to receiver / i

About Rational Approximation

Of special note is the internal method that converts a floating point value to a rational. We use a modified version of Farey's technique, which is efficient and numerically stable. The method allows you to specify the largest permissible denominator used to approximate the floating point value. Even limiting the denominator to less than 1000 produces rational approximations that are very close to their irrational counterparts, as can be seen in this example:

 // file: rational_eg.ck
 
 fun void test(float v, int dlimit) {
   Rational.create(v, dlimit) @=> Rational @ r;
   "Rational.create("+v+","+dlimit+")" => string label;
   <<< label, "~=", r.toString(), "~=", r.toFloat(), "err=", (r.toFloat()-v)*100/v, "%" >>>;
 }
 
 test(pi, 100);
 test(pi, 1000);
 test(pi, 10000);
 
 Math.sqrt(10.0) => float SQRT_10;
 test(SQRT_10, 100);
 test(SQRT_10, 1000);
 test(SQRT_10, 10000);
 
 Math.pow(2.0, 1/12.0) => float SEMITONE;
 test(SEMITONE, 100);
 test(SEMITONE, 1000);
 test(SEMITONE, 10000);

...which produces the following:

 bash-3.2$ chuck rational.ck rational_eg.ck
 Rational.create(3.1416,100) ~= 22/7 ~= 3.142857 err= 0.040250 % 
 Rational.create(3.1416,1000) ~= 355/113 ~= 3.141593 err= 0.000008 % 
 Rational.create(3.1416,10000) ~= 355/113 ~= 3.141593 err= 0.000008 % 
 Rational.create(3.1623,100) ~= 117/37 ~= 3.162162 err= -0.003652 % 
 Rational.create(3.1623,1000) ~= 721/228 ~= 3.162281 err= 0.000096 % 
 Rational.create(3.1623,10000) ~= 27379/8658 ~= 3.162278 err= 0.000000 % 
 Rational.create(1.0595,100) ~= 89/84 ~= 1.059524 err= 0.005731 % 
 Rational.create(1.0595,1000) ~= 196/185 ~= 1.059459 err= -0.000343 % 
 Rational.create(1.0595,10000) ~= 7893/7450 ~= 1.059463 err= -0.000001 % 

Links to the code, example file and test file

Comments, questions are welcome

rdpoor (at) gmail (dot) com