Библиотека BOOST ++: рациональные числа

Содержание

Краткое описание класса rational

Объяснение

Основы

Требования к целому типу

Интерфейс

         Вспомогательные функции

         Конструкторы

         Арифметические операции

         Ввод и вывод

         Присваивание по месту

         Преобразования

         Числитель и знаменатель

Быстродействие

Исключения

Внутренее представление

Замечания о дизайне

         Минимальная реализация

         Целые числа с ограниченным диапазоном

         Преобразование из чисел с плавающей точкой

         Абсолютное значение

Ссылки

История и признательности

Краткое описание класса rational

#include <boost/rational.hpp>

namespace boost {

template <typename I> I gcd(I n, I m);
template <typename I> I lcm(I n, I m);

class bad_rational;

template<typename I> class rational {
    typedef I int_type;

    // Constructors
    rational();          // Zero
    rational(I n);       // Equal to n/1
    rational(I n, I d);  // General case (n/d)

    // Normal copy constructors and assignment operators

    // Assignment from I
    rational& operator=(I n);

    // Assign in place
    rational& assign(I n, I d);

    // Representation
    I numerator() const;
    I denominator() const;

    // In addition to the following operators, all of the "obvious" derived
    // operators are available - see operators.hpp

    // Arithmetic operators
    rational& operator+= (const rational& r);
    rational& operator-= (const rational& r);
    rational& operator*= (const rational& r);
    rational& operator/= (const rational& r);

    // Arithmetic with integers
    rational& operator+= (I i);
    rational& operator-= (I i);
    rational& operator*= (I i);
    rational& operator/= (I i);

    // Increment and decrement
    const rational& operator++();
    const rational& operator--();

    // Operator not
    bool operator!() const;

    // Comparison operators
    bool operator< (const rational& r) const;
    bool operator== (const rational& r) const;

    // Comparison with integers
    bool operator< (I i) const;
    bool operator> (I i) const;
    bool operator== (I i) const;
}

// Unary operators
template <typename I> rational<I> operator+ (const rational<I>& r);
template <typename I> rational<I> operator- (const rational<I>& r);

// Reversed order operators for - and / between (types convertible to) I and rational
template <typename I, typename II> inline rational<I> operator- (II i, const rational<I>& r);
template <typename I, typename II> inline rational<I> operator/ (II i, const rational<I>& r);

// Absolute value
template <typename I> rational<I> abs (const rational<I>& r);

// Input and output
template <typename I> std::istream& operator>> (std::istream& is, rational<I>& r);
template <typename I> std::ostream& operator<< (std::ostream& os, const rational<I>& r);

// Type conversion
template <typename T, typename I> T rational_cast (const rational<I>& r);

Объяснение

Числа могут быть представлены в нескольких разных формах. Базовыми являются натуральные числа (неотрицательные целые числа), целые числа и действительные числа. Эти типы аппроксимируются встроенными типа C++ unsigned int, int, и float (а также различными их эквивалентами разного размера).

Стандартная библиотека C++ расширяет диапазон числовых типов за счет реализации типа complex - для комплексных чисел.

Данная библиотека обеспечивает еще один числовой тип - рациональные числа .

Класс rational реализован как шаблон, примерно как стандартный класс complex.

Основы

Математическая концепция рациональных чисел заключается в дробях - то есть числа представляются как отношения двух целых чисел. Эта концепция отличается от концепции действительных чисел, которые могут принимать намного больше значений (к примеру, квадратный корень 2 нельзя представить в виде дроби).

Компьютеры не могут представлять математические концепции точно - всегда приходится делать компромиссы. Машинное представление целых чисел имеет ограниченный диапазон представимых значений (обычно 32 бита), а машинная аппроксимация действительных чисел ограничена в точности. Компромиссы имеют разные причины - машинные целые допускают точные вычисления, но в ограниченном диапазоне, тогда как машинные действительные числа допускают намного больший диапазон, но за счет точности.

Класс рациональных чисел обеспечивает альтернативный компромисс. Вычисления с рациональными числами точные, но есть ограничения на возможный диапазон. Точнее говоря, рациональные числа точны до тех пор, пока числитель и знаменатель (которые всегда хранятся в нормализованном виде, с сокращенными общими множителями) находятся в пределах диапазона используемых целых чисел. Когда значения выходят за пределы этих границ, получается переполнение и результат неопределен.

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

Требования к целым типам

Тип rational получает единственный параметр шалона I. Этот используемый целый тип для представления числителя и знаменателя рационального числа. Любой встроенный целый тип C++ подходит в качестве I. Созданные пользователем типы также могут быть использованы, но пользователи должны учитывать, что эффективность класса rational сильно зависит от эффективности используемого целого типа (часто сложным образом - см. специальные замечания в секции Эффективность). Замечание: если возникнет необходимость реализовать поддержку целых с неограниченной точностью, то такой тип будет полностью поддерживаться классом rational.

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

Далее, I должен быть похож на целый тип, то есть следующие выражения должны быть корректными для двух любых величин n и m типа I, с "ожидаемой" семантикой:

 

Для типа должны быть возможны значения 0 и 1. Должно быть возможно получить их с помощью выражений I(0) и I(1) соответственно. Замечание: это не означает, что тип I должен допускать неявное преобразование из целого - достаточно явного (explicit) конструктора.

Тип I может быть беззнаковым. В этом случае использующий его класс rational также будет беззнаковым. В этом случае ошибки обратного переполнения (исчерпания - underflow) при вычитании дают неопределенный результат.

 

Интерфейс

Вспомогательные функции

В библиотеке Boost.Rational есть две вспомогательные утилиты, которые работают для любого типа I, для которого определены следующие операции: =, +=, *=, /=, %, <, и нулевая величина получается как I(0).

gcd(n, m) Наибольший общий делитель величин n и m
lcm(n, m) Наименьший общий множитель величин n и m

Замечание: В будущем эти функции могут быть перемещены в отдельную библиотеку в составе Boost C++.

Конструкторы

Рациональные числа могут быть созданы из пары (числитель, знаменатель) целых чисел, или одного числа. Также имеется конструктор по умолчанию, который инициализирует рациональное число нулевым значением.

Это подразумевает, что следующие выражения корректны:

