Этот вопрос имеет бюрократическую и алгоритмическую части.Число с плавающей запятой хранится внутри как (2 e × m), где e - показатель степени (сам двоичный), а m - мантисса.Бюрократическая часть вопроса заключается в том, как получить доступ к этим данным, но Р., похоже, больше интересует алгоритмическая часть вопроса, а именно преобразование (2 e × m) в дробь (a / b) вдесятичная форма.Ответ на бюрократический вопрос на нескольких языках - «frexp» (это интересная деталь, которую я не знал до сегодняшнего дня).
Это правда, что на первый взгляд требуется O (e 2 ) работает только для записи 2 e в десятичном виде, и еще больше времени для мантиссы.Но, благодаря волшебству алгоритма быстрого умножения Schonhage-Strassen , вы можете сделать это за Õ (e) времени, где тильда означает «до логарифмических факторов».Если вы рассматриваете Schonhage-Strassen как магию, то не так сложно думать о том, что делать.Если e чётно, вы можете рекурсивно вычислить 2 e / 2 , а затем возвести его в квадрат с помощью быстрого умножения.С другой стороны, если e нечетно, вы можете рекурсивно вычислить 2 e-1 и затем удвоить его.Вы должны быть осторожны, чтобы проверить, есть ли версия Schonhage-Strassen в базе 10. Хотя это не широко документировано, это может быть сделано в любой базе.
Преобразование очень длинной мантиссы из двоичной в базовую10 не совсем тот же вопрос, но он имеет аналогичный ответ.Вы можете разделить мантиссу на две половины, m = a 2 k + b.Затем рекурсивно преобразуйте a и b в основание 10, преобразуйте 2 ^ k в основание 10 и выполните другое быстрое умножение для вычисления m в основании 10.
Абстрактный результат, лежащий в основе всего этого, заключается в том, что вы можете преобразовать целые числа изодна база к другой за время Õ (N).
Если вопрос касается стандартных 64-битных чисел с плавающей запятой, то он слишком мал для причудливого алгоритма Шонхаге-Штрассена.В этом диапазоне вы можете вместо этого сохранить работу с различными трюками.Один из подходов состоит в том, чтобы сохранить все 2048 значений 2 e в справочной таблице, а затем работать в мантиссе с асимметричным умножением (между длинным умножением и коротким умножением).Другой трюк заключается в работе на базе 10000 (или более высокой степени 10, в зависимости от архитектуры) вместо базы 10. Но, как указывает Р. в комментариях, 128-битные числа с плавающей запятой уже позволяют достаточно большим показателям вызыватьвопрос и таблицы поиска и стандартное длинное умножение.На практике длинное умножение является самым быстрым, вплоть до нескольких цифр, затем в значительном среднем диапазоне можно использовать умножение Карацубы или умножение Тоом-Кука , а затем после этоговариант Schonhage-Strassen лучше всего подходит не только в теории, но и на практике.
На самом деле, большой целочисленный пакет GMP уже имеет radi (N) преобразование радиуса времени, а также хорошееэвристика, для которой выбор алгоритма умножения.Единственное различие между их решением и моим состоит в том, что вместо выполнения какой-либо большой арифметики в базе 10 они вычисляют большие степени 10 в базе 2. В этом решении им также требуется быстрое деление, но это можно получить из быстрого умножения в любомнескольких способов.