Портал аспирантов
 

Вернуться   Портал аспирантов > Общие > Дискуссионный зал > Физико-математические науки

Ответ
 
Опции темы
Старый 11.12.2014, 17:19   #1
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию Аппроксимация 80-битного float рациональным числом

Озаботился тут написанием своей процедуры преобразования веществен-
ного числа (80-битного extended) рациональным числом в виде P / Q, где
P и Q - сверхбольшие целые числа, арифметику кот. я реализовал ранее.

Написал, много разных замороченных багов отловил и исправил, вроде все.
Но надо как следует потестировать. Если несложно погоняйте программу,
в которой в верхнем поле вводите любое число 1E-4932 <= |X| <= 1E4932,
во второй строке получаете аппроксимацию дробью. Для очень больших и
очень маленьких вещественных дробь может оказаться очень большой и в
маленькое текстовое окно целиком не влезть, тогда выделите его и скопи-
руйте куда-нибудь в блокнот, и там уже целиком ее можно будет увидеть.
В третьей строке отображается контрольная проверка (результат деления
числителя дроби на знаменатель), и выводится результат в виде extended.

Точность: 1E-18. То есть, максимум 18 цифр, дальше уже все округляется.
Вложения
Тип файла: zip E2Rtest.zip (382.6 Кб, 7 просмотров)
Paul Kellerman вне форума   Ответить с цитированием
Реклама
Старый 20.12.2014, 18:38   #2
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию

В итоге задача преобразования привела к небольшому исследованию.

Преобразовывать из 80-битного float X в дробь P/Q можно двумя способами:

1) Напрямую залезая в биты мантиссы и экспоненты и работая в привычном
для процессора двоичном формате: считываем 64-битную мантиссу как 64-
битное беззнаковое целое и заносим в P, а Q полагаем 2^63. Затем считав
двоичную экспоненту, анализируем ее и сдвигаем на E-63 бит влево P, если
экспонента E > 63, или сдвигаем на 63-E бит влево Q, если экспонента E < 63.
Плюс метода - максимальная скорость и точность преобразования. Минус же
- почти всегда громоздкие дроби, за исключением случаев, когда число может
быть точно представлено дробью, у которой знаменатель является степенью 2.

2) Десятичный - аппроксимация с использованием быстросходящегося алгоритма
Евклида. За несколько итераций удается выйти на дробь, которая приближается
к исходному вещественному с относительной погрешностью 10^(-18). Причем в
алгоритме все переменные как это не прозвучит странно - вещественные, в том
числе и P и Q для максимальной скорости, и только в конце они округляются до
целого. И тут еще одна загвоздка - большинство сред программирования могут
вытаскивать только 18 десятичный цифр из 80-битного вещественного, и оно и
понятно (сам процессор имеет ассемблерную команду FBSTP, которая умеет 18
десятичных цифр получать из вещественного числа, не превосходящего 10^18).
В то же время в 64-бита мантиссу гарантированно влезают любые 19-разрядные
десятичные числа. Если довольствоваться стандартными средствами, выдающих
18 цифр, то итоговая погрешность аппроксимации ухудшается почти в 6 раз, и
достигает 5,6*10^(-18), и поэтому необходимо было любой ценой извернуться и
достать 19-ю десятичную цифру, и худшая итоговая погрешность < 1,2*10^(-18).
Плюс - максимально компактные (привычные для человека) дроби, при этом ско-
рость преобразования лишь немного уступает двоичному (работа на уровне битов).

Обратное преобразование из дроби в вещественное тоже можно двумя способами:

1) Двоичный - нормализуем P и Q, так чтобы старший бит у P был 127-м, а у Q был
63-м. После этого делим P на Q, и получаем 64 или 65-битное частное, если 65 бит,
то сдвигаем частное на 1 разряд вправо и делаем 64-битным. После этого записы-
ваем их в 64 бита мантиссы итогового вещественного. Экспонента формируется на
основе разницы номеров старших битов исходных P и Q (перед нормализацией), и
если частное получалось 64-битным, из разницы еще дополнительно вычитается 1.
Плюс метода - максимально быстро, точно и привычно с точки зрения процессора.

2) Десятичный - вычисляем десятичные логарифмы от P и Q и вычисляем разницу,
потом нормализуем P и Q по степеням 10 так, так чтобы они стали 19-разрядными
десятичными числами. После этого преобразуем их в вещественные числа, и делим
их друг на друга. Получившееся частное затем масштабируем по степеням 10 на
основе разницы логарифмов. Причем если частное оказалось меньше 1, то предва-
рительно умножаем его на 10, а разницу логарифмов при этом увеличиваем на 1.
Плюс - только то, что десятичные преобразования привычнее и понятнее человеку.
Минус - намного медленнее двоичного метода, к тому же вносит свою погрешность.

Впрочем, как говорится, лучше один раз увидеть все самим, и погонять программу,
в котором реализованы оба метода обоих преобразований и есть возможность как
для ручного преобразования заданного числа, так автоматическое тестирование с
использованием случайных вещественных чисел и сбором статистики погрешностей.
Вложения
Тип файла: zip E2Rtest.zip (423.6 Кб, 1 просмотров)
Paul Kellerman вне форума   Ответить с цитированием
Старый 21.12.2014, 15:53   #3
Paul Kellerman
Gold Member
 
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,804
По умолчанию

Обновление, небольшая оптимизация двоичных преобразований.

Протестировал все 4 сочетания режимов преобразований в дробь
и обратно по 10 миллионов случайных вещественных чисел float80.

В режиме двоичный/двоичный, худшая относительная погрешность = 0.
В режиме десятичный/двоичный, худшая относит. погрешность = 9,99E-19.
В режиме двоичный/десятичный худшая относит. погрешность = 2,99E-19.
В режиме десятичный/десятичный худшая относит. погрешность = 1,11E-18.
Вложения
Тип файла: zip E2Rtest.zip (423.6 Кб, 1 просмотров)
Paul Kellerman вне форума   Ответить с цитированием
Ответ

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.



Текущее время: 00:50. Часовой пояс GMT +3.


Powered by vBulletin® Version 3.8.8
Copyright ©2000 - 2024, vBulletin Solutions, Inc. Перевод: zCarot
© 2001—2024, «Аспирантура. Портал аспирантов»
Рейтинг@Mail.ru