Типы чисел

Числа имеют свою иерархию:

number 
    real 
        rational 
            integer 
                fixnum
                bignum
            ratio
        float
            short-float
            single-float
            double-float
            long-float
    complex

как видим, эта система древовидна - число принадлежит какому-либо типу, его супер-типу, и так вплоть до number, которому принадлежат все числа.

fixnum представляют из себя числа фиксированной точности - например 32-битные, при превышении по модулю некоторого предела (зависящего от платформы) они переходят в bignum, то есть числа в длинной арифметике. Вне зависимости от платформы CL гарантирует, что числа в диапазоне [-2^15, 2^15 - 1] являются fixnum числами. Размер bignum зависит только от количества памяти, выделяемой ОС лисп-среде.

ratio - это рациональные числа с положительным целым знаменателем и целым числителем (типов integer). для их записи можно использовать инфиксную форму: 1/2, 3/4. С точки зрения Лиспа 2/4 равно 1/2, и такое сокращение производится немедленно. Рациональные числа также получаются при делении целых:

1/2
;-> 1/2
(/ 1 2)
;-> 1/2
(/ 4 8)
;-> 1/2
(* (/ 4 8) 2)
;-> 1

Дробные числа бывают 4 видов точности - short-float, single-float, double-float и long-float. По умолчанию используются double-float числа. Эти числа возникают при использовании констант дробного типа, например таких как встроенная константа pi, и как результат некоторых функций.

(/ 1 2.0)
;-> 0.5
(* 2 pi)
;-> 6.283185307179586477L0

1e+1
;-> 10.0

кроме записи в десятичной записи, дробные числа поддерживают запись в научной форме, например - 2e+5 это не целое число 2^5, а дробное.

Наконец комплексные числа, complex, ведут себя как пары чисел типа real. Для их записи используется нотация #C(real-part imag-part).

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

