Базовый тип Rational

Разнообразные интервалы ( вещественные, комплексные, каухеровы) в конечном счете представляются несколькими вещественными числами. Это могут быть нижний и верхний концы вещественного интервала , или действительная и мнимая компоненты центра и радиус комплексного интервала и т.д. Естественно в API должны быть как конструкторы, создающие интервал по нескольким вещественным числам, так и функции-getter'ы, возвращающие вещественные характеристики интервала. Разные реализации могут использовать разные представления вещественных характеристик интервала: примитивные типы float, double, объекты BigInteger, BigDecimal или специально спроектированные классы.

Представляется однако, что на уровне API разнообразные реализации интервальных арифметик, входящие в JInterval, будут обмениваться через единый тип, представляющий вещественные числа. Назовем этот тип базовым типом. Единый базовых тип обеспечит интеграцию разных реализаций интервальных арифметик. Он позволит менять баланс между точностью и скоростью вычислений, проводить финальные итерации с повышенной точностью, используя результаты предыдущих итераций, выполненных с меньшей точностью.

Далее обсуждается множество вещественных значений, представимых базовым типом. Затем предлагается набор Java-классов, представляющих базовые тип.

Значения базового типа - рациональные числа или бесконечности

Мы не рассматриваем иррациональные числа в качестве концов и других характеристик интервалов, хотя Hans Boehm и предлагал класс, представляющий и рациональные и иррациональные числа. Его класс содержит алгоритм, который по заданной точности выдает рациональное приближение представляемого вещественного числа с этой или с лучшей точностью. Достаточной причиной не связываться в нашей библиотеке с интервалами с иррациональными границами является то, что проблема сравнения конструктивного вещественного числа с нулем алгоритмически неразрешима.

Поэтому базовые типы в нашей библиотеке будут представлять лишь рациональные числа. К ним хотелось бы добавить также -Infinity и +Infinity для представления границ бесконечных интервалов. Все вместе они представляют полностью упорядоченное множество.

Мы пока воздержались от появления таких объектов как нечисла (NaN) среди множества значений, чтобы сохранить полную упорядоченность множества значений. Однако желание поддерживать стандарт IEEE 754 может заставить нас представлять в Rational и нечисла (NaN) и уже заставил нас ввести в Rational такое значение как отрицательный ноль (-0.0).

Конструкторы и фабричные методы

Тип Rational является immutable. Определены несколько констант

 Rational.NEGATIVE_INFINITY - отрицательная бесконечность
 Rational.NEGATIVE_ZERO     - отрицательный ноль
 Rational.ZERO              - ноль
 Rational.POSITIVE_ZERO     - положительный ноль
 Rational.ONE               - положительная единица
 Rational.POSITIVE_INFINITY - положительная бесконечность

POSITIVE_ZERO и ZERO - разные имена одной и той же константы. NEGATIVE_ZERO - отрицательный ноль, который появился из желание быть совместимыми со стандартом IEEE 754. При сравнении отрицательный и положительный ноль равны. Однако некоторые операции в IEEE 754 отличаются для положительных и отрицательных нулей. Например, обратная величина от положительного нуля есть положительная бесконечность, а обратная величина отрицательного нуля есть отрицательная бесконечность.

Конструкторы типа Rational являются скрытыми (private). Вместо них доступны статические фабричные методы (factory methods), возвращающие значения Rational

 Rational r = Rational.valueOf(int v);
 Rational r = Rational.valueOf(long v);
 Rational r = Rational.valueOf(double v);
 Rational r = Rational.valueOf(Number v);
 Rational r = Rational.valueOf(Byte v);
 Rational r = Rational.valueOf(Short v);
 Rational r = Rational.valueOf(Integer v);
 Rational r = Rational.valueOf(Long v);
 Rational r = Rational.valueOf(Float v);
 Rational r = Rational.valueOf(Double v);
 Rational r = Rational.valueOf(BigInteger v);
 Rational r = Rational.valueOf(BigDecimal v);
 Rational r = Rational.valueOf(long numerator, long denominator);
              // return numerator/denominator
 Rational r = Rational.valueOf(BigInteger numerator, BigInteger denominator);
              // return numerator/denominator
 Rational r = Rational.valueOf(BigInteger numerator, BigInteger denominator, int exp);
              // return numerator/denominator*2^exp
 Rational r = Rational.valueOf(BigInteger unscaledValue, int exp);
              // return unscaledValue*2^exp 
 Rational r = Rational.pow2(int exp);
              // return 2^exp

