Class: FractionTree

Inherits:
Object
  • Object
show all
Defined in:
lib/fraction_tree.rb

Defined Under Namespace

Classes: Node

Constant Summary collapse

DEFAULT_TREE_DEPTH = 
20

Class Method Summary collapse

Class Method Details

.base_segment ⇒ Array

Returns the boundary nodes of the tree.

Examples:

FractionTree.base_segment => [(0/1), (1/0)]

Returns:

  • (Array) —

    the boundary nodes of the tree



11
12
13
 
# File 'lib/fraction_tree.rb', line 11

def base_segment
  [Node.new(0,1), Node.new(1,0)]
end

.child_of(number1, number2, strict_neighbors: true) ⇒ FractionTree::Node

The mediant child of the given numbers Return nil if bc - ad |= 1, for a/b, c/d

Examples:

FractionTree.child_of(1/1r, 4/3r) => (5/4)
FractionTree.child_of(7/4r, 4/3r) => nil

Parameters:

  • number1 —

    one of two parents

  • number2 —

    two of two parents

Returns:

  • (FractionTree::Node) —

    the mediant child of the given numbers Return nil if bc - ad |= 1, for a/b, c/d



132
133
134
135
 
# File 'lib/fraction_tree.rb', line 132

def child_of(number1, number2, strict_neighbors: true)
  return nil unless farey_neighbors?(number1, number2) || !strict_neighbors
  Node.new(number1.numerator, number1.denominator) + Node.new(number2.numerator, number2.denominator)
end

.common_ancestors_between(number1, number2) ⇒ Array

Returns the ancestors shared by the given descendants.

Examples:

FractionTree.common_ancestors_between(4/3r, 7/4r)
=> [(1/1), (2/1), (3/2)]

Parameters:

  • number1 —

    one of two descendants

  • number2 —

    two of two descendants

Returns:

  • (Array) —

    the ancestors shared by the given descendants



106
107
108
 
# File 'lib/fraction_tree.rb', line 106

def common_ancestors_between(number1, number2)
  path_to(number1) & path_to(number2)
end

.descendancy_from(number, depth = 5) ⇒ Array

Returns the descendants of number starting at its parents.

Examples:

FractionTree.descendancy_from(5/4r, 3)
=> [(1/1), (7/6), (6/5), (11/9), (5/4), (14/11), (9/7), (13/10), (4/3)]

Parameters:

  • number —

    around which descendancy is focused

  • depth (defaults to: 5) —

    how many nodes to collect

Returns:

  • (Array) —

    the descendants of number starting at its parents



118
119
120
121
 
# File 'lib/fraction_tree.rb', line 118

def descendancy_from(number, depth=5)
  parent1, parent2 = parents_of(number)
  descendants_of(parent1, parent2, depth)
end

.descendants_of(parent1, parent2, depth = 5, strict_neighbors: true) ⇒ Array

Of nodes descended from parent1 and parent2 Return empty array if bc - ad |= 1, for a/b, c/d

Examples:

FractionTree.descendants_of(1/1r, 4/3r, 3)
=> [(1/1), (7/6), (6/5), (11/9), (5/4), (14/11), (9/7), (13/10), (4/3)]

Parameters:

  • parent1 —

    one of two parents

  • parent2 —

    two of two parents

Returns:

  • (Array) —

    of nodes descended from parent1 and parent2 Return empty array if bc - ad |= 1, for a/b, c/d



146
147
148
149
150
 
# File 'lib/fraction_tree.rb', line 146

def descendants_of(parent1, parent2, depth=5, strict_neighbors: true)
  return [] unless farey_neighbors?(parent1, parent2) || !strict_neighbors
  segment = [Node.new(parent1.numerator, parent1.denominator), Node.new(parent2.numerator, parent2.denominator)]
  sequence(depth, segment: segment)
end

.numeric_sequence ⇒ Array

Returns of numerators of the fraction tree nodes. Also known as the Stern-Brocot sequence.

Examples:

FractionTree.numeric_sequence.take(12)
=> [1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2]

Returns:

  • (Array) —

    of numerators of the fraction tree nodes. Also known as the Stern-Brocot sequence.



185
186
187
188
189
190
191
192
193
 
# File 'lib/fraction_tree.rb', line 185

def numeric_sequence
  return enum_for :numeric_sequence unless block_given?
  a=[1,1]

  0.step do |i|
    yield a[i]
    a << a[i]+a[i+1] << a[i+1]
  end
end

.parents_of(number) ⇒ Array

Returns a pair of fraction tree nodes leading to the given number. For irrational numbers, the parent nodes are one of an infinite series, whose nearness is determined by the limits of the system.

Examples:

