Эта статья могла бы входить в цикл "Разрядность ЭВМ, с разных точек зрения". Но, хоть речь и будет идти о разрядности и точности чисел и вычислений, все сказанное будет верно в большей степени для математики, а не только ЭВМ. Поэтому решил не включать ее в цикл о разрядности ЭВМ.
Все началось со старой статьи
В комментариях к ней недавно разгорелась небольшая дискуссия на тему разрядности и точности вычислений. Моему оппоненту не понравились слова из статьи:
- "Цифровые вычислительные машины дискретны по самой своей природе. Какой бы высокой не была разрядность цифрового вычислителя мы всегда будем ограничены весом младшего разряда цифрового представления, которое и определяет дискретность"
Вот фрагмент его комментария:
- "- не верно, поэтому сомневаюсь в хоть каком-то знакомстве автора с вычтехникой и программированием"
Оставим в стороне хамство... Но вот его слова "НЕ ВЕРНО" о влиянии дискретности вычислений являются действительно в корне неверными! С этим и будем сегодня разбираться.
Увы, в ходе дискуссии быстро выяснилось, что оппонент рассматривает вопрос лишь с точки зрения общеприкладного программирования и в тонкостях машинных вычислений глубокими знаниями не обладает. Более того, он рассматривает машинные вычисления в отрыве от математики прикладной (точнее, арифметики). Но нам, для понимания сути рассматриваемых вопросов, понадобится еще пара фрагментов его комментариев:
- "про арифметику произвольной точности не слышали, да? готовым библиотекам уже хз сколько лет, но до сих пор слышу эти домыслы об ограничениях разрядностью. и, что примечательно, слышу в основном от тех кто застыл в образовании в 80-х годах прошлого века"
- "про накопление ошибок забудьте. как по вашему считают число Пи с точностью до миллионов знаков? на миллионобитной машине?"
Вот теперь у нас есть все необходимое и мы можем начать достаточно подробное, но без излишнего усложнения, рассмотрение всех вопросов.
Увы, Дзен становится все более неудобным для технический и научных статей...
И да, я знаю, что статья будет очень скучной и занудной. И что все это вообще "никому не нужно", тоже. Тем не менее, это фундаментальные тонкости любого практического вычисления.
Небольшой исторический экскурс
Нам необходима небольшая историческая ретроспектива без которой будет сложнее понять суть вопроса...
Само понятие чисел зародилось в глубокой древности, когда возникла необходимость оценивать количество различных предметов. Числа были целыми, а для их "записи" применялись визуальные и голосовые аналогии. Количество не загнутых пальцев на руке, количество камешков, и т.д. Дробные числа не были нужны. Даже дележ добытой на охоте пищи не требовал дробей, так как можно было использовать количество отдельных частей туши. Мир чисел древнего мира был дискретным.
С развитием цивилизации потребовались числа, которыми можно обозначать части целого - дроби. Визуально выполнить деление, например, выпеченного хлеба на несколько частей было не сложно. Вот пример того, как это делалось в Древнем Риме
Хлеб разделен на 8 частей. Конечно была и система записи дробных чисел, но дроби в Древнем Риме были двенадцатиричные.
Возникает естественный вопрос - на какое максимальное количество частей можно разделить целое? Так возникло представление о мельчайшей частице всего сущего, которую еще нельзя разделить на более мелкие части. Такую частицу назвали атомом - неделимым. Это не был атом в сегодняшнем представлении, просто то, что уже нельзя разделить.
Для нас важно, что ничто материальное нельзя делить бесконечно. Мир остался дискретным и для записи любой дроби было достаточно конечного количества цифр. Все было кратно атому.
Сегодня мы знаем, что и атом не является неделимым. И элементарные частицы не являются неделимым. И дискретность реального мира тем самым оказывается под вопросом. На самом глубоком уровне мир может оказаться непрерывным (аналоговым), а не дискретным. И нематериальные сущности, например, заряд, тоже могут оказаться не дискретными. Существуют частицы с дробным зарядом (заряд меньше заряда электрона). А ведь еще можно говорить о напряженности, например, электрического поля некой частицы с дробным зарядом на некотором расстоянии от нее.
Поэтому мы не можем сказать, сколько цифр нам нам может потребоваться в записи дробного числа. Просто завтра их может потребоваться больше, чем сегодня.
Небольшой математический экскурс
Обращаясь к истории мы увидели практическую сторону задачи записи чисел и выполнения вычислений. Но математика является абстрактной наукой, хоть и появилась как инструмент решения практических задач. Математику не важно, например, что именно мы делим на части. Операция деления абстрактна - мы делим просто одно число на другое число. И нам даже не важно, что это за числа. Более того, мы можем заменить числа переменными. И здесь возникает один очень интересный момент.
Достаточно легко разделить, например, один реальный хлеб на три равные части. И мы можем, не менее легко, записать в виде обыкновенной дроби 1/3. Но ведь одно и тоже число мы можем записать в разных формах. Работать с обыкновенными дробями менее удобно, чем с десятичными. Но при попытке записать число 1/3 в виде десятичной дроби мы обнаружим, что нам потребуется бесконечного количество цифр в дробной части. Впрочем, даже это не поможет записать число абсолютно точно.
И это проблема. Да, можно сказать, что она вызвана искусственно, так как можно было обойтись и без преобразования числа в десятичную дробь. Но это является наглядной демонстрацией того, что даже практические вычисления могут привести к ситуации, когда нам потребуется бесконечного количество цифр в записи числа, но неточность все равно сохранится. А ведь системы счисления могут быть разными. И число, которое мы можем точно записать в десятичной системе счисления при ручных расчетах, может оказаться невозможным точно записать в двоичной системе счисления, которая используется в ЭВМ. Дробное число, разумеется.
Арифметика манипулирует числами, но алгебра привносит понятие переменной, которая может соответствовать абсолютно любому числу. Причем априори считается, что точность переменной бесконечна. Таким образом, алгебра рассматривает числа, которые являются аналогами сущностей реального мира, как не просто бесконечную последовательность, но и последовательность непрерывную. Можно даже сказать, что переменные это аналоговые сущности.
Вот теперь мы можем перейти к сути тонкостей записи чисел и операций с ними. К вопросам, которые были подняты той самой дискуссией.
Непрерывность и дискретность
Итак, с точки зрения математики, переменные и числа являются бесконечными и непрерывными последовательностями. Мы можем описать такие последовательности как непрерывные математические функции, то есть, функции не имеющие точек разрыва. Еще раз подчеркну, что абстракция общего случая. А общий случай это совокупность случаев частных. Так множество действительных чисел действительно непрерывно, а множество натуральных чисел дискретно.
Как мы можем выразить это математически? Давайте введем понятие расстояния между двумя соседними (смежными) числами. Наглядно это можно показать с помощью числовой оси
Фактически, расстояние между смежными числами это просто разность между ними. Но поскольку числа это элементы множеств, то мы можем записать все так
То есть, предел разности двух смежных чисел, как элементов множеств, будет равен 0, если множество непрерывное. Если множество дискретное, то предел разности будет равен дискрету - приращению между смежными числами, расстоянию между ними.
Множество действительных чисел непрерывно, поэтому расстояние между двумя соседними числами равно 0. А вот расстояние между двумя натуральными числами равно 1, поэтому и множество натуральных чисел дискретно.
Совершенно очевидно и не требовалось столько времени тратить на объяснения? Подождите, это не голая теория, она напрямую соотносится с практикой вычислений.
Практический аспект записи чисел и операций с числами
Мой оппонент почему то посчитал, что слова из статьи "мы всегда будем ограничены весом младшего разряда цифрового представления, которое и определяет дискретность" относятся исключительно к определяемому аппаратно представлению чисел. То есть к тому, какую разрядность имеет процессор ЭВМ. Но простите, ведь в моих словах говорилось о цифровом представлении в общем и целом! Причем это, как мы сейчас увидим, касается вообще всех видов записи чисел и операций с ними.
Итак, у нас есть некоторая формула, причем нам сейчас не важно, что за формула, записанная с использованием переменных, знаков математических операций, математических функций. Нам требуется вычислить значение этой формулы для конкретных значений переменных. Приступим?
И мы сразу столкнемся с тем, что количество цифр в записи чисел, соответствующих значениям переменных, ограничено. То есть, математическая формула, которая соответствовала представлениям о непрерывности множества значений переменных, при практических вычислениях оказывается будет оперировать дискретным множеством чисел. И в этом нет ничего страшного. Просто мы перешли от общего случая к частному.
Абсолютно не важно, как именно, и где именно, выполняется запись чисел (значений переменных) и операции с числами. Мы может сделать это в уме, использовать лист бумаги, использовать арифмометр, использовать ЭВМ, и т.д. Суть от этого совершенно не меняется! И система счисления тоже ничего не изменяет.
Целые числа
Целые числа мы почти всегда можем записать точно. И большинство операций с целыми числами дадут точный результат, кроме деления, как пример. Почему "почти всегда"? Дело в том, что используемое нами количество цифр (разрядов) в записи целого числа может оказаться недостаточным, что бы вместить все число. В ЭВМ такая ситуация называется переполнением. Но ведь мы всегда можем перейти к "счету десятками". Или сотнями, и т.д. При этом целое число останется целым, но точным уже не будет. Мы обычно называем это округлением, например, до 10.
Дискрет множества таких "округленных целых чисел" будет уже равен не единице, а 10, 100, или больше. Смотря до чего мы округляем. Разумеется, точные операции с такими числами останутся точными, но поскольку участвующие в операции числа, хоть и целые, не являются точными, то результат точной операции оказывается неточным. Давайте взглянем на все это с точки зрения разрядности. Цифры, из которых состоит число, существуют не сами по себе, а располагаются в соответствующих позициях - разрядах. Вес каждого разряда определяется его положением в числе, с учетом основания системы счисления. Для простоты рассмотрим трехразрядные числа
Обратите внимание, что в округленных числах присутствуют "скрытые" разряды. Они не участвуют в записи числа и в операциях с числами, но все равно неявно присутствуют. И это влияет на то, какой именно вес будет иметь самый правый разряд в записи целого числа.
Для неокругленных, точных, целых чисел младшим разрядом всегда будут единицы. И дискретность такой записи всегда будет равна 1. В примере округленного целого числа (до сотен) младшим разрядом будет разряд сотен, так как разряды десятков и единиц скрыты округлением. И дискретность округленного до сотен числа будет равна 100, а не 1.
Единица разряда, и в десятичной, и в двоичной, системах счисления будет равна 1. Но с учетом веса младшего разряда мы и получаем реальную дискретность записи числа. И мы никак, при всем желании, не можем обойти эту дискретность. Хоть при вычислениях "на бумаге", хоть при использовании ЭВМ.
Действительные числа
Нам не важно деление действительных чисел на рациональные и иррациональные. Мы будем просто рассматривать представление действительных чисел в виде десятичной дроби. При этом нас не будет интересовать целая часть действительного числа, просто будем считать, что для целой части выделено достаточное количество разрядов. Нас будет интересовать лишь дробная часть числа. И округление будет затрагивать лишь количество разрядов (цифр!) в записи дробной части числа. Как видно, разница с целыми числами не велика
Скрытые разряды тоже присутствуют (в общем случае), но мы их обычно называем отбрасываемыми. Да, отбрасываемые разряды могут быть равны 0, если используемого количества разрядов (цифр!) в дробной части достаточно для точной записи числа. Но в большинстве случаев запись будет неточной. То есть, в большинстве случаев будет присутствовать округление.
Точно так же, как с целыми числами, мы можем выделить младший разряд, который будет самым правым в дробной части. И размер дискрета опять будет определяться единице с учетом веса этого разряда. В данном случае, дискрет будет равен 0.001 (одной тысячной).
Поскольку, в общем случае, запись действительных чисел будет неточной из-за ограниченного числа разрядов (бесконечное количество разрядов возможно только в теории, но не на практике), то и все операции с действительными числами будут неточными. Мы будем, абсолютно неизбежно, упираться в дискретность. В ту самую "единицу младшего разряда". Повторю, в практических вычислениях!
Но это еще не все, так как в математической операции могут присутствовать числа с разной дискретностью. И это тоже нужно учитывать. Но об этом чуть позже.
Действительные числа в экспоненциальной форме записи
Для очень больших и очень малых чисел использовать рассмотренную в предыдущем разделе форму записи крайне неудобно, так как требуется слишком большое количество разрядов (цифр). Для решения этой проблемы была придумана экспоненциальная форма записи. При этом ранее рассмотренный формат используется для записи мантиссы, а для указания величины и направления сдвига мантиссы на числовой оси используется целочисленный порядок.
Здесь мантисса обозначена буквой "m", а порядок буквой "p". Порядок не влияет на саму мантиссу, но изменяет вес разрядов в ней. Например, 1.5 т это 1500 кг. Но в экспоненциальной форме записи мантисса равна 1.5. Целая часть мантиссы соответствует разряду единиц, но порядок +3 сдвигает этот разряд на место разряда тысяч. В результате, целая часть мантиссы соответствует не 1, а 1000. Дробная часть мантиссы здесь равна 5 и расположена в разряде десятых. Но с учетом порядка она сдвигается на 3 разряда влево и будет соответствовать разряду сотен. И мы получаем число 1500, в обычной форме записи, которое соответствует нашей экспоненциальной форме записи.
Обратите внимание, что количество разрядов мантиссы все равно ограничено и она является обычным действительным числом. Значит сохраняется и дискретность! Но теперь на величину дискрета будет влиять и порядок, как описано выше. Поэтому дискретность может быть очень малой, но она неизбежно сохраняется из-за ограниченного количества разрядов мантиссы! То есть, не смотря ни на что мы опять упираемся в вес единицы младшего разряда числа, только теперь это будет определяться весом младшего разряда мантиссы с учетом порядка. Суть от этого не изменяется. И это верно как для ручных расчетов, так и при использовании ЭВМ.
Немного о тонкостях выполнения операций
С точностью записи чисел, которые в практических расчетах неизбежно будут дискретными, а не непрерывными, мы, пусть и очень упрощенно, разобрались. Но я хочу уделить немного дополнительно внимания операциям с действительными числами в экспоненциальной форме записи.
Сначала кратко о записи таких чисел в машинописных документах. В большинстве случаев набор символов машины (включая обычную пишущую машинку) ограничен. Поэтому математическую запись упрощают
Разумеется, если порядок отрицательный, то ему будет предшествовать знак минус (между буквой Е и порядком).
Экспоненциальная форма записи у новичков иногда вызывает восторг, ведь она позволяет обеспечивать, на первый (и ошибочный!) взгляд очень высокую точность. Но давайте вспомним, что порядок в такой форме записи приносит лишь облегчение в работе с большими и маленькими действительными числами. Это никак не изменяет правил выполнения операций с действительными числами. А эти правила требуют выравнивания чисел по разделителю целой и дробной частей, например, для сложения и вычитания. Для операций с числами в экспоненциальной форме записи это соответствует приведению порядков.
Давайте, для примера, рассмотрим сложение значительно различных чисел:
1.2340000Е12 + 1.2340000Е-12 = ?
Если мы попробуем привести порядок второго слагаемого к порядку первого слагаемого, то получим вот такое:
1.2340000Е12 + 0.000000Е12
Так как в результате приведения порядка количества разрядов дробной части оказывается недостаточно. И результат сложения будет просто равен первому слагаемому. И операция сложения становится просто излишней.
Если мы попытаемся привести порядок первого слагаемого к порядку второго, то получим переполнение, поскольку результат приведения не поместится в отведенное для числа количество разрядов. Это ошибка, которая приведет к невозможности выполнения операции сложения.
То есть, величина дискрета для экспоненциальной формы записи, который зависит от величины числа (дискрет мантиссы с учетом порядка), накладывает существенный отпечаток на результат вычисления. Снова повторю, что речь идет лишь о практических вычислениях. Причем любых, включая и машинные. То есть, абсолютно точная математическая формула, которая опирается на непрерывность и абсолютную точность значений переменных, в реальном мире и реальных вычислениях будет давать погрешность из-за дискретности чисел.
Промежуточный итог
То есть, абсолютно все цифровые методы вычислений, вне зависимости от того, выполняет вычисления человек или машина, будут иметь дискретный характер. Это суровая неизбежность, которая связана с ограниченным количеством разрядов в записи чисел и вытекающей из этого дискретности.
Вот это и имелось ввиду, когда я написал "мы всегда будем ограничены весом младшего разряда цифрового представления, которое и определяет дискретность". Цифровое представление не означает лишь "машинное", иначе бы так и было написано. Дискретность будет отсутствовать лишь при бесконечном количестве разрядов (цифр) в записи числа. Хоть у нас в голове, хоть на бумаге, хоть в памяти машины.
Да, мы может увеличить количество разрядов (и на бумаге, и в памяти ЭВМ), это уменьшит величину дискрета, но дискретность никуда не денется! Мы может использовать любые библиотеки, если разрядность процессора недостаточна, можем написать программу реализации своего метода, но это не устранит дискретность.
Да, мы можем вычислить число π с огромным количеством разрядов (сегодня вычислено несколько триллионов разрядов), но для этого используются специальные формулы и специальные алгоритмы вычисления. Итерационные, цифра за цифрой. Но число π все равно не вычислено абсолютно точно. Мы можем вычислить даже гугол разрядов числа π, но и этого может оказаться недостаточно. Да, дискретность будет исчезающе мала, но все таки она будет сохраняться.
И это вовсе не означает, что мы можем взять любую формулу и без всяких математических преобразований и учета алгоритмов и тонкостей вычислений получить абсолютно точный результат вычислений без даже намеков на дискретность!
Так что я вовсе не "застрял в 80-х", как заявлял мой оппонент. Я просто хорошо знаю теорию и практику как ручных, так и машинных вычислений. И математику, конечно.
Означает ли это, что машинные вычисления на ЦВМ ущербны по самой своей природе? Конечно не означает! Нам просто нужно обеспечить дискрет много меньше допустимой погрешности вычислений. Нам нужно не отсутствие дискретности, а приемлемая величина дискрета и связанной с этим погрешности. А для этого достаточно конечного количества разрядов.
Если аппаратной разрядности недостаточно мы просто будем использовать программные методы. Но крайне важно понимать, что платой за это будет значительное увеличение времени вычислений. И чем больше превышение программной разрядности над аппаратной, тем больше рост времени вычислений. Даже при использовании самых хитрых алгоритмов. Причем это касается и машинных вычислений, и ручных.
И еще один, но очень важный момент. Новички в программировании часто совершают одну ошибку - просто переносят математическую формулу в свою программу, совершенно не учитывая ни характер участвующих в вычислении данных, ни особенности "готовых библиотек". Результат зачастую бывает ужасен. К тому, что нужно выверять порядок вычисления, что нужно учитывать характер исходных данных, что нужно сортировать исходные данные для уменьшения погрешностей, приходят с опытом. Да и то не все. Видимо оппонент опыта еще не набрался...
Можно ли все это не учитывать? В ответ на заявления "можно, к черту все эти заморочки", скажу, что так вот и появляются программы, которые в тестовых примерах дают верный (допустимый) результат, но на некоторых наборах данных результат будет сущим кошмаром. Просто данные в том наборе "расположились неудачно".
Требуете примеры? Ну посмотрите хотя бы на ошибку команды FDIV в ранних Intel Pentium. При делении некоторых пар чисел с плавающей запятой процессор выдавал результат с очень большой погрешностью. И пусть вас не смущает, что та ошибка считается аппаратной. Команда FDIV выполнялась микропрограммно, поэтому и ошибка была именно программной, хоть с точки зрения чисто прикладных программистов и выглядела ка аппаратная.
Другой, весьма распространенной у новичков ошибкой, является вот такой код
float a, b;
if(a==b) ...
Дело в том, что в общем случае действительные числа в ЭВМ представлены не точно из-за дискретности. Мы только что это подробно разбирали. Проверка на равенство компилятором преобразуется в проверку равенства разности 0
if((a-b)==0) ...
Если значения переменные получили в результате вычислений, а не присваивания им одинаковых чисел, то результат вычитания будет неизбежно содержать погрешность. Поэтому две переменных, которые мы считаем равными, на самом деле будут немного отличаться и проверка на равенство окончится неудачей. Правильно сравнивать разность с некоторым очень малым числом, которое для определенности обозначим как epsilon
float a, b, epsilon;
epsilon=...
if(fabs(a-b)<epsilon)...
Да, это уже чисто машинные аспекты, которые не применимы к ручным вычислениям. Но ведь и оппонент говорил о машинных вычислениях, хоть всю статью мы и рассматривали вопрос в общем виде.
Заключение
Итак, любые численные (цифровые) методы записи чисел и выполнения вычислений, используемые на практике, обладают неизбежной дискретностью. Поэтому мы действительно будем ограничены единицей младшего разряда, как я и написал. И это верно и для машинных методов, и для ручных. Более того, в цепочках вычислений погрешность будет накапливаться. Накопление погрешности можно минимизировать используя математические преобразования, анализ и учет исходных данных, специальные алгоритмы, но это удается далеко не всегда.
Увеличение разрядности снижает связанную с дискретностью погрешность, но расплатой за это является увеличение времени выполнения вычислений. Нам зачастую и не требуется полное искоренение дискретности, просто погрешность не должна выходить за допустимые рамки. Иногда для этого приходится использовать более мощные ЭВМ, вплоть до суперЭВМ. Это в полной мере проявляется в математическом моделировании и научных расчетах, особенно при обработке больших объемов экспериментальных данных. И если кто то не сталкивался со всеми эти тонкостями, то совсем не значит, что этого не существует.
Остается очень коротко коснуться последнего вопроса - АВМ vs ЦВМ. Да, безусловно вычисления на АВМ не являются точными. Более того, погрешность АВМ зачастую превышает погрешность ЦВМ (ЭВМ). Это сегодня. Но в былые времена получить результат на АВМ часто было и быстрее, и точнее, чем на ЭВМ. Те времена прошли и ЭВМ в большинстве ситуаций выиграли. Но АВМ все таки сохранились в специфических местах.
Давайте вспомним, что математика считает переменную "аналоговой" величиной, ее значения принадлежат непрерывному множеству. И дискретность у нас возникает лишь в момент "оцифровки" аналоговой величины. То есть, в момент записи числа, вне зависимости, куда именно оно записывается. И все дальнейшие операции ЭВМ, как и человек (это важно!) выполняет уже с дискретными числами.
В противоположность этому на АВМ числа не оцифровываются, а представляются налоговыми величинами (напряжение, ток). Это касается и сигналов с различных датчиков экспериментальных установок, и задаваемых потенциометрами. И эти исходные данные тоже содержат погрешности. Но все операции выполняются в аналоговом виде. И погрешности тоже возрастают, так как параметры электронных элементов АВМ не идеальны. Но все таки результат, пусть и с погрешностью, все равно остается аналоговым.
Дискретным результат становится лишь в момент считывания его человеком или ЭВМ. Поэтому до считывания результата мы не можем говорить о каких либо "единицах младшего разряда числа", так как это понятие к аналоговой величине неприменимо. И погрешности порождаются совсем другими причинами. И мы можем уменьшить погрешность аналоговых вычислений используя более качественные компоненты схем, уменьшая влияние внешних полей, исключая колебания температуры, и т.д. Это повышает стоимость, но не влияет на время вычислений.
Идеала нет. И плата за снижение погрешности разная для АВМ и ЭВМ. Разный принцип их работы. Вам, прочитавшему эту занудную статью, возможно никогда ни с чем подобным сталкиваться не приходилось. Но может быть еще придется столкнуться?...