Так как решение о нечислах (NaN) еще не принято, фабричные методы, у которых есть оба аргумента numerator и denominator, выбрасывают исключительную ситуацию, если numerator=denominator=0. Также поступают и фабричные методам с аргументами v типа double, Float, Double, Number, если аргумент v есть нечисло.

В теперешней версии недоделана проверка переполнения. Например, Rational.valueOf(BigInteger.valueOf(4), Integer.MAX_VALUE) вернет 2^(1+Integer.MIN_VALUE) вместо 2^(2+Integer.MAX_VALUE).

Разложение Rational на компоненты

 boolean b = x.isNegativeInfinity();
 boolean b = x.isPositiveInfinity();
 boolean n = x.isFinite();
             // return true для всех Rational кроме бесконечностей
 int s = x.signum();
         // return +1 для положительных
         // return -1 для отрицательных
         // return 0 для всех нулей - положительных и отрицательных
 BigInteger n = x.getNumerator();
             // Числитель после сокращения
 BigInteger d = x.getDenominator();
             // Знаменатель после сокращения - положительное число для конечных Rational
 // Числитель и знаменатель положительной бесконечности выдаются как +1/0.
 // Числитель и знаменатель отрицательной бесконечности выдаются как -1/0.
 // Числитель и знаменатель любого нуля выдаются как 0/1.
 int exp = x.getFloorLog2();
           // return floor(log2(abs(x)))
           // Выбрасывает исключительную ситуацию для нулей
           // return Integer.MAX_VALUE для бесконечностей
 int exp = x.getCeilingLog2();
           // return ceiling(log2(abs(x)))
           // return Integer.MIN_VALUE для нулей
           // Выбрасывает исключительную ситуацию для бесконечностей

Несколько слов о внутреннем представлении типа Rational. Рациональные числа хранятся в сокращенном виде - у числителя и знаменателя нет общих простых множителей. Кроме того, степени двойки выносятся из числителя и знаменателя. Таким образом, рациональное число хранится как n2/d2*2^exp2. Таким образом при d2=1 значения типа Rational являются бинарными числами с плавающей точкой. Следующие операции вытаскивают детали внутреннего представления.

 int exp2 = x.getExp2();
 BigInteger n2 = x.getNumeratorWithout2s();
 BigInteger d2 = x.getDenominatorWithout2s();

Сравнения

 boolean b = x.eq(y); // x == y
 boolean b = x.ne(y); // x != y
 boolean b = x.lt(y); // x < y
 boolean b = x.le(y); // x <= y
 boolean b = x.gt(y); // x > y
 boolean b = x.ge(y); // x >= y
 int cmp = x.compareTo(y); // -1, x < y; 0, x == y; +1, x > y

Предыдущие сравнения считают отрицательный и положительный нули равными. Следующее сравнение соответствует totalOrder стандарата IEEE 754 и считает, что отрицательный нуль меньше положительного.

 boolean b = x.compareTotalTo(y);

Функции min и max также отнесены к сравнениям. Они различают отрицательный и положительный нули.

 Rational r = x.min(y);
 Rational r = x.max(y);

Точные арифметические операции

 Rational r = x.add(y);
 Rational r = x.subtract(y);
 Rational r = x.negate();
 Rational r = x.abs();
 Rational r = x.multiply(y);
 Rational r = x.divide(y); // Выбрасывает исключение при y = 0 
 Rational r = x.inverse(); // Выбрасывает исключение при x = 0
 Rational r = x.sqrt(); // Выбрасывает исключение, если x не точный квадрат.
 Rational r = x.power(int k);

Приближенные арифметические операции

При выполнении длинной цепочки вычислений могут появляться рациональные числа со все большими значениями числителя и знаменателя. Поэтому наряду с точными арифметических операций могут быть полезными и приближенные. Приближенные арифметические операции имеют, кроме двух операндов, еще один параметр, называемый контекст. Контекст определяет ValueSet - подмножество рациональных чисел, до которых должен округляться результат. Контекст также определяет функцию round, переводящую произвольное рациональное число в рациональное число из ValueSet. Другими словами, функция round задает направление округления. Приближенные арифметические операции x.op(y, context) определются как context.round(x.exactOp(y)).

