October 2005 Problem 'nearfr' Analysis

by Bruce Merry

This problem seems quite straightforward, but there are a few details that need to be considered. The first is that trying all possible fractions will be too slow. However, for each denominator, some simple arithmetic will give the two numerators corresponding to the fractions lying on either side of the input fraction.

Secondly, you need to be sure that the fraction you return is reduced. This is easily handled by taking the solution with smallest denominator out of solutions with identical value. You also need to avoid fractions that are equal to the target but with a common factor.

Thirdly, if you use floating point numbers to hold fractions then finite precision may become a problem. There are a number of cases where fractions must be compared for equality (in particular, the smaller of two equidistant answers must be used). If you just use simple comparison, the test could be incorrect due to finite precision. I prefer to use a fraction class, with 64-integers for the numerator and denominator, and operations for addition, subtraction, comparison etc. that you learn at high school. The other alternative is to use a so-called "epsilon test": treating values as equal if they are within some small value (epsilon) of each other. Epsilon must be chosen with some care, to avoid accidentally treating different values as equal: the difference between

32762/32765-1/32767
and
32763/32766-1/32764
is only 5.2e-18, and if you use double precision it will not be computed correctly. It turns out that for all the test cases used, double precision is enough, but to be safe you should use long double and set epsilon to around 1e-18 (don't use the C macro LDBL_EPSILON as is; this is the size of the least significant bit, and usually errors are somewhat larger due to accumulation of errors).

Here is Chinese sophomore Yuxi Chen's extraordinarily compact Pascal solution: 

var a, b, i, n, d: Longint;
procedure check (k: Longint);
begin
    if abs(a/b-n/d)>abs(k/i-n/d) then begin
	a:=k;
	b:=i;
    end;
end;

begin
    assign(input,'nearfr.in');reset(Input);
    assign(output,'nearfr.out');rewrite(output);
    read(n,d);
    a:=1;b:=1;
    for I:=1 to 32767 do begin
	if n*i mod d = 0 then begin
            check(n*i div d-1);
            check(n*i div d+1);
        end else begin
            check(n*i div d);
            check(n*i div d+1);
        end;
    end;
    writeln(a,' ',b);
    close(input);close(output);
end.

And here is USA senior George Washington's (that's his real name) expressive Java solution: 

import java.io.*;
import java.util.*;

public class nearfr {
    public static void main (String [] args) throws IOException {
        RandomAccessFile fin = new RandomAccessFile ("nearfr.in", "r");
        PrintWriter fout = new PrintWriter (new BufferedWriter (new FileWriter ("nearfr.out")));
        StringTokenizer st = new StringTokenizer (fin.readLine ());

        int N = Integer.parseInt (st.nextToken());
	int D=Integer.parseInt(st.nextToken());
	int temp;
        int[] best={1,1};
        double bestdiff = Math.abs (((double)best[0])/best[1]-((double)N)/D);
        for (int i=1; i < 32768; i++) {
            temp = (i*N)/D;
            if (temp/((double)i) != N/((double)D)) {
                if(Math.abs(((double)(temp))/i - ((double)N)/D)<bestdiff) {
                    best[0] = temp;
                    best[1] = i;
                    bestdiff = Math.abs(((double)best[0])/best[1]-((double)N)/D);
                }
                if(Math.abs(((double)(temp+1))/i - ((double)N)/D)<bestdiff) {
                    best[0] = temp+1;
                    best[1] = i;
                    bestdiff = Math.abs (((double)best[0])/best[1] - ((double)N)/D);
                }
            }
        }
        fout.println (best[0]+" "+best[1]);
        fout.flush();
    }
}