    I n, d;
    rational<I> zero;
    rational<I> r1(n);
    rational<I> r2(n, d);

Одноаргументный конструктор не объявлен как explicit, поэтому есть неявное преобразование из используемого целого типа в рациональное число.

Арифметические операторы

Все стандартные числовые операторы определены для класса rational, включая:

    +    +=
    -    -=
    *    *=
    /    /=
    ++   --    (как префиксная так постфиксная формы)
    ==   !=
    <    >
    <=   >=

Ввод и вывод

Определены операторы ввода и вывода << и >>. Внешнее представление рационального числа это два целых, разделенных символом дроби (/). На входе формат должен быть такой: два целых числа, разделенных символом / без пробелов. Внешнее представление целых чисел определяется используемым целым типом.

Присваивание по месту

Для любого объекта типа rational<I> r, метод  r.assign(n, m) работает эквивалентно выражению r = rational<I>(n, m); без создания временного объекта. Хотя это не столь важно для рациональным чисел, использующих встроенные целые типы, для рациональных чисел с использованием классов целых чисел с неограниченной точность это может дать весомый выигрыш.

Преобразования

Неявных преобразований из рациональных чисел в любой другой тип нет. Однако, есть функция явного преобразования типа rational_cast<T>(r). Она может быть использована так:

    rational r(22,7);
    double nearly_pi = boost::rational_cast<double>(r);

Результаты работы функции rational_cast<T> неопределены, если числитель или знаменатель исходного рационального числа не могут быть безопасно преобразованы в соответствующий тип с плавающей точкой, или если частное от деления числителя на знаменатель не может быть вычислено корректно. По сути, все необходимые преобразования должны сохранять исходные значения преобразуемых величин, и все операции должны вести себя "разумно". Если эти ограничения нельзя соблюсти, то необходимо создавать отдельную процедуру для преобразования типов.

Замечание о реализации:

Реализация функции rational_cast такая:

