Bits and Pieces: Fraction(): approximate a number as a common fraction

The Fraction() function approximates a number as a common fraction. For example, Fraction( 0.625, 16 ) = 5/8. Here 0.625 is the number being approximated and 16 is the maximum allowed denominator of the result.

The function considers the maximum denominator only as a limit it cannot exceed, but uses the denominator that gives the most precise approximation. For example, Fraction( 3.1415926, 100 ) = 3 1/7, because 3 1/7 is the most precise approximation of 3.1415926 among all fractions with denominators less than 100; only 106 will give better precision.

The basis behind the algorithm is the theory of continued fractions and the calculated fraction is a convergent of continued fraction. What's good about this is that a convergent is guaranteed to be the most precise approximation of a number among all fractions with denominators less than a given value. This means the function is very good when you care about precision.

It may be not as good if you care about easy-to-understand fractions. Though 5/17" may be quite a precise representation of some length, it's not very usable, because there's no easy way to divide an inch into 17 equal parts. Next time I'll write a function that takes this into consideration and limits the possible results to practicable ones.

The function actually consists of two functions and requires the CGD() function. It also contains an unpleasant hack to get the fractional part of the number; see below. The first function:

Fraction( number, maximum denominator )

Convergent( number - Int( number ); 
  1; 0; Int( number ); 1; maximum denominator )

is actually a wrapper; as you can see, it massages the number and passes it along with some other parameters to the Convergent() function that does all the work:

Convergent( number, P2, Q2, P1, Q1, maximum denominator )

Let( [ 
  A = Int( 1 / number );
  Q = A * Q1 + Q2 ];

  If( Q > maximum denominator;
    Let( [
      divisor = GCD( P1; Q1 ); 
      enumerator = Div( P1; divisor );
      denominator = Div( Q1; divisor );
      integer part = Div( enumerator; denominator );
      fractional part = Mod( enumerator; denominator ) ];

      If( integer part = 0 and fractional part = 0; 0;

        Case( integer part ≠ 0; integer part )
        & Case( integer part ≠ 0 and fractional part ≠ 0; " " )
        & Case( fractional part ≠ 0; fractional part & "/" & denominator ) ) );

    Let( P = A * P1 + P2;
      Convergent( Abs( 1 / number - A ); 
        P1; Q1; P; Q; maximum denominator ) ) ) )

The function is quite simple; more than a half of the code (the If() clause) is devoted to formatting the fraction. Yet it's technical and there's no way to explain what those P2 and Q1 are for without going into the theory. Unless users of your application are mathematicians, I'd suggest you to enable this function for full access accounts only.

The unpleasant hack

If you study the code carefully you'll see a strange piece of code:

Abs( 1 / number - A )

where A is:

A = Int( 1 / number )

This is a hack; this piece of code must get the fractional part of the number. FileMaker doesn't have a built-in function to do this, so I before I start writing this function, I typically calculated fractional part of a number using the Mod() function. Since Mod( number, divisor ) “returns the remainder after number is divided by divisor”, Mod( number, 1 ) should return the fractional part of number, right?

Not quite. Try to evaluate the following:

Mod( 1/(1/6), 1 )

It produces 1! If you check 1/(1/6) alone, it yield 6... does this mean Mod( 6, 1 ) = 1? What actually happens is that 1/(1/6) isn't equal to 6 exactly; it's 5.9999999.... When calculated on its own, the value is internally rounded to 6, but when used in Mod(), it's calculated with full precision, yields 0.9999999... as a result and then rounded to 1 the same way 5.9999999... is rounded to 6.

I'm not yet sure how to calculate fractional part; I've tried to test whether Mod( number, 1 ) = 1, but it doesn't work for obvious reasons: the numbers are not equal at that moment, because the rounding happens somewhere else. I also tried to calculate fractional part using number - Int( number ) and though this is better, sometimes FileMaker thinks Int( number ) is greater than number (!) and the function fails again. I hate shamanic “programming” but must admint that using Abs() seems to work, though I don't yet see why.

As soon as I'm ready with a better version, I'll post an update.

Test for the Function Tester

Assert Equals( Fraction( 1/2, 10 ), "1/2" ) &
Assert Equals( Fraction( 2/2, 10 ), "1" ) &
Assert Equals( Fraction( 3/2, 10 ), "1 1/2" ) &
Assert Equals( Fraction( 4/2, 10 ), "2" ) &
Assert Equals( Fraction( 5/2, 10 ), "2 1/2" ) &

Assert Equals( Fraction( 1/12, 12 ), "1/12" ) &
Assert Equals( Fraction( 2/12, 12 ), "1/6" ) &
Assert Equals( Fraction( 3/12, 12 ), "1/4" ) &
Assert Equals( Fraction( 4/12, 12 ), "1/3" ) &
Assert Equals( Fraction( 5/12, 12 ), "5/12" ) &
Assert Equals( Fraction( 6/12, 12 ), "1/2" ) &
Assert Equals( Fraction( 7/12, 12 ), "7/12" ) &
Assert Equals( Fraction( 8/12, 12 ), "2/3" ) &
Assert Equals( Fraction( 9/12, 12 ), "3/4" ) &
Assert Equals( Fraction( 10/12, 12 ), "5/6" ) &
Assert Equals( Fraction( 11/12, 12 ), "11/12" ) &
Assert Equals( Fraction( 12/12, 12 ), "1" ) &

Assert Equals( Fraction( 0.001, 1 ), "0" ) &
Assert Equals( Fraction( 0.999, 1 ), "1" ) &
 
Assert Equals( Fraction( PI, 100 ), "3 1/7" ) & // Archimedes: 22/7
Assert Equals( Fraction( PI, 1000 ), "3 16/113" ) // 355/113

Technorati Tags: FileMaker

3 Comments

Thanks! This really helped. I have run into some strange results where the function seems to be having trouble. I can send along the file if you are interested/have time.
Cheers.

Posted by: jh | December 29, 2006 at 01:27 AM