psksvp · July 22, 2020 03:02
diff --git a/approximateFraction.swift b/approximateFraction.swift

 //  approximate the fraction of a real
 //  Created by psksvp on 22/7/20.

 print(approximateFraction(0.5))
 print(approximateFraction(0.5454))
 print(approximateFraction(0.75))
 print(approximateFraction(0.333333))
 print(approximateFraction(0.888888888888))
 print(approximateFraction(0.0123456789))
 print(approximateFraction(3.14))
 print(approximateFraction(3.14159265359))

 /*
 rewrite from C code
 https://www.ics.uci.edu/~eppstein/numth/frap.c
 The comment below was copied from the comment in the above C code.
 ** find rational approximation to given real number
 ** David Eppstein / UC Irvine / 8 Aug 1993
 **
 ** With corrections from Arno Formella, May 2008
 **
 ** usage: a.out r d
 **   r is real number to approx
 **   d is the maximum denominator allowed
 **
 ** based on the theory of continued fractions
 ** if x = a1 + 1/(a2 + 1/(a3 + 1/(a4 + ...)))
 ** then best approximation is found by truncating this series
 ** (with some adjustments in the last term).
 **
 ** Note the fraction can be recovered as the first column of the matrix
 **  ( a1 1 ) ( a2 1 ) ( a3 1 ) ...
 **  ( 1  0 ) ( 1  0 ) ( 1  0 )
 ** Instead of keeping the sequence of continued fraction terms,
 ** we just keep the last partial product of these matrices.
 */
 func approximateFraction(_ n: Double, maxDenominator:Int = 1024) -> (Int, Int, Double)
 {
  var x = n
  var ai = Int(n)
  var m00 = 1
  var m01 = 0
  var m10 = 0
  var m11 = 1
  
  while(m10 * ai + m11 <= maxDenominator)
  {
    var t = m00 * ai + m01
    m01 = m00
    m00 = t
    t = m10 * ai + m11
    m11 = m10
    m10 = t
    if x == Double(ai)
    {
      break     // div by 0
    }
    x = 1 / (x - Double(ai))
    if x > 0x7FFFFFFF
    {
      break
    }
    ai = Int(x)
  }
  return (m00, m10, n - Double(m00) / Double(m10))
 }

	// approximate the fraction of a real
	// Created by psksvp on 22/7/20.

	print(approximateFraction(0.5))
	print(approximateFraction(0.5454))
	print(approximateFraction(0.75))
	print(approximateFraction(0.333333))
	print(approximateFraction(0.888888888888))
	print(approximateFraction(0.0123456789))
	print(approximateFraction(3.14))
	print(approximateFraction(3.14159265359))

	/*
	rewrite from C code
	https://www.ics.uci.edu/~eppstein/numth/frap.c
	The comment below was copied from the comment in the above C code.
	** find rational approximation to given real number
	** David Eppstein / UC Irvine / 8 Aug 1993
	**
	** With corrections from Arno Formella, May 2008
	**
	** usage: a.out r d
	** r is real number to approx
	** d is the maximum denominator allowed
	**
	** based on the theory of continued fractions
	** if x = a1 + 1/(a2 + 1/(a3 + 1/(a4 + ...)))
	** then best approximation is found by truncating this series
	** (with some adjustments in the last term).
	**
	** Note the fraction can be recovered as the first column of the matrix
	** ( a1 1 ) ( a2 1 ) ( a3 1 ) ...
	** ( 1 0 ) ( 1 0 ) ( 1 0 )
	** Instead of keeping the sequence of continued fraction terms,
	** we just keep the last partial product of these matrices.
	*/
	func approximateFraction(_ n: Double, maxDenominator:Int = 1024) -> (Int, Int, Double)
	{
	var x = n
	var ai = Int(n)
	var m00 = 1
	var m01 = 0
	var m10 = 0
	var m11 = 1

	while(m10 * ai + m11 <= maxDenominator)
	{
	var t = m00 * ai + m01
	m01 = m00
	m00 = t
	t = m10 * ai + m11
	m11 = m10
	m10 = t
	if x == Double(ai)
	{
	break // div by 0
	}
	x = 1 / (x - Double(ai))
	if x > 0x7FFFFFFF
	{
	break
	}
	ai = Int(x)
	}
	return (m00, m10, n - Double(m00) / Double(m10))
	}