Ruby program to find all f_10 fixed points from http://math.stackexchange.com/questions/806844/if-f-nx-ff-n-1xthen-f-10x-x-x-in-0-1

f10.rb

#!/usr/bin/env ruby

class Fspace
  # single iteration
  def f(x)
    if x < 0
      return 0.5
    elsif x <= 0.5
      return x + 0.5
    elsif x <= 1.0
      return 2*(1.0 - x)
    end
    return 0.0
  end

  def f1(x)
    return f(x)
  end

  def f2(x)
    return f(f1(x))
  end

  def f3(x)
    return f(f2(x))
  end

  def f4(x)
    return f(f3(x))
  end

  def f5(x)
    return f(f4(x))
  end

  def f6(x)
    return f(f5(x))
  end

  def f7(x)
    return f(f6(x))
  end

  def f8(x)
    return f(f7(x))
  end

  def f9(x)
    return f(f8(x))
  end

  # tenfold iteration
  def f10(x)
    return f(f9(x))
  end
end

 # numerical precision
$eps = 1e-6

# compare for equality (within precision)
def eq(x, y)
  return (x - y).abs < $eps
end

# store found rational representations
$rat_cache = { }
$rat_lookups = 0
$rat_hits = 0

# return closest rational number (within precision)
def to_rat(x)
  xr = $rat_cache[x]
  $rat_lookups += 1
  if xr.nil?
    xr = find_rat(x)
    $rat_cache[x] = xr
  else
    $rat_hits += 1
  end
  return xr
end

# find x = q / r (for x from I = [0, 1])
def find_rat(x)
  if eq(x, 0)
    return [0, 1]
  elsif eq(x, 1)
    return [1, 1]
  end
  r_max = 10000
  r = 2
  while r < r_max
    r_i = 1.0 / r
    q = 1
    x_r = r_i
    while q < r
      if eq(x, x_r)
        return [q, r]
      end
      q += 1
      x_r += r_i
    end
    r += 1
  end
  return [x, 1]
end

# rational number pair to string
def rat_to_s(x)
  q, r = x
  s = "#{q}/#{r}"
  return s
end

# rational number pair to LaTeX string
def rat_to_latex(x)
  q, r = x
  s = "\\frac{#{q}}{#{r}}"
  return s
end

# add float to array if new, return position (1..n)
def fp_add(a, y)
  i = 1
  a.each do |x|
    if eq(x, y)
      return i
    end
    i += 1
  end
  a.push(y)
  return i
end

# string representation of set of rational numbers
def set_to_s(set)
  s = '{ '
  n_set = set.length
  i = 0
  while i < n_set
    x_r = set[i]
    x_rs = rat_to_s(x_r)
    s += x_rs
    i += 1
    if i < n_set
      s += ', '
    end
  end
  s += ' }' 
  return s
end

# LaTeX string representation of set of rational numbers
def set_to_latex(set)
  s = '\left\{ '
  n_set = set.length
  i = 0
  while i < n_set
    x_r = set[i]
    x_rs = rat_to_latex(x_r)
    s += x_rs
    i += 1
    if i < n_set
      s += ', '
    end
  end
  s += ' \right\}' 
  return s
end

# print the collected fixed points
def list(fps, fn)
  n_fp = fps.length
  i = 0
  s_fps = fps.sort
  f = Fspace.new
  set = [ ]
  while i < n_fp
    j = i + 1
    x = s_fps[i]
    y = f.send(fn, x)
    delta = (x - y).abs
    x_r = to_rat(x)
    x_rs = rat_to_s(x_r)
    set.push(x_r)
    puts "#{j}: #{x_rs} = #{x} -> #{y} (delta = #{delta})"
    i = j
  end
  set_s = set_to_s(set)
  set_latex = set_to_latex(set)
  puts "found #{n_fp} fixed points"
  puts "A = #{set_s}"
  puts "$A = #{set_latex}, \\, |A| = #{n_fp}$"
  return n_fp
end

