home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / 17818 < prev    next >
Encoding:
Text File  |  1993-01-07  |  2.3 KB  |  95 lines
  1. Xref: sparky sci.math:17818 sci.math.num-analysis:3750
  2. Path: sparky!uunet!usc!rpi!usenet.coe.montana.edu!news.u.washington.edu!zermelo.math.washington.edu!petry
  3. From: petry@zermelo.math.washington.edu (David Petry)
  4. Newsgroups: sci.math,sci.math.num-analysis
  5. Subject: Re: Approximating decimal fractions with proper fractions
  6. Date: 8 Jan 1993 04:07:18 GMT
  7. Organization: University of Washington, Mathematics, Seattle
  8. Lines: 80
  9. Distribution: na
  10. Message-ID: <1iiulmINNf0r@shelley.u.washington.edu>
  11. References: <C0ICCG.1BJ@hsi.com>
  12. NNTP-Posting-Host: zermelo.math.washington.edu
  13. Keywords: fraction, approximation, number theory
  14.  
  15. In article <C0ICCG.1BJ@hsi.com> rogerh@code3 (Roger Harrison) writes:
  16. >I am looking for an algorithm (preferably a computationally cheap one)
  17. >to approximate a decimal fraction with a proper fraction for display 
  18. >purposes.  The ideal algorithm would take a decimal fraction and the 
  19. >maximum number of digits in the result's denominator to determine the 
  20. >proper fraction (in numerator/denominator form) which best approximates 
  21. >the original decimal fraction.
  22. >
  23. >Stated more precisely:
  24. >
  25. >Given the decimal fraction F, ( F = x/y where x < y, y = 10^n, n >= 1 ),
  26. >what is the proper fraction, a/b, that best approximates F if b < 10^m, 
  27. >m >= 1, m <= n.
  28.  
  29.  
  30. The following short C program will do the trick.  It works by 
  31. converting a real number into a contiunued fraction.   I'm not sure
  32. if all C math libraries have the function modf, so there might be
  33. some problems on some systems.
  34.  
  35.  
  36. David Petry
  37.  
  38.  
  39.  
  40. #include <stdio.h>
  41. #include <math.h>
  42.  
  43.  
  44. #define rational struct rat_
  45. rational {
  46.     int a,b;
  47. };
  48.  
  49.  
  50.  
  51. #define rational_to_real(r)       ((double) (r).a / (double) (r).b)
  52.  
  53. rational
  54. real_to_rational(r, err) double r, err;            
  55. {
  56.     int  k=1, A;
  57.     rational rat1, rat2, rat3;
  58.     double r1, rA;
  59.     r1 = modf(r, &rA);
  60.     A = (int) rA;
  61.     rat1.a = 1; 
  62.     rat1.b = 0;
  63.     rat2.a = A; 
  64.     rat2.b = 1;
  65.     while ( (k++<40) && (fabs(rational_to_real(rat2) - r) > err) ) {
  66.         r1 = modf(1./r1, &rA);
  67.         A = (int) rA;
  68.         rat3.a = A*rat2.a + rat1.a;
  69.         rat3.b = A*rat2.b + rat1.b;
  70.         rat1 = rat2;
  71.         rat2 = rat3;                        
  72.     }
  73.     return rat2;                        
  74. }
  75.  
  76.  
  77.  
  78. void
  79. print_rat(rat) rational rat;            
  80. {
  81.     printf("%d/%d", rat.a, rat.b);        
  82. }
  83.  
  84. main ()                        {
  85.     double r;
  86.     rational rat;
  87.     while (1)                {
  88.         printf("Enter real >> ");
  89.         scanf("%lf", &r);
  90.         rat = real_to_rational(r, .00000001);
  91.         printf("%d/%d\n", rat.a, rat.b);    
  92.     }    
  93. }
  94.  
  95.