Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 33
Может вы не знаете но есть IEEE 754—2008 в котором есть decimal32, decimal64, decimal128.
Рассмотрим сумму двух чисел 1.234567*10^3+7.654321*10^-1. Вычисление проведем с точностью до 7 значащих цифр, или с точностью до 6 знаков после точки.
Для этого представим наши числа в нормализованном виде: 1234567*10^-3; 7654321*10^-1. В СДДФ они будут выглядеть как [0, 000100101101011010000111,1,11] и
[0, 011101001100101110110001,1, 1].
Будем складывать в соответствие с правилами арифметики. 1234567*10^-3+ 7654321*10^-1=(1234567*10^-2+ 7654321) *10^-1= (12345,67 + 7654321)*10^-1=7666666,67*10^-1≈7666667*10^-1. Или в двоичном виде: 1234567*10^-2= 000100101101011010000111/1100100≈ 11000000111001.1≈11000000111010=12346. Сумма чисел в скобках будет 11000000111010+011101001100101110110001=11101001111101111101011=7666667. В результате получим число 7666667*10^-1, такое же, как если бы мы вычисляли вручную с точностью до 7 значащих цифр. В СДДФ это число будет выглядеть как
[0, 11101001111101111101011,1, 1]. В нем S=0, M=11101001111101111101011=7666667, z=1, e=1.
Для этого представим наши числа в нормализованном виде: 1234567*10^-3; 7654321*10^-1. В СДДФ они будут выглядеть как [0, 000100101101011010000111,1,11] и
[0, 011101001100101110110001,1, 1].
Будем складывать в соответствие с правилами арифметики. 1234567*10^-3+ 7654321*10^-1=(1234567*10^-2+ 7654321) *10^-1= (12345,67 + 7654321)*10^-1=7666666,67*10^-1≈7666667*10^-1. Или в двоичном виде: 1234567*10^-2= 000100101101011010000111/1100100≈ 11000000111001.1≈11000000111010=12346. Сумма чисел в скобках будет 11000000111010+011101001100101110110001=11101001111101111101011=7666667. В результате получим число 7666667*10^-1, такое же, как если бы мы вычисляли вручную с точностью до 7 значащих цифр. В СДДФ это число будет выглядеть как
[0, 11101001111101111101011,1, 1]. В нем S=0, M=11101001111101111101011=7666667, z=1, e=1.
google говорит другое 1235.3324321 https://www.google.com/search?q=1.234567*10%5E3+%2B+7.654321*10%5E-1&ie=utf-8&oe=utf-8
>(1234567*10^-2+ 7654321) *10^-1= (12345,67 + 7654321)*10^-1
Иными словами, приходится умножать на число, не равное основанию системы.
Это точно менее громоздко, чем двоично-десятичная арифметика?
Иными словами, приходится умножать на число, не равное основанию системы.
Это точно менее громоздко, чем двоично-десятичная арифметика?
В СДДФ все операции производятся над целыми числами, представленными в двоичном виде. Мы умножаем/делим ни на число, которое «не равно основанию системы», а на целое число, равное 10 в какой-то степени, которое представлено в двоичном виде.
Мы умножаем/делим ни на число, которое «не равно основанию системы», а на целое число, равное 10 в какой-то степени, которое представлено в двоичном виде.
10 по-вашему, равно основанию двоичной системы?
Впрочем, это лирика. Суть в том, что Вам приходится делать настоящее умножение вместо сдвига.
Вы проверяли, Ваш алгоритм действительно менее громоздок, чем двоично-десятичный?
10 по-вашему, равно основанию двоичной системы?
У меня смешанный десятично-двоичный формат.
В современных АЛУ операция умножения/деления двух целых чисел делается за 1 такт.
А вот, чтобы сложить два десятичных ЧПТ в BCD, а тем более с различными экспонентами, приходится попотеть. www.e-reading.club/chapter.php/99776/140/Cvetkova_-_Informatika_i_informacionnye_tehnologii__konspekt_lekciii.html
У меня смешанный десятично-двоичный формат.
Складываете и умножаете Вы двоичные числа. Как храните — вопрос десятый.
Т.е. алгоритм эффективен только на процессорах, имеющих целочисленное умножение за 1 такт. Да, при такой области применения, Вы правы.
Интересно было бы сравнить СДДФ с ДДФ на процессоре без команд умножения…
Складываете и умножаете Вы двоичные числа. Как храните — вопрос десятый.
Как сказать? Если обрабатывать большой массив чисел из памяти, то вопрос распаковки весьма актуален.
Интересно было бы сравнить СДДФ с ДДФ на процессоре без команд умножения…
По-моему, в настоящее время без аппаратного умножителя выпускаются только очень дешевые микроконтроллеры для несложных задач.
>> В современных АЛУ операция умножения/деления двух целых чисел делается за 1 такт.
А можно пруф?
Или хотя бы просто бенчмарк, который 2 случайных числа делит быстрее чем за наносекунду (такт сильно меньше)
По ссылке выше просто информация о медленности BCD, что логично. Поэтому никто в здравом уме в BCD мантиссы и не хранит.
А можно пруф?
Или хотя бы просто бенчмарк, который 2 случайных числа делит быстрее чем за наносекунду (такт сильно меньше)
По ссылке выше просто информация о медленности BCD, что логично. Поэтому никто в здравом уме в BCD мантиссы и не хранит.
Речь идет об FPU
Поэтому никто в здравом уме в BCD мантиссы и не хранит.
В IEEE754-2008 мантисса может храниться в двух видах. Как целое двоичное число и как упакованное BCD число.
На FPU нет деления за 1 такт, вас обманули.
Минимум чего обещают — 11 тактов (руководство по оптимизации от Intel). И это на плавающей точке на команде divss и в хороших условиях, скорее всего применяется метод Goldschmidt'а. На фиксированной — заметно дольше (будет SRT или что-то подобное).
Возможно, вы основывались на других данных: на том, что деление нацело на фиксированный делитель заменяется любым современным компилятором на обратное умножение. Это действительно может сделать операцию деления ценой на ненамного дороже умножения. У этого решения возможна и аппаратная реализация, и скорее всего она таки уже применена.
Минимум чего обещают — 11 тактов (руководство по оптимизации от Intel). И это на плавающей точке на команде divss и в хороших условиях, скорее всего применяется метод Goldschmidt'а. На фиксированной — заметно дольше (будет SRT или что-то подобное).
Возможно, вы основывались на других данных: на том, что деление нацело на фиксированный делитель заменяется любым современным компилятором на обратное умножение. Это действительно может сделать операцию деления ценой на ненамного дороже умножения. У этого решения возможна и аппаратная реализация, и скорее всего она таки уже применена.
> Или хотя бы просто бенчмарк, который 2 случайных числа делит быстрее чем за наносекунду (такт сильно меньше)
Ну случайное число ему там не сильно нужно — деление на несколько фиксированных степеней числа 10 может быть сделано через умножение на вшитый обратный множитель для каждого реализованного случая (а вот их уже можно делать через степени двойки в показателе). А на умножение, IMHO, лучше писать 3 такта (если меньше, это такты слишком длинные, а не умножение лёгкое).
> Поэтому никто в здравом уме в BCD мантиссы и не хранит.
Увы, IEEE754-2008 их таки ввёл в BCD тоже. Зачем, для кого они это сделали — ХЗ.
Я пытался найти бенчмарки binary vs decimal в железе, где есть последнее (IBM zSeries и POWER), но пока безуспешно. Есть только такое, где BCD раза в полтора медленнее чисто двоичной, но по разным операциям разница катастрофически неровна => ещё явно надо оптимизировать и отлаживать.
Ну случайное число ему там не сильно нужно — деление на несколько фиксированных степеней числа 10 может быть сделано через умножение на вшитый обратный множитель для каждого реализованного случая (а вот их уже можно делать через степени двойки в показателе). А на умножение, IMHO, лучше писать 3 такта (если меньше, это такты слишком длинные, а не умножение лёгкое).
> Поэтому никто в здравом уме в BCD мантиссы и не хранит.
Увы, IEEE754-2008 их таки ввёл в BCD тоже. Зачем, для кого они это сделали — ХЗ.
Я пытался найти бенчмарки binary vs decimal в железе, где есть последнее (IBM zSeries и POWER), но пока безуспешно. Есть только такое, где BCD раза в полтора медленнее чисто двоичной, но по разным операциям разница катастрофически неровна => ещё явно надо оптимизировать и отлаживать.
Да, я как-то замерял switch-case на 9 константных делителей vs обычное деление — switch сильно быстрее. Но тут их не 9, а 128, так что хз. Может сработает, а может загнётся кэш инструкций и будет грузить каждое конкретное деление из ОЗУ за те же десятки наносекунд.
IEEE действительно странный, допускает как BCD, так и binary. Может они заложились на гипотетическую платформу, которая с BCD работает не сильно медленнее. Нормализовывать десятичную точку все-таки удобнее в BCD.
IEEE действительно странный, допускает как BCD, так и binary. Может они заложились на гипотетическую платформу, которая с BCD работает не сильно медленнее. Нормализовывать десятичную точку все-таки удобнее в BCD.
Я правильно понимаю, что описано вот это, просто по-русски и другими словами?
https://en.m.wikipedia.org/wiki/Decimal_floating_point
Вычисления в decimal floating point действительно более «привычные» для человека, хотя остаётся проблема с округлением (10^64 + 10^-64 — 10^64 == 0). Основная проблема с ними — производительность, любое сложение/вычитание с разными экспонентами требует деления на степень десятки, что на порядок медленнее обычного сложения.
Необходимо различать следующие этапы арифметической обработки данных.
1. Распаковка. Она состоит из декодирования числа, записанного в памяти машинного слова в так называемом формате обмена. Число хранится в упакованном виде.
2. Арифметические операции, которые производятся над распакованными числами с использованием операционных регистров в расширенном виде.
3. Запаковка результата.
Сравнивая формат decimal IEEE и СДДФ, можно видеть, что упаковка-распаковка для decimal производится по достаточно сложному алгоритму, состоящему из проверок множества условий.
Числа в СДДФ записываются в память машины без какой-либо предварительной обработки.
Десятичная арифметика в настоящее время реализована двоично-десятичным форматом (BCD). Для округления в этом формате требуется операция деления/умножения на 10.
Реализовать сложение десятичных чисел в двоичном виде с разными экспонентами без деления на 10 можно только приблизительно.
Основная проблема в компьютерной бинарной арифметике, это получение необходимой точности вычислений. Существует много способов повысить точность вычислений. В частности: увеличение разрядности операционных регистров и специальные алгоритмы обработки (алгоритм Кэхэна), которые приводят к существенным дополнительным программно-аппаратным затратам.
Алгоритм, использующий СДДФ позволяет получать результаты, такие же, как сделанные вручную с небольшими накладными расходами…
1. Распаковка. Она состоит из декодирования числа, записанного в памяти машинного слова в так называемом формате обмена. Число хранится в упакованном виде.
2. Арифметические операции, которые производятся над распакованными числами с использованием операционных регистров в расширенном виде.
3. Запаковка результата.
Сравнивая формат decimal IEEE и СДДФ, можно видеть, что упаковка-распаковка для decimal производится по достаточно сложному алгоритму, состоящему из проверок множества условий.
Числа в СДДФ записываются в память машины без какой-либо предварительной обработки.
Десятичная арифметика в настоящее время реализована двоично-десятичным форматом (BCD). Для округления в этом формате требуется операция деления/умножения на 10.
Реализовать сложение десятичных чисел в двоичном виде с разными экспонентами без деления на 10 можно только приблизительно.
Основная проблема в компьютерной бинарной арифметике, это получение необходимой точности вычислений. Существует много способов повысить точность вычислений. В частности: увеличение разрядности операционных регистров и специальные алгоритмы обработки (алгоритм Кэхэна), которые приводят к существенным дополнительным программно-аппаратным затратам.
Алгоритм, использующий СДДФ позволяет получать результаты, такие же, как сделанные вручную с небольшими накладными расходами…
Вы пишите что
Десятичная арифметика в настоящее время реализована двоично-десятичным форматом (BCD).. То есть мантиссу вы сначала превращаетесь в bcd (в тетрадах байта цифры числа) и только потом выполняете арифметическую операцию?
Нет, мантисса выражена, как целое двоичное число. Арифметическая операция выполняется над целыми двоичными числами- целочисленная мантисса и двоичный эквивалент характеристики (10^e).
Здесь речь идет о том, как это реализовано в компьютере сегодня.
Десятичная арифметика в настоящее время реализована двоично-десятичным форматом (BCD).
Здесь речь идет о том, как это реализовано в компьютере сегодня.
остаётся проблема с округлением (10^64 + 10^-64 — 10^64 == 0).
В СДДФ такой проблемы не существует. Как и в обычной арифметике вычисление, допустим, 1,2345-1,2343 с точностью до 4 значащих цифр даст 0.
Почему этот пост в хабах c#, c, c++?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Двоичные вычисления для десятичной арифметики