    template <typename Float, typename Int>
    Float rational_cast(const rational<Int>& src)
    {
     return static_cast<Float>(src.numerator()) / src.denominator();
    }

Однако пользовательский код не должен полагаться на данную реализацию.

Числитель и знаменатель

Наконец, доступ к двум частям - числителю и знаменателю - возможен с помощью методов numerator() и denominator() соответственно.

Эти функции позволяют пользовательскому коду реализовать необходимую дополнительную функциональность. В частности, следует заметить, что могут быть случаи, когда ранее описанная функция rational_cast неприемлема - в частности в ситуациях, когда рациональные числа используют целый тип с неограниченной точностью. В этом случае специально написанная пользовательская процедура преобразования в число с плавающей точкой будет более предпочтительной.

Эффективность

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

Не делалось никаких попыток детально разобраться с гарантиями эффективности для операций, выполняющихся для класса rational. Такие гарантии могут быть обеспечены (так же, как это сделано для многих классов стандартной библиотеки), и это имело бы большое значение для пользователей библиотеки Boost.Rational. Вместо этого данная секция содержит общее обсуждение характеристик эффективности класса rational.

Далее следует список фундаментальных операций, реализованных в хидере <boost/rational.hpp> и неформальное описание их характеристик эффективности. Обратите внимание, что эти описания основаны на текущей реализации, и как таковые могут изменяться.

 

Обратите внимание, что неявно предполагается, что операции с типом IntType имеют "обычные" характеристики эффективности - особенно, что дорогими операциями являются умножение, деление и взятие модуля, тогда как сложение и вычитание значительно дешевле. Предполагается, что создание (из целочисленных литералов 0 и 1, и создание копированием) и присваивание относительно дешевы, хотя необходимо предпринять некоторые усилия для устранения избыточных созданий и копирований. Также предполагается, что сравнение (в частности с нулем) дешево.

Целые типы, которые не удовлетворяют этим предположениям, не могут быть эффективными в качестве используемого целого типа для класса rational. Вероятно, в этом случае эффективность будет значительно неоптимальна.

Выражения

Рациональные числа не могут иметь знаменатель 0 (данная библиотека не имеет представления для бесконечности или NaN). Если при работе с рациональным числом возникает нулевой знаменатель, генерируется исключение boost::bad_rational (подкласс std::domain_error). Это должно случаться только в случае, если пользователь пытается создать рациональное число с нулевым знаменателем, или разделить рациональное число на 0.

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

Внутренне представление

Замечание: Эти сведения даются только для информации. Не следует писать программы в расчете на детали такой реализации класса rational.

Рациональные числа хранятся как пара (числитель, знаменатель) целых чисел (чей тип специфицирован как параметр шаблона для типа rational). Рациональные числа всегда хранятся в полностью нормализованном виде (то есть gcd(numerator,denominator) = 1, и знаменатель всегда положительный).

 

Замечания о дизайне

Минимальная реализация

Класс рациональных чисел разработан в соответствии с основами. Реализованы минимально необходимые для числового типа операции, вместе с методами доступа к числителю и знаменателю - методы numerator() и denominator(). С такими строительными кирпичиками можно написать любую дополнительную функциональность.

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

Целые числа с ограниченным диапазоном

Класс рациональных чисел спроектирован в расчете на использование класса целых чисел неограниченной точности. С таким классом, рациональные числа всегда точны, не возникает проблем с потерей точности, переполнениями или исчерпаниями.

К несчастью, стандарт C++ не описывает такой класс (так же как и BOOST в настоящее время). Поэтому по всей вероятности класс rational во многих случаях будет использоваться с целыми типами ограниченной точности, таким как встроенный тип int.

Будучи использован с целым типом ограниченной точности, класс rational страдает от тех же проблем с точностью, что и типы с плавающей точкой. Хотя такие проблемы не должны оказывать большое влияние в простых случаях использования, пользователи не должны забывать об их существовании.

В качестве иллюстрации проблем, возникающих из-за ограниченной точности целых типов, рассмотрим случай, когда тип C++ int является 32-битовым знаковым. В этом случае, наименьшее представимое положительное рациональное число rational<int> равно 1/0x7FFFFFFF. Другими словами, "гранулярность" представления чисел классом rational<int> возле нуля приблизительно равно 4.66e-10. На другом конце представимого диапазона, наибольшее представимое рациональное число rational<int> равно 0x7FFFFFFF/1, и следующее меньшее представимое число rational<int> равно 0x7FFFFFFE/1. Таким образом, на этом конце диапазона представимых значений гранулярность равна 1. Такой тип неравномерной гранулярности типичен для представления чисел с плавающей точкой. Однако это не является естественным при работе с рациональными числами.

Пользователь должен проявлять осторожность при использовании класса rational  с целыми типами ограниченной точности.

Преобразование из числа с плавающей точкой

Библиотека Boost.Rational не содержит функции преобразования из плавающей точки в рациональное число. Было получено несколько запросов на включение в библиотеку соответствующей функции, но в результате интенсивного обсуждения среди сообщества BOOST привели к заключению, что не существует лучшего решения данной задачи. Так как ничто не мешает пользователю написать свой собственный код для выполнения такого преобразования, было решено не использовать какой-либо алгоритм в качестве "стандарта".

Ключевым моментом в функции преобразования из плавающего типа является вопрос, как контролировать потерю точности, которая сопряжена с операциями с плавающей точкой. Рассмотрим следующий пример для более конкретного обсуждения:

    // These two values could in practice be obtained from user input,
    // or from some form of measuring instrument.
    double x = 1.0;
    double y = 3.0;

    double z = x/y;

