golden ratio algorithms


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Source Code

-- Golden Ratio approximation algorithms
-- See: http://en.wikipedia.org/wiki/Golden_ratio

-- Fuzzy equality test
local function fuzzy_equal(a, b, eps) return (math.abs(a - b) < eps) end

-- Computes an approximate value of the Golden Ratio
-- Using a root based iteration.
-- See: http://en.wikipedia.org/wiki/Golden_ratio#Alternative_forms
-- seed    : (optional) seed to start the computation (defaults to 1)
-- acc     : (optional) approximation accuracy (defaults to 1E-8)
-- returns : an approximation of the Golden Ratio
local function golden_ration_root_iteration(seed, acc)
  local phi, phi2 = seed or 1
  acc = acc or 1e-8
  repeat
    phi2 = phi
    phi = math.sqrt(1 + phi)
  until fuzzy_equal(phi, phi2, acc) 
  return phi
end

-- Computes an approximate value of the Golden Ratio
-- Using a fractional based iteration.
-- See: http://en.wikipedia.org/wiki/Golden_ratio#Alternative_forms
-- seed    : (optional) seed to start the computation (defaults to 1)
-- acc     : (optional) approximation accuracy (defaults to 1E-8)
-- returns : an approximation of the Golden Ratio
local function golden_ration_fractional_iteration(seed, acc)
  local phi, phi2 = seed or 1
  acc = acc or 1e-8
  repeat
    phi2, phi = phi, 1 + (1 / phi)
  until fuzzy_equal(phi, phi2, acc) 
  return phi
end

-- Computes an approximate value of the Golden Ratio
-- Using Babylonian method.
-- See: http://en.wikipedia.org/wiki/Golden_ratio#Decimal_expansion
-- seed    : (optional) seed to start the computation (defaults to 1)
-- acc     : (optional) approximation accuracy (defaults to 1E-8)
-- returns : an approximation of the Golden Ratio
local function golden_ration_babylonian_iteration(seed, acc)
  local phi, phi2 = seed or 1
  acc = acc or 1e-8
  repeat
    phi2 = phi
    phi = (phi * phi + 1) / (2 * phi - 1)
  until fuzzy_equal(phi, phi2, acc)
  return phi
end

-- Computes an approximate value of the Golden Ratio
-- Using a Newton-Raphson solver (implemented as an external dependency)
-- See: http://en.wikipedia.org/wiki/Golden_ratio#Calculation
-- seed    : (optional) seed to start the computation (defaults to 1)
-- acc     : (optional) approximation accuracy (defaults to 1E-8)
-- returns : an approximation of the Golden Ratio
local solve = require 'lib.newtonraphson'
local function golden_ration_equation(seed, acc)
  return solve(function(x) return x * x - x - 1 end, seed, acc)
end

-- Computes an approximate value of the Golden Ratio
-- Using Fibonacci series (implemented as an external dependency).
-- See: http://en.wikipedia.org/wiki/Golden_ratio#Relationship_to_Fibonacci_sequence
-- seed    : (optional) seed to start the computation (defaults to 2)
-- acc     : (optional) approximation accuracy (defaults to 1E-8)
-- returns : an approximation of the Golden Ratio
local fib = (require 'lib.fib')
local function golden_ration_fibonacci_iteration(seed, acc)
  seed, acc = seed or 2, acc or 1e-8
  assert(seed >= 2, 'order must be greater than 1')
  local denum, num = fib(seed), fib(seed + 1)
  local phi, phi2 = num / denum
  repeat
    phi2 = phi
    seed = seed + 1    
    denum, num = num, fib(seed)
    phi = num / denum
  until fuzzy_equal(phi, phi2, acc)
  return phi
end

return {
  root       = golden_ration_root_iteration,
  fractional = golden_ration_fractional_iteration,
  babylonian = golden_ration_babylonian_iteration,
  equation   = golden_ration_equation,
  fibonacci  = golden_ration_fibonacci_iteration
}
-- Tests for golden_ratio.lua
local GN = require 'golden_ratio'

local total, pass = 0, 0

local function dec(str, len)
  return #str < len
     and str .. (('.'):rep(len-#str))
      or str:sub(1,len)
end

local function run(message, f)
  total = total + 1
  local ok, err = pcall(f)
  if ok then pass = pass + 1 end
  local status = ok and 'PASSED' or 'FAILED'
  print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

local function fuzzyEqual(a, b, eps)
  local eps = eps or 1e-8
  return (math.abs(a - b) < eps)
end

-- The real Gold Number value
GN.Value = (1 + math.sqrt(5)) / 2

run('Test for GN computation', function()
  assert(fuzzyEqual(GN.equation(1,1e-8), GN.Value))
  assert(fuzzyEqual(GN.root(1, 1e-8), GN.Value))
  assert(fuzzyEqual(GN.fractional(1, 1e-8), GN.Value))
  assert(fuzzyEqual(GN.fibonacci(2, 1e-8), GN.Value))
  assert(fuzzyEqual(GN.babylonian(2, 1e-8), GN.Value))
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
  :format(total, pass, total-pass, (pass*100/total)))