Newsgroup: it.comp.lang.c++
Titolo: numeri razionali

Una discreta presentazione si trova alla URL
http://forum.swarthmore.edu/dr.math/problems/lawson6.25.98.html
Uno fra i piu` semplici degli algoritmi, basato sulla
espansione in frazioni continue, si puo` concisamente
riassumere cosi`:
struct Fraction
{
    long num;
    long denom;
    Fraction(long num, long denom): num(num), denom(denom) {}
    static Fraction toFract(double val, double Precision);
    Fraction operator+(Fraction f)
    {
        return Fraction(num*f.denom+denom*f.num, denom*f.denom);
    }
};
Fraction Fraction::toFract(double val, double Precision)
{    // find nearest fraction
 int intPart = (int)val;
 val -= (double)intPart;
 Fraction low(0, 1);           // "A" = 0/1
 Fraction high(1, 1);          // "B" = 1/1
 for (int i = 0; i < 100; ++i)
 {
  double testLow = low.denom * val - low.num;
  double testHigh = high.num - high.denom * val;
  if (testHigh < Precision * high.denom)
   break; // high is answer
  if (testLow < Precision * low.denom)
  {  // low is answer
   high = low;
   break;
  }
  if (i & 1)
  {  // odd step: add multiple of low to high
   double test = testHigh / testLow;
   int count = (int)test;    // "N"
   int num = (count + 1) * low.num + high.num;
   int denom = (count + 1) * low.denom + high.denom;
   if ((num > 0x8000) ||
       (denom > 0x10000))
    break;
   high.num = num - low.num;  // new "A"
   high.denom = denom - low.denom;
   low.num = num;             // new "B"
   low.denom = denom;
  }
  else
  {  // even step: add multiple of high to low
   double test = testLow / testHigh;
   int count = (int)test;     // "N"
   int num = low.num + (count + 1) * high.num;
   int denom = low.denom + (count + 1) * high.denom;
   if ((num > 0x10000) ||
       (denom > 0x10000))
    break;
   low.num = num - high.num;  // new "A"
   low.denom = denom - high.denom;
   high.num = num;            // new "B"
   high.denom = denom;
  }
 }
 return Fraction(intPart, 1) + high;
}
ed ecco il caso di test:
long main(long argc, char* argv[])
{
    long num, den;
    printf("Enter num den:");
    scanf("%d %d", &num, &den);
    double m = double(num)/den;
    printf("%d/%d -> %f\n", num, den, m);
    double pr = 0.1;
    for(int i=0; i<5; ++i) {
        printf("Precision: %f ", pr);
        Fraction f = Fraction::toFract(m, pr);
        printf("%d/%d\n", f.num, f.denom);
        pr = pr / 10.0;
    }
 return 0;
}
con un esempio:
Enter num den:97 435
97/435 -> 0.222989
Precision: 0.100000 1/4
Precision: 0.010000 3/13
Precision: 0.001000 2/9
Precision: 0.000100 31/139
Precision: 0.000010 64/287
Precision: 0.000001 97/435
Precision: 0.000000 97/435
Precision: 0.000000 97/435
Alex







 Alex
Hai il virus del quadruplo post.  Attento!
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Univ. of Padova, Dept. of Physics - Padova, Italy            
lor...@pd.infn.it

 Hai il virus del quadruplo post.  Attento!
Grazie, stamattina ho notato quello che mi segnali.  Non
capisco proprio perche` il post sia partito simultaneamente
4 volte, anche perche` il post successivo invece, 10
minuti dopo, e` partito in copia singola.  Sospetto che
il glitch sia nel server di news che uso da casa, TIN,
che in effetti di stranezze ne fa tante e spesso.
Alex