Проблемы точности при преобразовании десятичного числа в его рациональный эквивалент

Question

Проблемы точности при преобразовании десятичного числа в его рациональный эквивалент

У меня есть проблема конвертации двойного (скажем, N) в p / q форму (рациональную форму), для этого у меня есть следующая стратегия:

Умножьте двойной N на большое число, скажем, $ k = 10 ^ {10} $
затем p = y*k а также q = k
принимать gcd(p,q) и найти p = p/gcd(p,q) а также q = p/gcd(p,q)

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

Я попробовал это сделать иначе: (Я использовал большое число 10 ^ k вместо 100)

if(abs(y*100 - round(y*100)) < 0.000001) y = round(y*100)/100

Но этот подход также не дает правильного представления все время.

Есть ли способ, которым я мог бы выполнить эквивалентное преобразование из двойного в p / q?

0

c++double rational-number

Решение

Другие решения

есть проблема конвертации двойного (скажем, N) в п / д форму
… когда N = 8,2

Типичный double не может кодировать 8.2 именно так. Вместо ближайшего представимого double около

8.19999999999999928945726423989981412887573...
8.20000000000000106581410364015027880668640...  // next closest

Когда код делает

double N = 8.2;

Это будет 8.19999999999999928945726423989981412887573... это превращается в рациональную форму.

Умножьте двойной N на большое число, скажем, $ k = 10 ^ {10} $

Это может переполнить double, Первым шагом должно быть определение того, double большой, в этом случае, это целое число.

Не умножайте на некоторую степень 10 как double конечно использует двоичную кодировку. Умножение на 10, 100 и т. Д. Может привести к ошибке округления.

C реализации double в подавляющем большинстве случаев использовать двоичную кодировку, так что FLT_RADIX == 2,

Тогда каждый конечный double x имеет значение, которое представляет собой долю целого числа от некоторой степени 2: двоичная дробь DBL_MANT_DIG цифры @ Ричард Криттен. Это часто 53 двоичные цифры.

Определить показатель степени double, Если достаточно большой или x == 0.0, double это целое число.

В противном случае масштабируйте числитель и знаменатель по DBL_MANT_DIG, В то время как числитель четный, делим пополам числитель и знаменатель. Как denominator является степенью 2, другие простые значения не нужны для упрощения рассмотрения.

#include <float.h>
#include <math.h>
#include <stdio.h>

void form_ratio(double x) {
double numerator = x;
double denominator = 1.0;
if (isfinite(numerator) && x != 0.0) {
int expo;
frexp(numerator, &expo);
if (expo < DBL_MANT_DIG) {
expo = DBL_MANT_DIG - expo;
numerator = ldexp(numerator, expo);
denominator = ldexp(1.0, expo);
while (fmod(numerator, 2.0) == 0.0 && denominator > 1.0) {
numerator /= 2.0;
denominator /= 2.0;
}
}
}
int pre = DBL_DECIMAL_DIG;
printf("%.*g --> %.*g/%.*g\n", pre, x, pre, numerator, pre, denominator);
}

int main(void) {
form_ratio(123456789012.0);
form_ratio(42.0);
form_ratio(1.0 / 7);
form_ratio(867.5309);
}

Выход

123456789012 --> 123456789012/1
42 --> 42/1
0.14285714285714285 --> 2573485501354569/18014398509481984
867.53089999999997 --> 3815441248019913/4398046511104

1

Источник

Accepted Answer

Арифметика с плавающей точкой очень сложна. Как уже упоминалось в комментариях, часть трудностей заключается в том, что вам нужно представлять свои числа в двоичном виде.

Например, число 0.125 может быть представлено точно в двоичном виде:

0.125 = 2^-3 = 0b0.001

Но число 0,12 не может.

До 11 значимых цифр:

0.12 = 0b0.00011110101

Если это преобразовать обратно в десятичную, то ошибка становится очевидной:

0b0.00011110101 = 0.11962890625

Так что если вы напишите:

double a = 0.2;

Что на самом деле делает машина, так это находит наиболее близкое двоичное представление 0.2, которое может храниться в двойном типе данных. Это приближение, поскольку, как мы видели выше, 0.2 не может быть точно представлено в двоичном виде.

Один из возможных подходов состоит в том, чтобы определить «эпсилон», который определяет, насколько близко ваше число может быть к ближайшей представимой двоичной плавающей запятой.

Вот хорошая статья о плавающих точках:

https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/

1