    rational<I> r = rational_from_double(z);

Фундаментальный вопрос таков: каким должно быть рациональное число r? Наивный ответ - r должно быть равно 1/3.Однако этот ответ игнорирует множество проблем.

Прежде всего, z не равно в точности 1/3. Из-за ограниченной точности представления чисел с плавающей точкой, 1/3 не может быть точно представлено любым способом типом double. Должно ли рациональное число r представлять неточное значение z? И будет ли пользователь рад получить значение 33333333333333331/100000000000000000 для r?

Прежде чем разбираться с данным примером, сначала рассмотрим точность исходных величин x и y. Если они поступили от аналогового измерительного прибора, к примеру, тогда они в любом случае не являются точными. В таком случае, рациональное представление наподобие приведенного ранее дает гораздо большую точность, чем есть основания ожидать.

Все это подразумевает, что мы должны искать некоторую форму "ближайшей простой дроби". Соответствующий алгоритм существует (см. здесь), однако не все приложения хотят работать таким образом. В других случаях, главной задачей преобразования в рациональное число является получение точного представления, чтобы предотвратить потерю точности во время серии вычислений. В таком случае требуется максимально точное представление, даже если получающаяся дродь выглядит несколько "неестественным".

С такими противоречивыми требованиями очевидно не может быть единого решения, которое удовлетворит всех пользователей. Более того, используемые для преобразования алгоритмы относительно сложны и специализированы, и поэтому их лучше применять при полном понимании стоящих целей. Все эти факторы делают такую функцию преобразования неподходящей для библиотеки общего назначения, каковой является Boost.Rational.

Абсолютное значение

На первый взгляд, кажется логичным реализовать функцию abs(rational<IntType>) в терминах abs(IntType). Есть, однако, ряд вопросов, которые надо учесть.

Первый вопрос заключается в том, что для того, чтобы получить соответствующую реализацию abs(IntType) в случае пользовательского класса для IntType, определенного в пространстве имен пользователя, необходимо использовать алгоритм поискf имен в зависимости от типов аргументов (Koenig lookup). В настоящее время не все компиляторы поддерживают просмотр имен Кёнига для функций. Для таких компиляторов требуется применять неудобные обходные средства, требующие кооперации с пользователем класса rational.

Второй, и потенциально более серьезный, вопрос состоит в том, что для нестандартных встроенных целых типов (к примеру, 64-битовые целые типы вроде long long или __int64), нет гарантий, что поставщик компилятора предусмотрел версию функции abs(). Это вопрос качества реализации компилятора, но на практике поддержка поставщиками компиляторов типов вроде long long еще очень ущербна.

Вследствие таких вопросов реализация abs(rational<IntType>) в терминах abs(IntType) не кажется хорошим решением. Вместо этого используется простое решение с инлайновой реализацией функции abs():

    template <typename IntType>
    inline rational<IntType> abs(const rational<IntType>& r)
    {
        if (r.numerator() >= IntType(0))
            return r;

            return rational<IntType>(-r.numerator(), r.denominator());
    }

По тем же самым причинам везде, где требуется получить абсолютное значение объекта типа IntType, соответствующие вычисления выполняются непосредственно по месту (inline).

Ссылки

История и благодарности

В декабре 1999 я реализовал начальную версию класса rational, и опубликовал его в рассылке boost.org. Было несколько дискуссий по реализации. В частности, Andrew D. Jewell указал на важность гарантий, что риск переполнений минимизируется и реализации базовых операторов не должны вызывать переполнение. Название rational_cast было предложено Кельвином Хэнни (Kevlin Henney). Эд Брей (Ed Brey) высказал бесценные замечания, в частности по поводу некоторых достаточно глупых опечаток в оригинальном коде!

David Abrahams сделал вклад в виде замечаний по документации.

Длинная дискуссия о выгодах реализации преобразования из плавающей точки в рациональное число имела место в почтовой рассылке boost в ноябре 2000 года. Список важнейших разработчиков< принявших участие, включает Reggie Seagraves, Lutz Kettner и Daniel Frey (хотя кажется, что большинство читателей рассылки boost оказались так или иначе вовлеченными в обсуждение!). Хотя итоговым решением было не реализовать вообще функцию для такого преобразования, дискуссия была очень полезна для понимания отдельных вопросов.

Stephen Silver сделал вклад в виде ценного опыта по использованию класса rational с пользовательским классом целых чисел.

Nickolay Mladenov создал текущую реализацию operator+= и operator-=.

Дискуссия вокруг вопроса с алгоритмом просмотра Кёнига и std::swap, описанная в секции абсолютное значение, имела место в листе рассылки BOOST в январе 2001 года.

Revised  February 5, 2001

© Copyright Paul Moore 1999-2001. Permission to copy, use, modify, sell and distribute this document is granted provided this copyright notice appears in all copies. This document is provided "as is" without express or implied warranty, and with no claim as to its suitability for any purpose.

последняя правка: 08.06.2005

библиотека BOOST C++ http://www.boost.org
перевод Elijah Koziev www.solarix.ru

  © Mental Computing 2010