Числовая башня: целые, дроби, комплексные

Изучаем, почему арифметика в Lisp устроена честнее, чем в большинстве языков, и что такое числовая башня.

Числовая башня (numeric tower) — иерархия числовых типов Common Lisp: целые → рациональные → вещественные → комплексные. Каждый следующий уровень включает предыдущий, а операции автоматически выбирают подходящий тип результата, сохраняя точность там, где это возможно.

В большинстве распространённых языков числа — это компромисс с аппаратурой: целые ограничены 32 или 64 битами и молча переполняются, а дроби представлены приближённо в плавающей точке, отчего 0.1 + 0.2 внезапно не равно 0.3. Lisp исторически создавался не под аппаратуру, а под математику, и его числовая система отражает это: целые числа не переполняются, а дроби могут быть точными. Эта «числовая башня» — одна из самых приятных и недооценённых черт языка.

Целые без ограничения разрядности

В Common Lisp целые числа бывают двух видов, но граница между ними прозрачна для программиста. Fixnum — это небольшие целые, помещающиеся в машинное слово, с ними процессор работает напрямую и очень быстро. Bignum — это сколь угодно большие целые, которые при необходимости занимают столько памяти, сколько нужно. Самое важное: переход от fixnum к bignum происходит автоматически. Когда результат вычисления перестаёт помещаться в машинное слово, Lisp молча переключается на bignum, и вы просто получаете правильный ответ, а не переполнение.

Это качественно отличается от языков вроде C или Java, где целое фиксированной разрядности при переполнении «заворачивается» и даёт бессмысленный отрицательный результат. В Lisp факториал большого числа или огромная степень двойки вычисляются точно, без всяких специальных библиотек «длинной арифметики».

;; Целые не переполняются — переход к bignum автоматический:
(defun factorial (n)
  (if (<= n 1) 1 (* n (factorial (- n 1)))))

(factorial 30)
;; => 265252859812191058636308480000000   (точно, без переполнения)

(expt 2 100)
;; => 1267650600228229401496703205376     (2 в сотой степени, точно)

Рациональные числа: точные дроби

Вот черта, которой нет почти нигде в мейнстриме: Common Lisp умеет работать с точными рациональными числами — обыкновенными дробями вида «числитель/знаменатель». Когда вы делите два целых, и они не делятся нацело, Lisp не переходит к приближённой плавающей точке, а возвращает точную дробь. 1/3 — это полноценное число, а не приближение 0.333.... Дроби автоматически сокращаются, а арифметика над ними остаётся точной.

;; Деление целых даёт ТОЧНУЮ дробь, а не приближение:
(/ 1 3)            ; => 1/3        (рациональное число, не 0.333...)
(/ 6 4)            ; => 3/2        (автоматически сократилось)
(+ 1/3 1/6)        ; => 1/2        (точная арифметика дробей)
(* 2/3 3/4)        ; => 1/2

;; Сумма третей даёт ровно единицу — без накопления ошибки:
(+ 1/3 1/3 1/3)    ; => 1

Сравните это с плавающей точкой, где (+ 1/3 1/3 1/3) в приближённом виде могло бы дать что-то вроде 0.9999999. Точные дроби незаменимы там, где важна абсолютная корректность: финансовые расчёты, символьная математика, точные пропорции. Целые и рациональные вместе образуют категорию точных (exact) чисел — для них результат арифметики математически верен, без округлений.

Числа с плавающей точкой: когда нужна аппроксимация

Разумеется, не всё можно выразить дробью: корень из двойки, число пи, синус угла — иррациональны. Для них есть числа с плавающей точкой — приближённые вещественные числа, как в других языках. Они помечаются десятичной точкой (3.14) или экспонентой. Важно понимать «заразность» плавающей точки: как только в вычислении появляется хоть одно неточное число, результат становится неточным — Lisp вынужден перевести всё в плавающую точку, потому что точное число и приближённое нельзя честно смешать, сохранив точность.