(typep 5 'number)
;-> T
(typep 5 'fixnum)
;-> T
(typep 5 'bignum)
;-> NIL
(typep (expt 1000 1000) 'bignum)
;-> T
(type-of 3.14159)
;-> DOUBLE-FLOAT
(subtypep 'rational 'real)
;-> T

Сравнение чисел

Существует достаточно предикатов для сравнения чисел.

• = возвращает истину, если все его аргументы (от 1 и более, для 1 аргумента возвращает T) равны, иначе дает ложь.
• /= возвращает истину, если все его аргументы (от 1 и более, для 1 аргумента возвращает T) не равны, иначе дает ложь. Выражение (/= a b c) эквивалентно (not (= a b c))
• Четыре предиката <, <=, >, >= для сравнения чисел на меньше, меньше-или-равно, больше, больше-или-равно соответственно. Аналогично - аргументов может быть от 1 и более. Например: (< a b c d) эквивалентно неравенству a < b < c < d (которые позволены, например, в Python).
• Для сравнения чисел с нулём можно использовать специальные предикаты - minusp, zerop, plusp - они определены только для одно аргумента, и их назначение очевидно.
• Для определения чётности/нечётности чисела предназначены предикаты evenp и oddp соответственно.
• Наконец есть ряд предикатов для определения типа числа. Т.к. типизация динамическая, переменная может менять свой тип и проконтролировать его можно с помощью таких предикатов. numberp, realp, rationalp, floatp, integerp, complexp, random-state-p - по одной функции на каждый тип. О проверке с помощью typep и type-of уже писалось выше.

Приведение типов

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

• floor, ceiling, truncate, round - принимают один или два аргумента - число и делитель (при отсутствии считается единицей). возвращает целую часть по делителю и остаток по делителю, остаток = число - целая-часть * делитель. Соответственно при единичном делителе получается просто целая и дробная части. Несколько примеров должны прояснить разницу между этими функциями:

; floor возвращает ближайшее целое "снизу"
(floor 5.1) => 5
(floor 5.9) => 5
(floor -5.1) => -6
(floor -5.9) => -6
; ceiling возвращает ближайшее целое "сверху"
(ceiling 5.1) => 6
(ceiling 5.9) => 6
(ceiling -5.1) => -5
(ceiling -5.9) => -5
; truncate возвращает ближайшее целое "в сторону нуля"
(truncate 5.1) => 5
(truncate 5.9) => 5
(truncate -5.1) => -5
(truncate -5.9) => -5
; round возвращает ближайшее целое
(round 5.1) => 5
(round 5.9) => 6
(round -5.1) => -5
(round -5.9) => -6

• ffloor, fceiling, ftruncate, fround - то же самое, но остаток возвращается такой же точности, как и число.
• (mod a b) = второе значение (floor a b).
• (rem a b) = второе значение (truncate a b).
• float - для образования дробного числа. Например для того, чтобы не тратить время на операции с рациональными, которые более медленны.
• rational и rationalize - для приведения дробного к рациональному.
• numerator - возвращает числитель рационального числа.
• denominator - возвращает знаменатель рационального числа.
• complex - для образования комплексного числа их действительной и мнимой частей.
• realpart - возвращает действительную часть комплексного числа.
• imagpart - возвращает мнимую часть комплексного числа.

Округление дробных чисел

Функции для округления дробных чисел до определённого количества знаков не входят в стандарт, но могут быть легко реализованы:

(defun round-to-ratio (number precision &optional (round-function #'round))
  "Округляет число NUMBER до количества знаков PRECISION, если PRECISION
отрицательно, то происходит потеря разрядов. Возвращает рациональное число,
ROUND-FUNCTION - округляющая функция, например:
  #'floor
  #'ceil
  #'truncate
  #'round (по-умолчанию)."
  (let ((div (expt 10 precision)))
    (/ (funcall round-function (* number div)) div)))

(defun round-to-float (number precision &optional (round-function #'round))
  "Округляет число NUMBER до количества знаков PRECISION, если PRECISION
отрицательно, то происходит потеря разрядов. Возвращает дробное число.
ROUND-FUNCTION - округляющая функция, например:
  #'floor
  #'ceil
  #'truncate
  #'round (по-умолчанию)."
  (float (round-to-ratio number precision round-function)))

;; (round-to-ratio 1234.4567 2)
;; 61723/50

;; (round-to-float 1234.4567 2)
;; 1234.46

Встроенные математические функции

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

Итак, функции, работающие со всеми числовыми типами:

• + и * используют от нуля (в этом случае (+) дает 0, а (*) дает 1) и более аргументов.
• - и / определены либо для 1, либо для двух аргументов. - c одним аргументом возвращает противоположное по знаку значение, а / - обратное для числа. Для функции / - если оба аргумента были целыми, то результат рациональный, а если хоть один дробный - результат тоже дробный.
• (exp x) - экспонента числа x = e^x.
• (expt x a) - число x в степени a = x^a.
• sin, cos, tan, acos, asin, atan - ряд тригонометрических функций. Аргумент задаётся в радианах.
• sinh, cosh, tanh, acosh, asinh, atanh - гиперболические функции.
• (sqrt x) - квадратный корень из числа x.
• (isqrt x) - возвращает целую часть квадратного корня.
• (log x) - натуральный логарифм числа x = ln(x)
• (log x a) - логарифм числа x по основанию a.
• (conjugate x) - возвращает сопряженное комплексное число (a-ib для a+ib). Для действительных чисел сопряженные совпадают.
• (abs x) - модуль числа.
• (phase x) - фаза комплексного числа.
• (signum x) - число, имеющее ту же фазу, что и x, но единичный модуль.
• (cis phi) - вычисляет выражение exp(i * phi), значение phi задаётся в радианах.

Следующие функции определены только для некоторых типов:

• max и min принимают от 1 и более аргументов, первая возвращает максимальное, а вторая - минимальное значение. Не определены для комплексных чисел.
• gcd - наибольший общий делитель (НОД) чисел, принимает от 0 и более аргументов.
• lcm - наименьшее общее кратное (НОК) чисел, принимает от 0 и более аргументов.
• 1+ и 1- это инкрементор и декриментор - соответственно увеличивают и уменьшают целое значение на единицу. incf и decf ведут себя также, но имеют побочный эффект, и они более общие.
• pi - константа "пи".

Случайные числа

• (random n) - возвратит случайное число от 0 до n.
• *random-state* - текущее состояние генератора случайных чисел.
• make-random-state - функция для изменения состояния генератора.
• (random n random-state) - возвратит случайное число от 0 до n, используя состояние генератора, определённое в random-state.

Булевые функции

• and - выполняет логическое умножение аргументов (для целых чисел возвращает максимум).
• xor - выполняет логическое сложение аргументов.
• or - (or x y) === (xor (and x y) (xor x y)) (для целых чисел возвращает минимум).
• not - обратное логическое значение : T => NIL, NIL => T.

Логические функции для работы с битами чисел

• boole
• lognot
• logeqv
• logand
• logandc1
• logandc2
• lognand
• logxor
• logior
• logorc1
• logorc2
• lognor
• logbitp
• logtest
• logcount
• ash
• mask-field

Работа с битами чисел

Для доступа к битам можно использовать функции:

• integer-length
• ldb-test
• ldb
• dpb
• byte
• byte-size
• byte-spec
• byte-position
• short-floatsingle-float
• double-float
• long-float

Границы точности для чисел

На разных платформах они будут разные. Этой цели служит ряд платформо-определяющих фунций

• decode-float
• scale-float
• float-radix
• float-digits
• float-precision
• upgraded-complex-part-type

Пример : корень функции на комплексной плоскости

Задача - определена функция f на комплексной плоскости. Известно, что на квадрате S имеется только один корень. Найти его.

Решение - воспользуемся теоремой вычетов для функции 1 / F (X). Сначала нужно написать функцию для интеграла по соронам квадрата.

(defun integrate-square-path (f start length precision)
  "f - функция для интегрирования.
   Start - комплексное число, определяющее нижний левый угол квадрата.
   Length - сторона квадрата.
   Precision - точность."
  (let* ((sum 0)
         (n (ceiling (/ length precision)))
         (step (float (/ length n)))
         (j 0)
         (side 0)
         (d (complex step 0))
         (cur start))
    (loop (incf sum (* (funcall f cur) d))
          (incf cur d)
          (incf j)
          (when (= j n)
            (setf j 0)  
            (incf side)
            (setf d (case side
                      (1 (complex 0 step))
                      (2 (complex (- step) 0))
                      (3 (complex 0 (- step)))
                      (4 (return sum))))))))

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

Теперь можно проверить:

(integrate-square-path (lambda (x) (/ 1 x)) #C(-1 -1) 2 0.001)
;-> #C(-0.0019999794 6.2832413)

Вроде верно, т.е. 2*pi*i.

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

(defun pole-p (f start length precision)
  "Проверка наличия полюса у функции f в квадрате S."
  (when (> (abs (integrate-square-path f start length precision)) (sqrt precision))
    (+ start (/ (complex length length) 2))))

Этот предикат может установить наличие полюса, но ничего не говорит о его местонахождении. Чтобы найти координаты полюса, воспользуемся следующим способом - разделим исходный квадрат на 4 части и применим предикат к каждому. Т.к. полюс один - только один квадрат удовлетворит предикату, далее повторим процедуру рекурсивно, пока искомая точка не будет найдена с нужной точностью.

(defun find-pole (f start length precision)
  "нахождение полюса функции f на квадрате S."
  (when (> (* precision 10) length) 
    (return-from find-pole (pole-p f start length precision)))
  (let ((h (float (/ length 2))))
    (flet ((check-pole (start)
             (when (pole-p f start h precision)
               (find-pole f start h precision))))
      (or (check-pole start)
          (check-pole (+ start (complex 0 h)))
          (check-pole (+ start (complex h 0)))
          (check-pole (+ start (complex h h)))))))

Наконец, остался последний шаг - чтобы найти корень функции f, нужно нацти полюс функции 1/f (это, опять же, следствие теоремы вычетов):

(defun find-root (f start length precision)
  "Находит корень функции f на квадрате S."
  (find-pole (lambda (x) (/ 1 (funcall f x))) start length precision))

Теперь посмотрим - например, f(X) = X^2+2 имеет два корня : ±sqrt(2)*i.

(find-root (lambda (x) (+ (* x x) 2)) #C(-1 0) 5 0.0001) 
;-> #C(-5.493164E-4 1.4138794)

Похоже, правильный ответ!

Библиотеки

• Maxima - свободная система компьютерной алгебры, написанная на Common Lisp.
• Mathematics @ www.cliki.net - список математических библиотек.
• math @ www.cs.cmu.edu - библиотеки clmath, matrix и др.