# iterate k times
def iterate(x, k)
  f = Fspace.new
  i = 0
  while i < k
    x = f.send(:f, x)
    i += 1
  end
  return x
end

# take fixed points from fps of order k to set
def take_by_order(fps, k)
  set = [ ]
  n_fps = fps.length
    i = 0
  while i < n_fps
    x0 = fps[i]
    x = iterate(x0, k)
    # check if fixed point of order k
    if eq(x, x0)
      xr = to_rat(x0)
      set.push(xr)
      fps.delete_at(i)
      n_fps -= 1
    else
      i += 1
    end
  end
  return set
end

# partition fixed points regarding cycle length
def partition(fps, order)
  fp_set = fps.clone
  sets = [ ]
  for k in 1..order
    set = take_by_order(fp_set, k)
    sets.push(set)
  end
  # save remaining stuff
  sets.push(fp_set)
  return sets
end

def list_partition(fps, order)
  sets = partition(fps, order)
  n_sets = sets.length
  puts "partitions: #{n_sets}"
  i = 0
  while i < n_sets
    set = sets[i]
    set_s = set_to_s(set)
    n_set = set.length
    puts "A#{i+1} = #{set_s}, |A#{i+1}| = #{n_set}"
    i += 1
  end
  i = 0
  while i < n_sets
    set = sets[i]
    set_latex = set_to_latex(set)
    n_set = set.length
    puts "$A_{#{i+1}} = #{set_latex}, |A_{#{i+1}}| = #{n_set}$"
    i += 1
  end
end

# search fixed points
# - divide I = [0, 1] into n equal parts
# - calculate where the secant crosses the identity function
def search_fp(fn, n)
  # interval
  a = 0.0
  b = 1.0
  l = (b - a)
  h = l / n
  puts "n = #{n}, h = #{h}"
  f = Fspace.new
  # found fixed points
  fps = [ ]
  # loop to move [x_i, x_j] window
  x_i = a
  y_i = f.send(fn, x_i)
  puts "x0 = #{x_i}, y0 = #{y_i}"
  x_j = x_i + h
  for j in 1..n 
    y_j = f.send(fn, x_j)
    if ((y_i < x_i) && (y_j > x_j)) || ((y_i > x_i) && (y_j < x_j))
      # there is a fixed point, estimate where
      m = (y_j - y_i) / (x_j - x_i)
      m1 = m - 1
      if eq(m1, 0)
        puts "  secant close to id, using mid-point"
        x_m = (x_i + x_j) / 2
      else
        x_m = (m * x_i - y_i) / m1
      end
      i_fp = fp_add(fps, x_m)
      x_mr = to_rat(x_m)
      x_mrs = rat_to_s(x_mr)
      puts "  FP ##{i_fp} around #{x_m} = #{x_mrs}"
    end
    puts "x#{j} = #{x_j}, y#{j} = #{y_j}"
    # prepare next step
    x_i = x_j
    y_i = y_j
    x_j += h
  end
  list(fps, fn)
  list_partition(fps, 10)
  return fps
end

# alternative method:
# - perform all 2^{10} = 1024 decisions and 
# - gather the resulting fixed points 
def generate_fp(fn)
  fps = [ ]
  # todo
  list(fps, fn)
  return fps
end

# alternative method:
# - divide I = [0, 1] into n = 6*k equal parts
# - this induces a "board game" with 6*k+1 spaces from 0 to n
# - f moves pieces from space i to space f(i)
# - this forms several graphs G = (V, E)
# - the spaces are the vertices V_i
# - the moves are the edges E_j = (V_i, V_f(i))
# - the graphs might have cycles
# - the points in a cylce of length k are fixed points of f_k     
def graph_fp(fn, k)
  fps = [ ]
  # todo
  list(fps, fn)
  return fps
end

puts  "first try"
search_fp(:f, 2)

puts "second try"
search_fp(:f2, 3)

puts "find all FP for f_10:"
search_fp(:f10, 1024)

puts "rat_cache hits: #{$rat_hits} of #{$rat_lookups} lookups"