;; Точка делает число неточным (float), и это "заражает" результат:
(/ 1 3)            ; => 1/3        (точная дробь)
(/ 1.0 3)          ; => 0.33333334 (float — появилась 1.0)
(+ 1/2 0.5)        ; => 1.0        (float "победил" дробь)

;; Иррациональные величины — всегда приближённые:
pi                 ; => 3.141592653589793d0
(sqrt 2)           ; => 1.4142135623730951d0

Здесь важна осознанность: если вам нужна точность — держитесь целых и дробей и не вводите случайно .0; если нужна работа с иррациональными величинами или скорость — используйте плавающую точку, понимая, что результат приближённый. Common Lisp даёт выбор, тогда как многие языки навязывают плавающую точку для любого деления.

Стоит сказать пару слов и о разновидностях плавающей точки. Стандарт предусматривает несколько форматов разной точности — короткие, одинарные, двойные и длинные, — которые задаются буквой в экспоненте: 1.5e0 — одинарной точности, 1.5d0 — двойной (отсюда суффикс d0, который вы видели у числа пи). По умолчанию SBCL читает обычные десятичные литералы как числа двойной точности, что соответствует типу double в других языках. Точные правила формата редко нужны новичку, но полезно узнавать суффикс d0 в выводе и понимать, что это просто пометка «двойная точность», а не часть значения. Когда важна предсказуемость на разных реализациях, тип литерала фиксируют явным суффиксом, чтобы программа не зависела от настроек по умолчанию.

Особо отметим коварство сравнения чисел с плавающей точкой на точное равенство. Из-за того что многие десятичные дроби не представимы в двоичной плавающей точке абсолютно точно, выражение вроде (= 0.1 (- 0.3 0.2)) вполне может вернуть ложь — накопленная погрешность делает левую и правую части чуть-чуть разными. Это не особенность Lisp, а общее свойство плавающей точки во всех языках, но в Lisp оно особенно заметно на контрасте: ведь рядом есть точные дроби, лишённые этой беды. Практическое правило — никогда не сравнивать результаты вычислений с плавающей точкой на строгое равенство, а проверять, что разность по модулю меньше малого порога; либо, если задача терпит, вести расчёты в точных рациональных числах и забыть о погрешностях вовсе.

Комплексные числа: вершина башни

На вершине башни — комплексные числа, встроенные прямо в язык, без всяких библиотек. Комплексное число записывается через #c(вещественная мнимая). Что особенно элегантно: некоторые функции возвращают комплексный результат там, где математически это правильно, — например, квадратный корень из отрицательного числа. Многие языки в этом случае выдали бы ошибку или «не-число»; Common Lisp честно возвращает комплексное число.

