John Harrison - Введение в функциональное программирование (1108517), страница 30
Текст из файла (страница 30)
Этим представлениемявляются программы (или, вообще говоря, правила) вычисления требуемых чисел спроизвольной заданной разрядностью. Например, мы можем написать программу,вычисляющую для заданного n первые n знаков числа π или же рациональноечисло r такое, что |π − r| < 2−n . Независимо от того, какой из подходов был выбрандля последовательного уточнения вещественного числа, важнейшим его свойствомявляется конечность программы-представления.Такой подход особенно хорошо реализуется на языках, подобных ML, припомощи функций высших порядков. То, что мы называли выше «программой», вML-реализации становится просто функцией. Арифметические операции при этомпредставимы функциями высших порядков, которые по заданным аппроксимациям xи y конструируют аппроксимации для x + y, xy, sin(x) и т.д.
В более традиционныхязыках программирования нам пришлось бы задать конкретное представлениепрограмм, например, гёделеву нумерацию, и реализовать для него интерпретатор.49.3.1Выбор представления вещественных чиселКаждому вещественному числу x поставим в соответствие функцию fx : N →Z, которая для произвольного n ∈ N возвращает масштабированное приближенноезначение x с точностью 2−n :|fx (n) − 2n x| < 1.− x| < 21n .
ТакжеВ свою очередь, данное выражение эквивалентно | fx2(n)nвозможно непосредственное вычисление рационального приближенного значения, нодля удобства вычислений важно, чтобы знаменатели всех вычисляемых величинбыли представимы в виде степеней некоторого числа.
Подобное ограничениепозволит избежать лавинообразного роста общего знаменателя при суммировании.Явное масштабирование упрощает реализацию операций, позволяя ограничиться3Вещественное число называетсяалгебраическим, если оно является корнем полинома с целыми√коэффициентами (например, 2), в противном случае это число — трансцендентное.4Effectively, we are manipulating functions ‘in extension’ rather than ‘in intension’, i.e. not concerningourselves with their representation.1319.3. Точная арифметика вещественных чиселГлава 9.
Примерылишь целочисленной арифметикой. Выбор 2 в качестве основания произволен.Малые основания предпочтительнее тем, что позволяют подбирать подходящуюточность более гибко. Например, выбор основания 10 ведёт к тому, что дажепри необходимости небольшого увеличения точности представления мы вынужденыувеличивать её в 10 раз.9.3.2Целые числа произвольной разрядностиСтандартный целочисленный тип (int) в CAML имет довольно ограниченныйдиапазон представимых значений, поэтому нам прежде всего потребуетсявозможность оперировать целыми числами неограниченной разрядности.Программная реализация подобной арифметики не слишком сложна, но несколькоутомительна.
К счастью, версия CAML Light, установленная на Thor, уже включает всебя библиотеку быстрых алгоритмов целочисленной (на самом деле, рациональной)арифметики. Предположим, что конфигурация системы задает следующие путипоиска исполнимых файлов:PATH="$PATH: / home/ j r h 1 3 / caml / b i n "export PATHВ этом случае CAML-система с поддержкой «длинной» арифметики запускаетсякомандой:$ camllight my_little_camlПосле запуска системы используйте директиву #open для получения доступа ковсем функциям библиотеки:##open "num";;В библиотеке определяется новый тип данных num, представляющийрациональные числа произвольной разрядности, среди которых нам понадобитсялишь подмножество целых чисел.
Язык CAML не предоставляет возможностиперегрузки операций, поэтому для обозначения арифметических действий над numприходится использовать другие символы.Отметим, что числа-константы типа num должны задаваться как Int k, ане просто k. Фактически, Int является конструктором типа num и применяетсяв случае, когда число имеет прямое машинное представление. Большие числаконструируются Big_int.Унарная операция смены знака величины типа num обозначается minus_num.Ещё одна полезная унарная операция — abs_num, которая вычисляет абсолютнуювеличину аргумента, т. е. по заданному x возвращает |x|.Помимо унарных, в наше распоряжение предоставлен стандартный наборбинарных операций.
Операции целочисленного деления и вычисления остатка,обозначенные quo_num и mod_num, не являются инфиксными. В то же время,большинство прочих бинарных операций определены как инфиксные с именами,полученными добавлением символа “/” к именам аналогичных операций надтипом int. Важно помнить, что в общем случае требуется использовать =/ для132Глава 9. Примеры9.3.
Точная арифметика вещественных чиселсравнения чисел. Причина этого в том, что конструкторы типа num, как всегда,различны по определению, но могут пересекаться по интерпретации представляемыхзначений. Например, в ходе вычисления частного 230 и 2 при помощи двух доступныхопераций деления мы можем получить результаты, численно равные, но различныес точки зрения языка, поскольку в одном случае будет использован конструктор Int,а в другом — Ratio.#(Int 2 **/it : bool =#(Int 2 **/it : bool =Int 30) // Int 2 = quo_num (Int 2 **/ Int 30) (Int 2);;falseInt 30) // Int 2 =/ quo_num (Int 2 **/ Int 30) (Int 2);;trueПолный список инфиксных операций:Оператор**/*/+/-/=/<>/</<=/>/>=/Типnum ->num ->num ->num ->num ->num ->num ->num ->num ->num ->numnumnumnumnumnumnumnumnumnum->->->->->->->->->->numnumnumnumboolboolboolboolboolboolЗначениеВычисление степениУмножениеСложениеВычитаниеРавенствоНеравенствоМеньше, чемМеньше либо равноБольше, чемБольше либо равноПример использования операций:#Int 5 */ Int 14;;it : num = Int 70#Int 2 **/ Int 30;;it : num = Big_int <abstr>#(Int 2 **/ Int 30) // Int 2;;it : num = Ratio <abstr>#quo_num (Int 2 **/ Int 30) (Int 2);;it : num = Int 536870912Отметим, что числа типа num по умолчанию не выводятся.
Однако, мы всегдаможем преобразовать их в строки при помощи функции string_of_num.#string_of_num(Int 2 ** Int 150);;- : string = "1427247692705959881058285969449495136382746624"Аналогично делается и обратное преобразование, реализуемое функцией с вполнеестественным именем num_of_string.9.3.3Основные операцииНапомним, что для вещественных чисел нами было выбрано представление в видефункций Z → Z. Реализация на языке ML в действительности будет использовать int-> num, поскольку диапазона значений встроенного целочисленного типа вполне1339.3. Точная арифметика вещественных чиселГлава 9. Примерыдостаточно для задания требуемой разрядности.
Определим некоторые базовыеоперации над вещественными числами. Наиболее фундаментальная операция, скоторой мы начнём, ставит в соответствие заданному целому вещественное число.Её реализация проста:#let real_of_int k n = (Int 2 **/ Int n) */ Int k;;real_of_int : int -> int -> num = <fun>#real_of_int 23;;- : int -> num = <fun>Очевидно, что для произвольного k справедлив критерий аппроксимации:|fk (n) − 2n k| = |2n k − 2n k| = 0 < 1Определим первую нетривиальную операцию — смену знака.l e t r ea l_ n e g f n = minus_num ( f n ) ; ;Компилятор для этой функции выводит более общий тип, чем требуется, но этоне создаст трудностей.
Достаточно легко убедиться, что критерий аппроксимации ненарушается. Если нам известно, что для любого n выполняется|fx (n) − 2n x| < 1,то из этого следует|f−x (n) − 2n (−x)| ===<| − fx (n) − 2n (−x)|| − (fx (n) − 2n x)||fx (n) − 2n x|1Аналогично, мы можем определить вычислениевещественных чисел, используя функцию abs_num:абсолютнойвеличиныl e t r e a l _ a b s f n = abs_num ( f n ) ; ;Доказательство корректности этого определения также не представляет трудности,принимая во внимание, что ||x| − |y|| ≤ |x − y|.Перейдем к следующей задаче — сложению двух вещественных чисел.Предположим, что x и y представлены как fx и fy соответственно.
Определимсложение так:fx+y (n) = fx (n) + fy (n).Однако, такое определение не гарантирует соблюденния критерия аппроксимации:|fx+y (n) − 2n (x + y)| = |fx (n) + fy (n) − 2n (x + y)|≤ |fx (n) − 2n x| + |fy (n) − 2n y|Можно утверждать, что сумма в правой части неравенства не превышает 2, в товремя, как критерий ограничивает нас 1.
Следовательно, в данном случае нам134Глава 9. Примеры9.3. Точная арифметика вещественных чиселтребуется вычислить x и y с большей разрядностью, чем требуется от результатаоперации. Предположим, чтоfx+y (n) = (fx (n + 1) + fy (n + 1))/2.Это, в свою очередь, дает|fx+y (n) − 2n (x + y)| = |(fx (n + 1) + fy (n + 1))/2 − 2n (x + y)|≤ |fx (n + 1)/2 − 2n x| + |fy (n + 1)/2 − 2n y|11=|fx (n + 1) − 2n+1 x| + |fy (n + 1) − 2n+1 y|2211<1+ 1=122Очевидно, что такое определение достигает желаемой точности. Однако, в нёмнеявно используется операция деления вещественных чисел. Поскольку функциядолжна возвращать целочисленный результат, частное требуется округлить.
Еслимы вычислим частное при помощи quo_num, ошибка округления составит почти 1и не позволит достичь требуемой точности независимо от точности вычисленияаргументов. В то же время, затратив чуть больше усилий, мы можем определитьфункцию деления, которая всегда будет возвращать целое число, ближайшеек точному результату (или одно из двух ближайших, если расстояние до нихоказывается одинаковым), так что ошибка округления никогда не превысит 21 .Такая функция может быть реализована в целочисленной арифметике, но будетпроще всего воспользоваться операцией деления рациональных чисел с последующимокруглением частного к ближайшему целому, поскольку для этих действий ужеопределены встроенные функции:#let ndiv x y = round_num(x // y);;ndiv : num -> num -> num = <fun>##infix "ndiv";;#(Int 23) ndiv (Int 5);;- : num = Int 5#(Int 22) ndiv (Int 5);;- : num = Int 4#(Int(-11)) ndiv (Int 4);;- : num = Int -3#(Int(-9)) ndiv (Int 4);;- : num = Int -2Если мы определим операцию сложения с учётом сказанного выше,fx+y (n) = (fx (n + 2) + fy (n + 2)) ndiv 4,всё будет работать, как требуется:|fx+y (n) − 2n (x + y)| = |((fx (n + 2) + fy (n + 2)) ndiv 4) − 2n (x + y)|1≤+ |(fx (n + 2) + fy (n + 2))/4 − 2n (x + y)|21 1=+ |(fx (n + 2) + fy (n + 2)) − 2n+2 (x + y)|2 41359.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
