В ходе довольно жаркой дискуссии был затронут
один интересный вопрос: преобразование float
в str
.
Коротко о сути проблемы:
На Питоне 2.6 число 4.31
выглядит как 4.3099999999999996
:
Python 2.6.6 (r266:84292, Sep 15 2010, 16:22:56)
[GCC 4.4.5] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 4.31
4.3099999999999996
>>>
Питон 2.7 (и 3.1) работает несколько иначе:
Python 2.7.0+ (r27:82500, Sep 15 2010, 18:14:55)
[GCC 4.4.5] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 4.31
4.31
>>>
Это баг или изменение записи float
чисел?
Ни то ни другое.
Во первых, это одно и то же число:
>>> 4.31 == 4.3099999999999996
True
>>>
Во вторых, битовые записи обоих чисел совпадают.
Т.е. это имеенно то же самое число, а не результат какого-то хитрого поведения операции сравнения:
>>> import struct
>>> a = struct.pack('d', 4.31)
>>> b = struct.pack('d', 4.3099999999999996)
>>> a == b
True
>>>
Можно приести еще несколько примеров, доказывающих идентичность - но это излишне.
Так что же поменялось?
Изменилась реализация метода __repr__
,
т.е. преобразование float
в строку str
.
Это отражено в баг трекере Питона и списке изменений.
Видимо, текст по приведенным ссылкам недостаточно хорошо описывает суть проделанной работы.
Попытаюсь пересказать на русском и более развернуто.
Имеем дробь 4.31
.
В float она хранится в виде <знак>1.<мантисса> * pow(2, <экспонента>)
Знак и экспонента сейчас не важны. Мантисса - дробная часть числа, записанная по основанию два.
Оригинальная запись была "4.31"
, дробная часть пишется по основанию 10
.
Когда переводим из десятичного основания в двоичное - получаем бесконечную дробь.
Примерно как натуральная дробь 1/3
в переводе
на десятичное основание - тоже бесконечная.
В float мантисса записывается "пока хватает места", а (возможно, бесконечный) остаток выбрасывается.
Если записывать 1/3
с точностью до 3
знаков, получим 0.333
.
В float
пятьдесят три (считая со старшей неявной единицей) двоичных разряда.
Я не хочу приводить эту длинную простыню ноликов и единичек, достаточно представить что она есть.
Теперь нужно обратно перевести float в строку в десятичном представлении.
Двоичное число стало конечным.
Но из-за отсечения не поместившихся бит оно не точно соответствует десятичному числу, из которого конструировалось.
Python 2.6- (и Python 3.0) делали это так:
преобразовывали "как есть" и получали длинный "хвост" - 4.3099999999999996
В Python 3.1 (а после и в Python 2.7) алгоритм поменяли.
Это длинная простыня format_float_short
в ./Python/pystrtod.c
Работает она так:
У нас есть мантисса <b1 b2 b3 b4 b5>
- на самом деле 52 бита.
Переводим ее в десятичную форму: <d1 d2>
.
Перевод остановился на b3
, например
- потому что b4
и b5
не дают десятичного числа, нужны еще биты.
Последняя десятичная цифра d3
- неполная,
потому что входной поток бит закончился раньше,
чем мы получили их достаточное количество.
Добавляем в этот поток все возможные комбинации,
необходимые для завершения построения d3
.
Выбираем из всех возможных d3
такую цифру,
чтобы результирующее число имело минимальную запись.
Чем больше выходит десятичных ноликов в конце, тем лучше.
Вуаля, получили минимальное десятичное представление двоичного числа.
Легко заметить, чем отличается старый алгоритм от нового.
Старый добавлял нулевые биты для построения d3
, в то время как
новый подбирает их по более умному принципу.
Заключение
Внимание, это - не округление в математическом смысле слова.
Алгоритм подбирает такой остаток, не поместившийся в мантиссу из-за конечного ее размера, чтобы результат можно было записать минимальным количеством цифр.
Точность при этом не теряется - десятичное число "длиннее" в двоичном виде, чем мантисса в float и при этом совпадает с ней на первых 52 битах.
Получилось всё еще довольно сложно и запутанно - но этот вопрос крайне нелегко объясняется "на пальцах".
Вот документ, с которого всё начиналось: FP-Printing-PLDI96.pdf
Довольно много математики.
Довеском предлагаю ознакомится с замечательными статьями по работе чисел с плавающей запятой.
А чеб не кидать с хабра ссылки на блог? :)
ОтветитьУдалитьМатериал интересный и полезный. Реквестирую еще :)
Я не зарегистрирован на Хабре :(
ОтветитьУдалитьИзбегаю этот ресурс - слишком много пишут, читать не успевал.
Иногда прихожу на этот хабр по ссыклам с Планеты Питон. Комментировать не дают - регистрация нужна.
Может, чего-то не понимаю в жизни.
Если вы будете постить мои поделки на хабре с ссылкой на этот блог - возражений не имею.
Там (на хабре) дурацкие правила по-поводу чужих статей.
ОтветитьУдалитьА для регистрации нужен инвайт. С удовольствием отдам его вам, если и когда он у меня появится. Ну или может кто-нибудь с форума поделится :)