;; Комплексные числа встроены в язык:
#c(3 4)            ; => #C(3 4)       (3 + 4i)
(+ #c(1 2) #c(3 4)); => #C(4 6)
(* #c(0 1) #c(0 1)); => -1            (i умножить на i = -1)

;; Корень из отрицательного даёт комплексное число, а не ошибку:
(sqrt -1)          ; => #C(0.0 1.0)  (мнимая единица i)
(sqrt -4)          ; => #C(0.0 2.0)

Так замыкается иерархия: целое — частный случай рационального, рациональное и вещественное — частные случаи действительных чисел, действительное — частный случай комплексного. Любая арифметическая операция автоматически выбирает наиболее «узкий» подходящий тип результата, поднимаясь по башне ровно настолько, насколько нужно, и не выше.

Сравнение чисел: = против eql

С числами связана ещё одна тонкость, на которой спотыкаются новички, — как их правильно сравнивать. В Lisp есть несколько разных предикатов равенства, и для чисел важно выбрать верный. Функция = сравнивает числа по математическому значению, игнорируя тип: для неё 1, 1.0 и 1/1 равны, потому что обозначают одно и то же число. А вот eql сравнивает строже — учитывая и значение, и тип: для неё целое 1 и вещественное 1.0 уже не равны, потому что это числа разных типов. Это различие принципиально: для арифметических сравнений почти всегда нужен =, а eql уместен, когда тип числа важен.

;; = сравнивает по значению, игнорируя тип:
(= 1 1.0)          ; => T    (математически равны)
(= 1/2 0.5)        ; => T    (одно и то же значение)
(= 3 3 3.0 6/2)    ; => T    (принимает много аргументов)

;; eql учитывает и тип, и значение:
(eql 1 1.0)        ; => NIL  (целое и float — разные типы)
(eql 1 1)          ; => T

;; Сравнения тоже принимают любое число аргументов:
(< 1 2 3 4)        ; => T    (строго возрастает)
(<= 1 1 2 3)       ; => T    (неубывает)

Заметьте попутно, что операторы сравнения <, >, <=, >= в Lisp — это обычные функции в префиксной записи, принимающие любое число аргументов. Запись (< 1 2 3 4) проверяет, что вся цепочка строго возрастает, — лаконичная замена нескольким сравнениям. И, разумеется, как любые имена-функции, эти символы можно цитировать и передавать как данные, что мы используем в разделе про функции высшего порядка.

Как это работает под капотом

За автоматическим выбором типа стоит механизм, называемый контагией (contagion) — правилами «заражения» типов. При операции над числами разных типов Lisp приводит их к общему «наименьшему охватывающему» типу: целое и дробь дают дробь; точное и неточное дают неточное (float); вещественное и комплексное дают комплексное. Результат возвращается в самом узком типе, который его точно представляет: например, (/ 6 3) даст целое 2, а не дробь 2/1, потому что деление вышло нацело и дробь автоматически «опустилась» до целого.

На уровне реализации fixnum хранятся прямо в машинном представлении и обрабатываются быстро, а bignum, рациональные и комплексные — это полноценные объекты в куче. Поэтому за гибкость и точность приходится платить: арифметика с bignum и дробями медленнее машинной. Когда критична скорость и известно, что числа малы, программист может с помощью объявлений типов подсказать компилятору SBCL использовать быстрые машинные операции. Но по умолчанию язык выбирает корректность, а не предельную скорость, — и это сознательное решение в духе математической честности Lisp.

Частые ошибки

Первая ошибка — случайно «уронить» точность, написав десятичную точку. Стоит в выражении появиться 2.0 вместо 2, и весь результат станет приближённым float, даже если остальные числа точные. Если вам нужна точная арифметика, следите, чтобы все литералы были целыми или дробями, без лишних .0.

Вторая ошибка — ждать дробь там, где деление выходит нацело. (/ 6 3) даст целое 2, а не 2/1: Lisp всегда опускает результат до самого узкого типа. Это не баг, а корректное поведение башни, но новичка может удивить, что «деление» иногда даёт целое.

Третья ошибка — забывать о цене больших чисел и дробей. Точность не бесплатна: операции с bignum и рациональными медленнее машинных, и в горячем цикле, перемалывающем миллионы чисел, это может быть заметно. В таких местах либо используют плавающую точку осознанно, либо ограничивают значения fixnum и объявляют типы. Знать о компромиссе «точность против скорости» полезно, чтобы выбирать осознанно, а не натыкаться на замедление случайно.

Итоги

• Числовая башня Common Lisp: целые → рациональные → вещественные → комплексные; операции автоматически выбирают подходящий тип.
• Целые не переполняются — переход fixnum → bignum происходит автоматически, факториалы и степени вычисляются точно.
• Деление целых даёт точные рациональные дроби (1/3), которые сокращаются и считаются без потери точности; целые и дроби — это «точные» числа.
• Десятичная точка делает число неточным (float) и «заражает» весь результат; иррациональные величины и скорость требуют плавающей точки.
• Комплексные числа встроены в язык; корень из отрицательного честно возвращает комплексное число. Точность не бесплатна — bignum и дроби медленнее машинной арифметики.