Сейчас в библиотеке реализован только BinaryMathContext - контект, множество значений которого BinaryValueSet есть множество значений некоторого бинарного формата стандарта IEEE 754. BinaryValueSet параметризуется тремя числами: precision, minexp, maxexp . Это плавающие числа вида fp = m*2^e, где

 m и e - целые
 abs(m) < 2^precision
 fp - кратно 2^(minexp - precision + 1)
 abs(fp) < 2^(maxexp + 1)

Предполагается также добавить в BinaryValueSet признак flushToZero, который исключает из множества значений денормализованные числа. BinaryMathContext содержит также поле типа java.math.RoundingMode, определяющее направление, в котором округляет round.

Возможно в будущем будет реализован RationalMathContext, у которого множество RationalValueSet - рациональные числа с некоторыми ограничениями на размер числителя и знаменателя. А сейчас определены такие приближенные арифметические операции

 BinaryMathContext mc = ...;
 Rational r = x.round(mc);
 Rational r = x.add(y, mc);
 Rational r = x.subtract(y, mc);
 Rational r = x.multiply(y, mc);
 Rational r = x.divide(y, mc); // Выбрасывает исключение при y = 0 
 Rational r = x.inverse(mc); // Выбрасывает исключение при x = 0
 Rational r = x.sqrt(mc); // Выбрасывает исключение при x < 0

Экспорт в стандартные типы

Класс Rational является подклассом класса java.lang.Number и соответствующим образом переопределяет его методы

 double v = x.doubleValue();
 float v = x.floatValue();
 long v = x.longValue();
 int v = x.longValue();
 short v = x.longValue();
 byte v = x.longValue();

Кроме, этого есть дополнительные функции преобразования

 BigInteger v = x.toBigInteger();
 BigDecimal v = x.bigDecimalValue(java.math.MathContext mc);
 float v = x.floatValue(java.math.RoundingMode roundingMode);
 double v = x.doubleValue(java.math.RoundingMode roundingMode);

Специализации последней функции:

 double v = x.doubleValueUp();
 double v = x.doubleValueDown();
 double v = x.doubleValueCeiling();
 double v = x.doubleValueFloor();
 double v = x.doubleValueHalfUp();
 double v = x.doubleValueHalfDown();
 double v = x.doubleValueHalfEven();
 double v = x.doubleValueExact();

Детали реализации

Ожидается, что чаще будут использоваться реализации интервалов, границы которых не произвольные рациональные числа, а бинарные числа с плавающей точкой, а еще чаще - double границы. Поэтому при выборе представления типа Rational особое внимание уделялось этим частным случаям. Вот диаграмма наследования классов, каждый из которых представляет какой-то случай рационального числа. Значок (A) помечает абстрактные классы.

 -+ Rational (A)
  |
  +-- RationalImpl
  |
  +-+ Binary (A)
    |
    +-- BinaryImpl
    |
    +-+ BinaryDouble (A)
      |
      +-- BinaryDoubleImpl
      |
      +-- Zero
      |
      +-+ Infinity (A)
        |
        +-- NegativeInfinity
        |
        +-- PositiveInfinity

RationalImpl - рациональное число общего вида, представленное двумя BigInteger полями с числителем и знаменателем и int полем с двоичное экспонентой. BinaryImpl - рациональное число, являющееся бинарным числом с плавающей точкой. Представлено одним BigInteger полем с мантиссой и int полем с даоичной экспонентой. BinaryDoubleImpl - рациональное число, которое может быть представлено типом double.

Соответственно арифметические операции имеют отдельные алгоритмы для пары рациональных чисел, для пары бинарных чисел, для пары double чисел. Происходит переключение на нужный алгоритм в зависимости от конкретных типов аргументов арифметической операции.

К сожалению, реализация использует не слишком быструю целую арифметику из java.math.BigInteger (время умножения пропорционально произведению разрядностей операндов). Это замедляет арифметические операции над рациональными числами с длинными числителем и знаменателем. Существуют асимптотически более быстрые реализации целой арифметики:apifloat, gmplib. Предполагается ввести SPI (Service Provider Interface) для того чтобы рациональные числа большой разрядности представлялись и обрабатывались внешними пакетами.

