|
11.12.2014, 17:19 | #1 |
Gold Member
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,814
|
Аппроксимация 80-битного float рациональным числом
Озаботился тут написанием своей процедуры преобразования веществен-
ного числа (80-битного extended) рациональным числом в виде P / Q, где P и Q - сверхбольшие целые числа, арифметику кот. я реализовал ранее. Написал, много разных замороченных багов отловил и исправил, вроде все. Но надо как следует потестировать. Если несложно погоняйте программу, в которой в верхнем поле вводите любое число 1E-4932 <= |X| <= 1E4932, во второй строке получаете аппроксимацию дробью. Для очень больших и очень маленьких вещественных дробь может оказаться очень большой и в маленькое текстовое окно целиком не влезть, тогда выделите его и скопи- руйте куда-нибудь в блокнот, и там уже целиком ее можно будет увидеть. В третьей строке отображается контрольная проверка (результат деления числителя дроби на знаменатель), и выводится результат в виде extended. Точность: 1E-18. То есть, максимум 18 цифр, дальше уже все округляется. |
Реклама | |
|
20.12.2014, 18:38 | #2 |
Gold Member
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,814
|
В итоге задача преобразования привела к небольшому исследованию.
Преобразовывать из 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. Плюс - только то, что десятичные преобразования привычнее и понятнее человеку. Минус - намного медленнее двоичного метода, к тому же вносит свою погрешность. Впрочем, как говорится, лучше один раз увидеть все самим, и погонять программу, в котором реализованы оба метода обоих преобразований и есть возможность как для ручного преобразования заданного числа, так автоматическое тестирование с использованием случайных вещественных чисел и сбором статистики погрешностей. |
21.12.2014, 15:53 | #3 |
Gold Member
Регистрация: 25.06.2005
Адрес: F000:FFF0
Сообщений: 1,814
|
Обновление, небольшая оптимизация двоичных преобразований.
Протестировал все 4 сочетания режимов преобразований в дробь и обратно по 10 миллионов случайных вещественных чисел float80. В режиме двоичный/двоичный, худшая относительная погрешность = 0. В режиме десятичный/двоичный, худшая относит. погрешность = 9,99E-19. В режиме двоичный/десятичный худшая относит. погрешность = 2,99E-19. В режиме десятичный/десятичный худшая относит. погрешность = 1,11E-18. |