Как Вы печатаете ТОЧНОЕ значение числа с плавающей точкой?

В этом вопросе есть бюрократическая часть и алгоритмическая часть. Число с плавающей запятой хранится внутри как (2 ^e × m), где e - показатель степени (в двоичном формате), а m - мантисса. Бюрократическая часть вопроса заключается в том, как получить доступ к этим данным, но Р., похоже, больше интересует алгоритмическая часть вопроса, а именно преобразование (2 ^e × m) в дробь (a / b) в десятичная форма. Ответ на бюрократический вопрос на нескольких языках - «frexp» (это интересная деталь, о которой я не знал до сегодняшнего дня).

Это правда, что на первый взгляд требуется O (e ² ) работы, чтобы просто записать 2 ^e в десятичной системе, и еще больше времени для мантиссы. Но, благодаря магии алгоритма быстрого умножения Шёнхаге-Штрассена , вы можете сделать это за Õ (e) времени, где тильда означает «с точностью до логарифмических множителей». Если вы считаете Шёнхаге-Штрассен волшебством, то не так уж и сложно придумать, что делать. Если e четно, вы можете рекурсивно вычислить 2 ^{e / 2} , а затем возвести его в квадрат, используя быстрое умножение. С другой стороны, если e нечетно, вы можете рекурсивно вычислить 2 ^e-1 , а затем удвоить его. Вы должны быть осторожны, чтобы проверить, есть ли версия Шёнхаге-Штрассена в базе 10. Хотя это не так широко документировано, это можно сделать в любой базе.

Преобразование очень длинной мантиссы из двоичной в основание 10 - это не совсем тот же вопрос, но на него есть похожий ответ. Вы можете разделить мантиссу на две половины: m = a 2 ^k + b.Затем рекурсивно преобразуйте a и b в базу 10, преобразуйте 2 ^ k в базу 10 и выполните еще одно быстрое умножение для вычисления m в базе 10.

Абстрактный результат всего этого заключается в том, что вы можете преобразовать целые числа из одной базы в другой через Õ (N) раз.

Если речь идет о стандартных 64-битных числах с плавающей запятой, то это слишком мало для причудливого алгоритма Шёнхаге-Штрассена. В этом диапазоне вы можете вместо этого сохранить работу с помощью различных уловок. Один из подходов состоит в том, чтобы сохранить все 2048 значений 2 ^e в таблице поиска, а затем работать с мантиссой с асимметричным умножением (между длинным и коротким умножением). Другой трюк - работать с базой 10000 (или с более высокой степенью 10, в зависимости от архитектуры) вместо базы 10. Но, как указывает R. в комментариях, 128-битные числа с плавающей запятой уже позволяют вызывать достаточно большие экспоненты для вызова. подвергают сомнению обе таблицы поиска и стандартное длинное умножение. На практике длинное умножение является самым быстрым до нескольких цифр, затем в значительном среднем диапазоне можно использовать умножение Карацубы или умножение Тоома-Кука , а затем после этого вариант Шёнхаге-Штрассена лучше всего не только в теории, но и на практике.

На самом деле, в большом целочисленном пакете GMP уже есть Õ (N) преобразование счисления счисления по времени, а также хорошая эвристика для выбора алгоритма умножения. Единственная разница между их решением и моим состоит в том, что вместо того, чтобы выполнять какие-либо большие арифметические операции с основанием 10, они вычисляют большие степени 10 по основанию 2.В этом решении они также нуждаются в быстром делении, но его можно получить путем быстрого умножения любым из нескольких способов.