FractionTree.parents_of(15/13r) => [(8/7), (7/6)]
FractionTree.parents_of(Math::PI) => [(447288330638589/142376297616907), (436991388364966/139098679093749)]

Parameters:

  • num —

    the child number whose parents are being sought

Returns:

  • (Array) —

    a pair of fraction tree nodes leading to the given number. For irrational numbers, the parent nodes are one of an infinite series, whose nearness is determined by the limits of the system



94
95
96
 
# File 'lib/fraction_tree.rb', line 94

def parents_of(number)
  path_to(number, find_parents: true)
end

.path_to(number, find_parents: false, segment: base_segment) ⇒ Array

Returns set of fraction nodes leading to the given number.

Examples:

FractionTree.path_to(7/4r) => [(1/1), (2/1), (3/2), (5/3), (7/4)]

Parameters:

  • number —

    the target the fraction path leads to

Returns:

  • (Array) —

    set of fraction nodes leading to the given number



63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
# File 'lib/fraction_tree.rb', line 63

def path_to(number, find_parents: false, segment: base_segment)
  return Node.new(number.numerator, number.denominator) if number.zero?
  q = Node.new(number.numerator, number.denominator)
  l = segment.first
  h = segment.last
  not_found = true
  parents = []
  results = []
  while not_found
    m = (l + h)
    if m < q
      l = m
    elsif m > q
      h = m
    else
      parents << l << h
      not_found = false
    end
    results << m
  end
  find_parents == false ? results : parents
end

.quotient_walk(number, limit: 10, segment: computed_base_segment(number)) ⇒ Array

Returns of FractionTree::Nodes leading quotient-wise to number.

Examples:

FractionTree.quotient_walk(15/13r)
=> [(1/1), (2/1), (3/2), (4/3), (5/4), (6/5), (7/6), (8/7), (15/13)]

Parameters:

  • number —

    to walk toward

  • limit (defaults to: 10) —

    the depth of the walk. Useful for irrational numbers

Returns:

  • (Array) —

    of FractionTree::Nodes leading quotient-wise to number



160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
 
# File 'lib/fraction_tree.rb', line 160

def quotient_walk(number, limit: 10, segment: computed_base_segment(number))
  iterating_quotients = ContinuedFraction.new(number, limit).quotients.drop(1)
  comparing_node = Node.new(number.numerator, number.denominator)

  segment.tap do |arr|
    held_node = arr[-2]
    moving_node = arr[-1]

    iterating_quotients.each do |q|
      (1..q).each do |i|
        arr << held_node + moving_node
        # We don't want to walk past the number when it's a rational number and we've reached it
        break if arr.include?(comparing_node)
        moving_node = arr[-1]
      end
      held_node = arr[-2]
    end
  end
end

.sequence(depth = 5, segment: base_segment) ⇒ Array

Returns a sequence of fraction tree nodes.

Examples:

FractionTree.sequence(3)
  => [(0/1), (1/3), (1/2), (2/3), (1/1), (3/2), (2/1), (3/1), (1/0)]

Parameters:

  • depth (defaults to: 5) —

    the number of iterations of the algorithm to run. The number of nodes returned will be greater

  • segment (defaults to: base_segment) —

    a tuple array defining the segment of the tree to collect nodes. The elements of the tuple must be instances of FractionTree::Node

Returns:

  • (Array) —

    a sequence of fraction tree nodes



53
54
55
 
# File 'lib/fraction_tree.rb', line 53

def sequence(depth=5, segment: base_segment)
  [segment.first]+_sequence(depth, segment:)+[segment.last]
end

.tree(depth = DEFAULT_TREE_DEPTH) ⇒ Array

Returns a multi-dimensional array with the elements of fraction tree, organized by level/row.

Examples:

FractionTree.tree(4)
=> [[(0/1), (1/0)],
    [(1/1)],
    [(1/2), (2/1)],
    [(1/3), (2/3), (3/2), (3/1)]]

Parameters:

  • number (Integer) —

    the depth of the tree

Returns:

  • (Array) —

    a multi-dimensional array with the elements of fraction tree, organized by level/row



25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
# File 'lib/fraction_tree.rb', line 25

def tree(depth=DEFAULT_TREE_DEPTH)
  Array.new(depth, 0).tap do |sbt|
    row = 0
    sbt[row] = base_segment
    i = 2
    while i <= depth do
      figure_from = sbt[0..row].flatten.sort
      new_frow = Array.new(2**(i-2), 0)
      idx = 0
      figure_from.each_cons(2) do |left,right|
        new_frow[idx] = Node.new(left.numerator+right.numerator, left.denominator+right.denominator)
        idx += 1
      end
      row += 1
      sbt[row] = new_frow
      i += 1
    end
  end
end