C++: перевод простой дроби в десятичную

125

20 декабря 2021, 04:00

Подскажите пожалуйста с алгоритмом:

У меня есть простая дробь, которая хранится в виде пары целых чисел

using fraction_t = std::pair<int, int>

Требуется, если это позволяет знаменатель (т.е. он может быть представлен в виде 2^n * 5^m), перевести простую дробь в десятичную.

Задачу можно решить в лоб, т.е. итерационно знаменатель разделить на 5 и 2, пока это возможно и если после всего этого останется 1 - можно формировать десятичную дробь

int multiplier = 1;
while (value % 2 == 0)
{
    value /= 2;
    multiplier *= 2;
}
while (value % 5 == 0)
{
    value /= 5;
    multiplier *= 5;
}
if (value == 1){// десятичная дробь}

А есть ли возможность как-то более оптимально выполнить такую задачу?

Answer 1

Показатель степени для двойки в делителе на большинстве процессоров можно найти за одну инструкцию — bsf (Bit Scan Forward, она же ctz count trailing zeros). В gcc для этого есть встроенная (built-in) функция — ffs() (Find first set), но надо помнить, что биты в ней считаются с единицы. Соответственно нахождение показателя степени двойки, получение частного и множителя будет выглядеть как-то так:

#define _GNU_SOURCE 
#include <strings.h>
// ...
assert (value!=0);
unsigned n = ffs(value) - 1;
value >>= n;
multiplier = 1<<n;

В С++20 также появится стандартный вариант операции, countr_zero():

#include <bit>
//...
unsigned value;
//...
assert (value!=0);
unsigned n = countr_zero(value);

Answer 2

Проверка остатка на два, лучше заменить битовыми операциями, тогда будет быстрее работать. При наличии битовых операций, можно проверить делимость на 2 (value & 1)==0 на 4 (value & 3)==0 на 8 (value & 7)==0 это всё можно сгрупировать...

 while (true) {
   switch (value & 7) {       
     case 4:/*100*/;  value >>= 2; multiplier <<=2;  
        continue; 
     case 6 /*110*/:; 
     case 2:/*010*/; value >>= 1; multiplier <<=1;  
         continue; 
     case 0:; 
      value >>= 3; multiplier <<=3;  
      countinue;
    }
  break;
  }

Для 8 - будет 4 ветки и 4 случая break, для 16 будет 8 веток, и 8 случаев break. Возможно для 1,2,3 лучше массив, тогда проверка будет ещё проще. C двойкой вообще всё хорошо (то же самое через массив):

 int divs8[] = {0,1,0,2,0,2,0,3};
 while (value & 1) {
     multiplier <<=divs8[value & 7];//можно опустить
     value >>= divs8[value & 7];
     }

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

Для 5, я бы сделал тоже несколько проверок аналогично. Два случая с пять - 25. У нас соответственно при делении на 25 будет 20 15 10 5 - нужно делить на 5, а 25 - на 25. Ветку 20 и 10 можно убрать, если проверено что на 2 не делится. Т.е.

while (true) {
switch (value % 25) {       
   //case 20 :;     case 10 :;
   case 15 :;    
     value /=5; multiplier*=5;  
     continue;          
    case 0:; 
      value /=25; multiplier*=25;  
     continue; 
     }
    break;
    }

Данный алгоритм будет замечательно работать на числах меньше 50, хорошо до 100. На больших вероятно будет проигровать - прийдется добавить больше проверок.

Да, увидел multiplier можно вынести из цикла int multipler = value0 / value; добавит быстродействие.

Если это соревнование - то суть - сделать как можно меньше проверок.

Answer 3

Если речь об оптимизации алгоритма, в случае больших чисел, то можно, например, так:

int value0=value;
for(int m  : { 152587890625, 390625, 625, 25, 5, //5^16, 5^8, 5^4, 5^2, 5^1
               4294967296, 65536, 256, 16, 4, 2  //2^32 , 2^16,...
             })
    if( value  %m ==0 )
        value /= m;
int multipler = value0 / value; // ненужно умножать на каждой итерациии. (можно один раз.)

Но в случае маленьких чисел, может быть дольше.