Finds two integers whose ratio is closest to the given floating point value

farey.go

// farey rational approximation

package main

import (
	"fmt"
	"math"
)

// x is value to find rational approximation of
//     x must be between 0 and 1
// n is max denominator
func farey(x float64, n uint) (uint, uint) {
	a, b, c, d := uint(0), uint(1), uint(1), uint(1)
	for b <= n && d <= n {
		mediant := float64(a+c) / float64(b+d)
		if x == mediant {
			if b+d <= n {
				return a + c, b + d
			} else if d > b {
				return c, d
			} else {
				return a, b
			}
		} else if x > mediant {
			a, b = a+c, b+d
		} else {
			c, d = a+c, b+d
		}
	}

	if b > n {
		return c, d
	} else {
		return a, b
	}
}

func reportFarey(x float64, n uint) {
	u, l := int(1), int(1)
	if math.Abs(float64(n)) < math.Abs(x) {
		fmt.Printf("|%v| is invalid: must be >= |%v|\n", n, math.Abs(x))
		return
	} else if x < -1 {
		ul, uu := farey(-1/x, n)
		u, l = -1*int(uu), int(ul)
	} else if x < 0 {
		uu, ul := farey(-1*x, n)
		u, l = -1*int(uu), int(ul)
	} else if x <= 1 {
		uu, ul := farey(x, n)
		u, l = int(uu), int(ul)
	} else {
		ul, uu := farey(1/x, n)
		u, l = int(uu), int(ul)
	}
	fmt.Printf("%v = %v / %v\n", x, u, l)
}

func main() {
	reportFarey(float64(1/math.Pi), uint(25))
	reportFarey(float64(-1/math.E), uint(100))
	reportFarey(float64(1/math.Sqrt2), uint(1000))
	reportFarey(float64(0), uint(1000))
	reportFarey(float64(1), uint(1000))
	reportFarey(float64(1300.5), uint(1000))
	reportFarey(float64(-1300.5), uint(1000))
}

// Output is
// 0.3183098861837907 = 7 / 22
// -0.36787944117144233 = -32 / 87
// 0.7071067811865476 = 408 / 577
// 0 = 0 / 1
// 1 = 1 / 1
// |1000| is invalid: must be >= |1300.5|
// |1000| is invalid: must be >= |1300.5|