Преобразовать число с плавающей точкой в простую дробь., Нужен оптимальный алгоритм пересчета Опции

[M_Andrey]

Встала задача преобразовать число single/double в простую дробь.
Классическое правило:
1.2345 = 12345 / 10000
Находим наибольший общий делитель НОД(12345,10000)=5 и сокращаем дробь:
12345 / 10000 = 2469 / 2000
Еще нашел способ:

CODE

d = 0.12345; // Исходная дробь, может быть любой
a0 = 0; a1 = 1; b0 = 1; b1 = 0;
while(не_достигнута_нужная точность)
{
N = Floor(d);
a = N * a1 + a0;
b = N * b1 + b0;
printf("%d / %d = %f\n", a, b, a/b);
a0 = a1; a1 = a; b0 = b1; b1 = b;
d = 1/(d - N);
}

Первый способ дает неоптимальные числа (слишком большие) при той-же точности, у второго в алгоритме есть дыры типа деления на ноль. Может кто-то уже проходил этот путь? Что посоветуете?

[_pv]

для чего, если не секрет?

1.2345 = 1.2345 / 1 = 2.469 / 2 = 3.7035 / 3 = ... = 457.9995/371 ~ 458/371 = ... = 2469 / 2000
правда очень не быстро, зато найдёт минимальное число с любой заданной точностью.

[M_Andrey]

для чего, если не секрет?

Нужно вводить коэффициент редуктора двигателя в частотник из верхнего софта.

[Maverick]

Нужно вводить коэффициент редуктора двигателя в частотник из верхнего софта.

посмотрите
MATLAB:

Код

rat(pi)
            ans = 3 + 1/(7 + 1/(16))
            rat(pi, 1e-12)
            ans = 3 + 1/(7 + 1/(16 + 1/(-294 + 1/(3 + 1/(-4 + 1/(5))))))
            [n,d]=rat(pi);
            [n d]
            ans =   355     113
            [n, d]=rat(pi, 1e-12);
            [n d]
            ans =    5419351    1725033
            s = rats(pi)
            s = 355/113
            s = rats(pi, 26)
            s = 5419351/1725033

Причина редактирования: Избыточное цитирование

[M_Andrey]

Если-бы мне надо было сделать это один раз, то я бы на калькуляторе посчитал и ввел один раз. Но эти коэффициенты наладчики будут вводить на объектах из верхнего софта (HMI SCADA), программа ПЛК получает число (double), пересчитывает в числитель и знаменатель, и передает их частотнику.

[_pv]

эти коэффициенты наладчики будут вводить на объектах из верхнего софта (HMI SCADA), программа ПЛК получает число (double), пересчитывает в числитель и знаменатель, и передает их частотнику.

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

double n = 1.2345;
double maxErr = 0.0001;

int denom = 1;
double err = n;
for(int i = 1; i <= 30000; i++){
double e = abs((double)((int)(n * i + 0.5)) / i - n );
if (e < err){ err = e; denom = i;}
if (e < maxErr) break;
}

получившаяся дробь: (n * denom + 0.5) / denom

[Tanya]

Встала задача преобразовать число single/double в простую дробь.
Что посоветуете?

https://ru.wikipedia.org/wiki/%D0%9D%D0%B5%...%BE%D0%B1%D1%8C

[M_Andrey]

https://ru.wikipedia.org/wiki/%D0%9D%D0%B5%...%BE%D0%B1%D1%8C

Не пойму как непрерывную дробь применить в моем случае.
PS. А вот "подходящая дробь" мой случай Спасибо.

[Maverick]

Не пойму как непрерывную дробь применить в моем случае.
PS. А вот "подходящая дробь" мой случай Спасибо.

посмотрите там алгоримтм и программа правда на PHP

[M_Andrey]

PS. А вот "подходящая дробь" мой случай Спасибо.

Оказалось что второй способ в моем первом посте и есть реализация "подходящей дроби".
Вот только беда в том что постоянное деление (1/х) в каждой итеррации приводит к погрешности при вычислении даже конечной дроби.

[jcxz]

Встала задача преобразовать число single/double в простую дробь.
Классическое правило:
1.2345 = 12345 / 10000
...
Может кто-то уже проходил этот путь? Что посоветуете?

Теперь разложите числитель и знаменатель на простые сомножители и сократите общую часть их.
Получите числитель и знаменатель в виде: 2^K1 * 3^K2 * 5^K3 * 7^K4... (где ^ - возведение в степень). Выберите минимальную степень из каждой пары Kn и поделите на неё.

[M_Andrey]

Теперь разложите числитель и знаменатель на простые сомножители и сократите общую часть их.
Получите числитель и знаменатель в виде: 2^K1 * 3^K2 * 5^K3 * 7^K4... (где ^ - возведение в степень). Выберите минимальную степень из каждой пары Kn и поделите на неё.

А как их искать - перебором? Мне нужен машинный алгоритм.

[jcxz]

А как их искать - перебором? Мне нужен машинный алгоритм.

Гуглите "решето Сундарама". Быстрый алгоритм поиска всех простых чисел не превышающих некоторого N.
Далее, если математику в школе учили, находите квадратный корень от числа, которое надо разложить на множители, и Сундараму задаёте значение корня в качестве предела N.

[XVR]

Теперь разложите числитель и знаменатель на простые сомножители и сократите общую часть их.

Это ровно то, что ТС сделал и описал в самом первом сообщении темы.

[jcxz]

Это ровно то, что ТС сделал и описал в самом первом сообщении темы.

Если он уже это сделал, то больше делать нечего, зачем бы тогда он спрашивал? Вы почитайте заголовок топика.