Число в дробь (convert double to fraction)

[Igor Makanu]

Ищу способ преобразовать вещественное число в дробь, нагуглил исходник https://stackoverflow.com/questions/26643695/converting-decimal-to-fraction-c

портировал под MQL (скрипт для проверки):

void OnStart()
  {
   double x = 1.0;
   double y = 4.0;
   string sfoo=foo(x/y);
   Print("sfoo = ",sfoo);
  }
//+------------------------------------------------------------------+
string foo(double value)
  {
   double integral=floor(value);
   double frac=value-integral;
   const long precision=1000000000; // This is the accuracy.
   long gcd_=gcd(long(round(frac*precision)),precision);
   long denominator=precision/gcd_;
   long numerator=long(round(frac*precision)/gcd_);
   string s=StringConcatenate(integral," + ",numerator," / ",denominator);
   return(s);
  }
//+------------------------------------------------------------------+
long gcd(long a,long b)
  {
   if(a == 0) return b; else if(b == 0)  return a;
   if(a < b)  return gcd(a, b % a); else  return gcd(b, a % b);
  }
//+------------------------------------------------------------------+

появились вопросы:

1. как ускорить этот алгоритм?

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

3. опционально, интересуют другие реализации convert double to fraction и convert double in continued fraction (преобразование числа в цепную дробь).

[Igor Makanu]

//+------------------------------------------------------------------+
//|  class CFraction                                                 |
//+------------------------------------------------------------------+
class CFraction
  {
private:
   int               integer;                      // целая часть
   double            original;                     // исходное число
   ulong             numerator,denominator,real;   // числитель, знаменатель и вещественная часть
   ulong             gcd(ulong u);                 // НОД
public:
   void              CFraction(double value);
   void     Print(){ Print("integer = ",integer," , numerator = ",numerator," , denominator = ",denominator);};
  };
//+------------------------------------------------------------------+
ulong CFraction::gcd(ulong u)
  {
   int shift=0;
   ulong swap,v=1e15;
   if(u == 0) return v;
   while(((u|v) &1)==0)
     {
      u>>= 1;
      v>>= 1;
      shift++;
     }
   while((u  &1)==0) u>>=1;
   do
     {
   while((v  &1)== 0) v>>=1;
   if(u>v) {swap=v; v=u; u=swap;}
   v-=u;
  }
while(v!=0);
return (u<<shift);
}
//+------------------------------------------------------------------+
CFraction::CFraction(double value)
{
   original = fabs(value);
   original-=floor(original);
   real=(ulong)NormalizeDouble(floor(original*1e15+0.5)-0.5,0);
   integer=value>=0.0?(int)floor(value):(int)ceil(value);
   original=value;
   ulong g = gcd(real);
   numerator=real/g;
   denominator=(ulong)1e15/g;
}
//+------------------------------------------------------------------+
void OnStart()
  {
   CFraction x(-1.425);
   x.Print();
  }
//+------------------------------------------------------------------+

[Maxim Kuznetsov]

Igor Makanu:

Ищу способ преобразовать вещественное число в дробь, нагуглил исходник https://stackoverflow.com/questions/26643695/converting-decimal-to-fraction-c

портировал под MQL (скрипт для проверки):

появились вопросы:

1. как ускорить этот алгоритм?

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

3. опционально, интересуют другие реализации convert double to fraction и convert double in continued fraction (преобразование числа в цепную дробь).

если любопытно, то есть мат.основа типа такой http://alexhvorost.narod2.ru/numbers/11.html (вообще автору респект и уважуха)

алгоритм влёт не вспомню :-( но из double надо поотдельности вытаскивать мантиссу и показатель (просто битовыми операциями) и с ними работать.

[Igor Makanu]

Maxim Kuznetsov:

если любопытно, то есть мат.основа типа такой http://alexhvorost.narod2.ru/numbers/11.html (вообще автору респект и уважуха)

алгоритм влёт не вспомню :-( но из double надо поотдельности вытаскивать мантиссу и показатель (просто битовыми операциями) и с ними работать.

теорию по цепным дробям уже с неделю читаю, спасибо

а смысл мантиссу юзать? я в лонги все перевел, затем лонг побитно по алгоритму наименьшего общего делителя преобразую в числитель и знаменатель (алгоритм НОД не оптимизирован, пока портировал из англ. Вики )

цепную дробь, еще поэкспериментирую, потом добавлю в топик, если есть готовые реализации этих алгоритмов, хотелось бы посмотреть

[Koldun Zloy]

Вот такой вариант:

struct Rational
{
   long Numerator;
   long Denominator;
   
   Rational() : Numerator(0), Denominator(0){}
   Rational( long N, long D ) : Numerator(N), Denominator(D){}
   Rational( const Rational& other ) : Numerator( other.Numerator ), Denominator( other.Denominator ){}
};

//+------------------------------------------------------------------+
Rational FloatToRational( double x )
{
   long numerator = (long)x;
   long denominator = 1;
   double endCondition = fabs( x / 100000000.0 );
   
   double z;
   while( fabs(z = x - double(numerator) / double(denominator)) > endCondition )
   {
      long Z = (long)round( 1.0 / z );
      if( Z < 0 ){
         numerator = numerator * -Z - denominator;
      }
      else {
         numerator = numerator * Z + denominator;
      }
      denominator *= abs(Z);
      long n = gcd( numerator, denominator ); //        Наибольший общий делитель
      if( n > 1 ){
         numerator /= n;
         denominator /= n;
      }
   }
   if( numerator < 0 && denominator < 0 ){
      numerator = -numerator;
      denominator = -denominator;
   }
   Rational result( numerator, denominator );
   return result;
}
//+------------------------------------------------------------------+
long gcd( long a, long b )
{
   long _a = abs( a );
   long _b = abs( b );
   while( _b != 0 )
   {
      long c = _a % _b;
      _a = _b;
      _b = c;
   }
   return _a;
}
//+------------------------------------------------------------------+
long abs( long x )
{
   if( x < 0 ){
      return -x;
   }
   return x;
}
//+------------------------------------------------------------------+