Scala API

Реализованный на языке Java тип Rational имеет нужную семантику, но синтаксически неудобен для написания научных программ. Сравните

 r = x + y*z
 r = x.add(y.multiply(z, mc), mc);

Поэтому предполагается мигрировать на язык Scala. Сейчас написан Scala-класс com.kenai.jinterval.scla.number.Rational, являющийся wrapper-ом Java-класса Rational.

 class Rational(imp: com.kenai.jinterval.number.Rational) extends ScalaNumber {
  def impl = imp
 
  override def isWhole = false
  override def underlying = imp
  override def doubleValue = imp.doubleValue
  override def floatValue = imp.floatValue
  override def longValue = imp.longValue
  override def intValue = imp.intValue
 
  def isNaN = false
  def isNegativeInfinity = imp.isNegativeInfinity
  def isPositiveInfinity = imp.isPositiveInfinity
  def isFinite = imp.isFinite
  def getNumerator = new BigInt(imp.getNumerator)
  def getDenominator = new BigInt(imp.getDenominator)
  def signum = imp.signum
  def getCeilLog2 = imp.getCeilLog2
  def getFloorLog2 = imp.getFloorLog2
  def compareTo(that: Rational) = imp.compareTo(that.impl)
  def round(mc: RationalMathContext) = mc.round(imp)
  def doubleValue(rm: java.math.RoundingMode) = imp.doubleValue(rm)
  def doubleValueUp = imp.doubleValueUp
  def doubleValueDown = imp.doubleValueDown
  def doubleValueCeiling = imp.doubleValueCeiling
  def doubleValueFloor = imp.doubleValueFloor
  def doubleValueHalfUp = imp.doubleValueHalfUp
  def doubleValueHalfDown = imp.doubleValueHalfDown
  def doubleValueHalfEven = imp.doubleValueHalfEven
  def doubleValueExact = imp.doubleValueExact
  def toBigInt = new BigInt(imp.toBigInteger)
  def bigDecimalValue(mc: java.math.MathContext) = new BigDecimal(imp.bigDecimalValue(mc))
  
  def negate(implicit mc: RationalMathContext) = mc.negate(this)
  def abs(implicit mc: RationalMathContext) = mc.abs(this)
  def inverse(implicit mc: RationalMathContext) = mc.inverse(this)
 
  def < (y: Rational): Boolean = this.imp.lt(y.impl)
  def <= (y: Rational): Boolean = this.imp.le(y.impl)
  def > (y: Rational): Boolean = this.imp.lt(y.impl)
  def >= (y: Rational): Boolean = this.imp.ge(y.impl)
  def == (y: Rational): Boolean = this.imp.eq(y.impl)
  
  def + (y: Rational)(implicit mc: RationalMathContext): Rational = mc.add(this, y)
  def - (y: Rational)(implicit mc: RationalMathContext): Rational = mc.subtract(this, y)
  def * (y: Rational)(implicit mc: RationalMathContext): Rational = mc.multiply(this, y)
  def / (y: Rational)(implicit mc: RationalMathContext): Rational = mc.divide(this, y)
  def sqrt()(implicit mc: RationalMathContext): Rational = mc.sqrt(this)
 
  def min (y: Rational) = if (this.compareTo(y) <= 0) this else y
  def max (y: Rational) = if (this.compareTo(y) >= 0) this else y
 
  override def toString = impl.toString
 }
 
 object Rational {
  def valueOf(v: Number): Rational = new Rational(com.kenai.jinterval.number.Rational.valueOf(v))
  def valueOf(v: com.kenai.jinterval.number.Rational): Rational = new Rational(com.kenai.jinterval.number.Rational.valueOf(v))
 
  implicit def valueOf(v: Double): Rational = new Rational(com.kenai.jinterval.number.Rational.valueOf(v))
 }

Благодаря возможности языка Scala переопределять операторы и благодаря неявным параметрам вышеприведенный пример будет выглядеть на Scale так

 implicit val mc: RationalMathContext
 val r = x + y*z