Перевод из десятичной дроби в обыкновенную - варианты

[Deffe]

Какой алгоритм перевода конечной десятичной дроби, меньше единицы, заданной конечным набором цифр, в простую несократимую дробь является наиболее эффективным? Первое что приходит в голову - найти НОД данного числа и $10^k$ и сократить на него. Существуют ли другие подходы? Кроме того, дана оценка знаменателя $M<\sqrt{10^k/2}$, не знаю как с ее помощью можно что то сделать.

[venco]

Можно не искать НОД по общему алгоритму, т.к. знаменатель делится только на 2 и 5 из простых делителей. Проще делить только на них, причём деление на 2 отлично оптимизируется, да и на константу 5 компилятор может делить быстрее, чем на произвольное число.

[Andrey A]

Deffe в сообщении #996019 писал(а):

Первое что приходит в голову - найти НОД данного числа и $10^k$ и сократить на него.

Если для нахождения НОД используется алгоритм Евклида, то записывайте заодно в строку неполные частные. Получите конечную последовательность знаков $a_1, a_2, ..., a_n$. Стройте теперь новую последовательность $u_n$:

$u_1=a_n$
$u_2=u_1a_{n-1}+1$
$u_3=u_2a_{n-2}+u_1$
$u_4=u_3a_{n-3}+u_2$ и т.д. Последние два члена образуют знаменатель и числитель нужной Вам дроби.

upd
Для конечных легче разделить на НОД, а для периодических может пригодиться.