Номер (часть 1)
Когда я только начинал заниматься программированием (конец 60-х), я задавался вопросом, почему научные/математические вычисления так часто приводят к ошибкам. В те дни у нас не было чисел с двойной точностью, поэтому фактических ошибок могло быть очень много. С другой стороны, мы смогли отправить людей на Луну, поэтому очевидно, что некоторые люди знали, как решить эту проблему. Но я не знал никакого общего способа даже отслеживать возможные ошибки в числовых вычислениях. Казалось, что чего-то не хватает. Я решил, что рано или поздно попытаюсь решить эту проблему. Примерно в 2002 году я начал работу над набором библиотек Java для отслеживания ошибок и модулей. Но в Java было достаточно проблем и ограничений, поэтому, хотя она работала довольно хорошо, я перестал пытаться ее улучшить.
Когда я впервые услышал о Scala, мне показалось, что я смогу исправить некоторые из этих проблем с Java, учитывая улучшенную систему типов. И это правда. Итак, эта статья (часть 1) посвящена нечеткости числа. Как сделать тип нечетким? Итак, Fuzzy[X] — это трейт, который придает нечеткость типу X. Поскольку это класс типов, нам не нужно владеть X или даже иметь его источник где-то локально. Это одна из самых важных функций Scala, позволяющая делать подобные вещи.
Итак, как насчет примера? Допустим, есть класс case с именем Color. Вы не сами это написали, но выглядит это так:
case class Color(r: Short, g: Short, b: Short) { def difference(x: Color): Color = Color(math.abs(r - x.r), math.abs(g - x.g), math.abs(b - x.b)) def whiteness: Double = math.sqrt(r * r + g * g + b * b) / 255 }
Мы можем увидеть, насколько близки два цвета, взяв их разницу, а затем получив белизну результата. Если он равен нулю, то наши два цвета одинаковы. Но что, если мы не можем воспринимать даже небольшие различия в цвете? Добавим размытости. Но сначала нам лучше определить нашу черту Fuzzy:
/** * Type class which adds fuzzy behavior to a type X. * * @tparam X the type to be made fuzzy. */ trait Fuzzy[X] { /** * Method to determine if x1 and x2 can be considered the same with a probability of p. * * @param p a probability between 0 and 1 -- 0 would always result in true; 1 will result in false unless x1 actually is x2. * @param x1 a value of X. * @param x2 a value of X. * @return true if x1 and x2 are considered equal with probability p. */ def same(p: Double)(x1: X, x2: X): Boolean }
Как видите, здесь действительно только один метод. Он называется same и принимает два набора параметров: p (Double, представляющий вероятность) и пару X. с. Полученное логическое значение указывает, следует ли считать x1 и x2 одним и тем же. Вот и все, что есть в этом, самом общем, случае. Мы найдем нечеткость более полезной, когда у нас будут числовые значения, но мы вернемся к этому позже.
Теперь давайте посмотрим, как мы можем добавить размытия в Color:
object Color { def apply(r: Int, g: Int, b: Int): Color = Color(r.toShort, g.toShort, b.toShort) trait FuzzyColor extends Fuzzy[Color] { def same(p: Double)(x1: Color, x2: Color): Boolean = -math.log(x1.difference(x2).whiteness) / 3 > p } implicit object FuzzyColor extends FuzzyColor }
Как видите, мы несколько произвольно определили два цвета как одинаковые, если одна треть (отрицательного) логарифма белизны разницы больше, чем p. Используя это определение, Color(255,255,255) и Color(242,242,242) считаются одним и тем же с 80% достоверностью. Если нам нужна 100% достоверность (p = 1), то одинаковыми считаются только идентичные цвета. Для достоверности 0% все цвета одинаковы. Вот и весь этот довольно искусственный пример. Теперь давайте посмотрим, как это может работать, чтобы считать числа.
Наряду с номинальным значением числа мы также храним некоторую (необязательную) нечеткость. Когда нет нечеткости, наше число точное. Два точных числа могут считаться равными только в том случае, если они действительно равны. А вот нечеткие числа могут быть «равны» по разности: как номинальному значению, так и функции распределения вероятностей (PDF).
Не углубляясь в математику этих PDF, отметим, что если номинальное значение находится в пределах PDF, то есть некоторая вероятность того, что значение является истинным значением. Предположим, что PDF является ступенчатой функцией. Он начинается (для очень отрицательных значений) с нуля; когда она достигает определенного значения, плотность вероятности становится равной 1/a (где a — это диапазон возможных значений, также известный как «допуск»); это продолжается на расстоянии a по оси значений; после этого (для более положительных значений) снова с нулевой вероятностью. Я называю этот PDF-файл «коробкой». Это гипотетический pdf, конечно. Но он может возникнуть в результате процесса, например, при изготовлении стальных гвоздей произвольной длины (с равномерным распределением). Гвозди, которые не соответствуют допустимым требованиям (слишком короткие или слишком длинные), выбрасываются и переплавляются. Появляющиеся гвозди будут иметь pdf их длины, как у коробки, описанной выше.
Когда два нечетких числа (x +- a и y +- b), оба с прямоугольными PDF-файлами, вычитаются (или складываются), результирующий PDF-файл выглядит примерно так: следующий:
Несколько произвольно Number не использует такие трапециевидные PDF. Вместо этого, если мы добавляем два числа, мы аппроксимируем их PDF как гауссовские («нормальные») распределения. Это потому, что такие распределения очень легко комбинировать: среднее — это сумма (или разность, если вычесть) средних; дисперсия представляет собой сумму дисперсий.
С другой стороны, если мы умножим (или разделим) два таких числа с нечеткостью прямоугольного типа, результат будет иметь прямоугольное распределение (с шириной, заданной суммой ширин входных полей), при условии, что PDF были относительно номинальные значения, а не абсолютные. Это следует из простого исчисления.
Итак, как видите, у нас есть четыре типа числовой нечеткости: абсолютная или относительная; коробка или гауссова. Вообще говоря, как только мы объединим нечеткие числа вместе, их PDF-файлы обычно будут иметь форму Гаусса. Кроме того, физические константы также начинаются с гауссовой функции плотности вероятности, например, гравитационная постоянная G:
Круглые скобки вокруг «15» подразумевают гауссово распределение в последних двух десятичных разрядах со средним значением 30 и стандартным отклонением 15. Ниже я опишу, как вводить нечеткие числа. Ряд констант, включая G, определены в типе Constants. Он определяется следующим образом: Number(«6.67430(15)E-11»), т. е. с использованием одного из методов apply.
Для диадических операций (особенно умножения и возведения в степень) наиболее удобны относительные PDF. Для монадических операций (например, натурального логарифма) или сложения более удобны абсолютные PDF-файлы. Но, конечно же, все преобразования и свертки выполняются автоматически кодом Number.
Итак, как нам реализовать описанный выше тот же метод? Мы берем разницу двух номинальных значений и определяем, можно ли считать это число (x) равным нулю, учитывая результирующую плотность вероятности. Для PDF-файла прямоугольного типа (который обычно получается только при сравнении нечеткого числа с точным числом) мы по существу игнорируем значение p (если оно не равно 0 или 1) и просто возвращаем true ( т. е. то же самое), если число x находится в поле. Для гауссовского распределения мы используем функцию «обратной erf» (в которую мы передаем дополнительную вероятность, т. е. 1-p). Это эффективно преобразует гауссовский PDF в поле.
Альтернативный взгляд на этот определитель состоит в том, что p соответствует вероятности того, что ноль принадлежит нечеткому множеству (как в Нечеткой логике Лотфи Заде), которое включает все возможные нечеткие числа.
Как я расскажу во второй части, номинальное значение числа может быть либо целым числом, либо рациональным числом (основанным на делении BigInt на BigInt), либо двойным числом. значение точности. Если нам нужно преобразовать целое или рациональное число в двойное число, мы добавляем небольшое количество (относительной) нечеткости: (1.6E-16) к любым существующим нечетким числам.
Итак, как нам справиться с введением нечеткости в наши расчеты? Ну, во-первых, мы не добавляем произвольно нечёткость. Число, такое как фи, золотое сечение, определяется следующим образом: Number(«1,618033988749894»). Результат имеет абсолютную нечеткость формы Box со значением 0,5E-15. Это следует из 15 знаков после запятой, данных в определении. По соглашению строка только с одним или двумя десятичными знаками считается точной (как если бы это были доллары и центы). Однако вы можете отменить это соглашение, просто добавив после строки «*» или «…». Кроме того, если у вас есть десятичное представление числа, которое на самом деле является точным, то представьте его как целое число с отрицательной степенью (по крайней мере, на данный момент мы должны предварять «E» десятичной точкой). Или, проще говоря, просто добавьте «00» в конец строки.
Вы можете сделать нечеткость в форме прямоугольника явной, добавив к десятичной строке суффикс «[x]» или «[xx]», где x или xx обозначает максимально возможное отклонение. в любом одном направлении. Точно так же для гауссовской нечеткости (как мы показали с константой G выше) мы добавляем к десятичной строке суффикс «(x)» или «(xx)». В этом случае x или xx представляют собой стандартные отклонения возможных различий в указанных цифрах. Между прочим, нечеткость должна предшествовать любому показателю.
Как я объясню в следующий раз, числа π и e точны. Так, например, если вы вычислите atan(tan(π)), результатом будет ровно π. Точно так же, если вы вычислите e^(ln(e)), результатом будет ровно e. Однако более общие иррациональные числа, такие как √2, не могут быть представлены точно. Но, как упоминалось в моей статье Composable Matchers, если вы оцениваете √2 √2 или что-то еще, вы получите ровно 2, но это достигается с помощью механизма, называемого ExpressionMatchers. который не работает на низком уровне чисел, описанных здесь. Об этом позже, во второй части.
Итак, в чем смысл всего этого? На самом простом уровне предположим, что у вас есть маятник, такой как маятник Фуко. Он очень высокий, и было бы крайне неудобно измерять его длину. Тем не менее, вы можете довольно легко измерить период t с помощью секундомера. Формула для определения длины l маятника:
где g — ускорение свободного падения в точке, где находится маятник. С точностью до двух знаков после запятой g = 9,81 м/с.
В первом сценарии у нас есть точный секундомер, но мы просто игнорируем сотые доли секунды. Наш код выглядит так:
import com.phasmidsoftware.number.core.{Expression, Number} import Number._ val g = Number("9.81*") val t = Number("16.5*") val length: Number = g * ((t / twoPi) ^ 2)
Нам нужно вводить числа в виде строк со звездочкой, потому что они имеют один и два десятичных знака, иначе они были бы интерпретированы как точные. Результат, который мы получаем для длины, равен 67,65[44]. Это означает, что мы почти уверены в первых двух значащих цифрах (67), но фактическое значение может быть где-то между 67,21 и 68,09. Давайте посмотрим, как мы можем рассчитать вклад неопределенностей g и t.
Во-первых, давайте посмотрим на общую формулу для границ погрешности умножения двух неопределенных величин, где f = x y (это следует из производной от f):
Если мы разделим обе части на f, мы получим:
Это означает, что мы просто суммируем границы относительной ошибки x и y, чтобы получить границу относительной ошибки f. В нашем примере выше у нас есть три члена: g и t (дважды, так как оно возведено в квадрат). Относительная ошибка g составляет около 0,0005, а относительная ошибка t — около 0,003. Таким образом, относительная ошибка l составляет приблизительно 0,0065.
Несколько более реалистична ситуация, когда мы измеряем колебания маятника примерно 1000 раз и вычисляем среднее значение и стандартное отклонение. Допустим, среднее значение равно 16,487, а стандартное отклонение — 0,041 секунды. Запишем это количество как 16,487(41). Результат, который мы получаем сейчас, равен 67,54(35), что означает, что у нас есть 68-процентная уверенность в том, что истинная длина находится между 67,19 и 67,89 метрами.
Пакет Number постоянно развивается. Здесь описана версия 1.0.10. Вы можете найти его на https://github.com/rchillyard/Number. Во второй части я опишу механизм ленивых вычислений, предназначенный для того, чтобы по возможности избежать ненужной потери точности, например, в случае выражения (√3+1)(√3–1), которое, как мы знаем, имеют точное значение 2.