Как printf извлекает цифры из числа с плавающей запятой?

Question

Как функции, такие как printf, извлекают цифры из числа с плавающей запятой? Я понимаю, как это можно сделать в принципе. Для заданного числа x, из которых вам нужны первые n цифры, масштабируйте x в степени 10, чтобы x находилось между pow(10, n) и pow(10, n-1). Затем преобразуйте x в целое число и возьмите цифры целого числа.

Я попробовал это, и это сработало. Вроде, как бы, что-то вроде. Мой ответ был идентичен ответу, данному printf для первых 16 десятичных цифр, но, как правило, отличался от тех, что после этого. Как printf это делает?

Answer 1

Классическая реализация - Дэвид Гэй dtoa. Точные детали несколько загадочны (см. Почему «dtoa.c» содержит так много кода? ), но в целом он работает, выполняя базовое преобразование, используя большую точность, чем та, которую вы можете получить из 32- разрядное, 64-разрядное или даже 80-разрядное число с плавающей запятой. Для этого он использует так называемые числа больших чисел или числа произвольной точности, которые могут содержать столько цифр, сколько вы можете уместить в памяти. Код Gay был с изменениями скопирован в бесчисленное множество других библиотек, включая общие реализации стандартной библиотеки C (так что она может питать ваши printf), Java, Python, PHP, JavaScript и т. Д.

(В качестве примечания ... не все эти копии кода dtoa для Gay были обновлены, так как PHP использовал старую версию strtod, которую он зависал при разборе 2.2250738585072011e-308. )

В общем, если вы будете делать вещи «очевидным» и простым способом, например, умножением на степень 10 и последующим преобразованием целого числа, вы потеряете небольшую степень точности, а некоторые результаты будут неточными ... но возможно, вы получите правильные первые 14 или 15 цифр. Гей-реализация dtoa () утверждает, что все цифры верны ... но в результате код довольно сложен для отслеживания. Перейдите к нижней части, чтобы увидеть сам strtod, вы можете увидеть, что он начинается с «быстрого пути», который просто использует обычную арифметику с плавающей точкой, но затем он обнаруживает, что этот результат неверен, и использует более надежный алгоритм с использованием bigints, который работает в все случаи (но медленнее).

Реализация имеет следующую цитату, которая может вас заинтересовать:

 * Inspired by "How to Print Floating-Point Numbers Accurately" by
 * Guy L. Steele, Jr. and Jon L. White [Proc. ACM SIGPLAN '90, pp. 112-126].

Алгоритм работает, вычисляя диапазон десятичных чисел, которые производят данное двоичное число, и, используя больше цифр, диапазон становится все меньше и меньше, пока вы не получите точный результат или не сможете правильно округлить до запрошенного числа цифр. .

В частности, из раздела 2.2 Алгоритм

Алгоритм использует точную рациональную арифметику для выполнения своих вычислений, чтобы не было потери точности. Для генерации цифр алгоритм масштабирует число так, чтобы оно имело форму 0.d ₁ d ₂ ..., где d ₁ , d ₂ , ..., цифры основания B. Первая цифра вычисляется путем умножения масштабированного числа на выходную базу B и взятия целочисленной части. Остаток используется для вычисления остальных цифр с использованием того же подхода.

Затем алгоритм может продолжаться до тех пор, пока не получит точный результат (что всегда возможно, поскольку числа с плавающей запятой являются основанием 2, а коэффициент 2 равен 10) или пока он не будет иметь столько цифр, сколько требуется. Статья продолжает доказывать правильность алгоритма.

---

Также обратите внимание, что не все реализации printf основаны на dtoa Гея, это просто очень распространенная реализация, которая часто копируется.

Answer 2

Ни в стандарте C, ни в C ++ не прописан определенный алгоритм для таких вещей. Поэтому невозможно ответить, как printf делает это.

Если вы хотите узнать пример реализации printf, вы можете посмотреть здесь: http://sourceware.org/git/?p=glibc.git;a=blob;f=stdio-common/vfprintf.c и здесь: http://sourceware.org/git/?p=glibc.git;a=blob;f=stdio-common/printf_fp.c

Answer 3

Существуют различные способы безошибочного преобразования чисел с плавающей запятой в десятичные. (Точно или с округлением до желаемой точности).

Один из методов заключается в использовании арифметики, преподаваемой в начальной школе. C предоставляет функции для работы с числами с плавающей запятой, такими как frexp, которая разделяет дробь (также называемую значимым, часто ошибочно называемым мантиссой) и показателем степени. Учитывая число с плавающей запятой, вы можете создать большой массив для хранения десятичных цифр, а затем вычислить цифры. Каждый бит в дробной части числа с плавающей запятой представляет некоторую степень двойки, определяемую показателем степени в числе с плавающей запятой. Таким образом, вы можете просто поставить «1» в массиве цифр, а затем использовать арифметику начальной школы, чтобы умножить или разделить ее необходимое количество раз. Вы можете сделать это для каждого бита, а затем добавить все результаты, и сумма представляет собой десятичное число, равное числу с плавающей запятой.

Коммерческие printf реализации будут использовать более сложные алгоритмы. Обсуждение их выходит за рамки вопросов и ответов о переполнении стека. Основным документом по этому вопросу является Правильно округленные двоично-десятичные и десятично-двоичные преобразования . Автор David M. Gay . (Копия, по-видимому, доступна здесь , но, похоже, она размещена третьей стороной; я не уверен, насколько она официальна или надежна. Поиск в Интернете может привести к появлению других источников.) Более поздний статья с алгоритмом преобразования двоичного числа с плавающей запятой в десятичное с кратчайшим числом цифр, необходимым для однозначного различения значения: Печать чисел с плавающей запятой: всегда корректный метод , автор Марк Андриско, Ранджит Джхала и Сорин Лернер .

Одним из ключей к тому, как это делается, является то, что printf будет использовать не только формат с плавающей запятой и его операции для выполнения работы. Он будет использовать некоторую форму арифметики с расширенной точностью, либо работая с частями числа с плавающей запятой в целочисленном формате с большим количеством битов, разделяя число с плавающей запятой на части и используя несколько чисел с плавающей запятой для работы с ним. или с использованием формата с плавающей точкой с большей точностью.

Обратите внимание, что первый шаг в вашем вопросе, кратный х в степени десять, уже имеет две ошибки округления. Во-первых, не все степени десяти точно представимы в двоичной форме с плавающей точкой, поэтому просто получение такой степени десяти обязательно имеет некоторую ошибку представления. Затем умножение x на другое число часто приводит к математическому результату, который не может быть точно представлен, поэтому его необходимо округлить до формата с плавающей запятой.