Class: FractionTree::Node

Inherits:
Object
  • Object
show all
Extended by:
Forwardable
Includes:
Comparable
Defined in:
lib/fraction_tree/node.rb

Constant Summary collapse

IDENTITY_MATRIX = 
Matrix.identity(2)
LEFT_MATRIX = 
Matrix[[1,1]
RIGHT_MATRIX = 

      
    

  




  
Instance Attribute Summary collapse

  




  
    

      Class Method Summary
      collapse
    


    
  
    

      Instance Method Summary
      collapse
    


    
  


  
  

  
Constructor Details

  
    

  

  
    #initialize(num)  ⇒ Node 
  

  

  


  

    

Returns a new instance of Node.



  





  



  

    
      


16
17
18
19

    		
    
      
# File 'lib/fraction_tree/node.rb', line 16

def initialize(num)
  (@numerator, @denominator) = fraction_pair(num)
  @number = num
end

    		
  





  



  

    
Instance Attribute Details

    
      
      
      

  

  
    #denominator  ⇒ Object  (readonly)
  

  

  


  

    

Returns the value of attribute denominator.



  





  



  

    
      


10
11
12

    		
    
      
# File 'lib/fraction_tree/node.rb', line 10

def denominator
  @denominator
end

    		
  





    
      
      
      

  

  
    #number  ⇒ Object  (readonly)
  

  
    Also known as:
    to_r
    
  

  


  

    

Returns the value of attribute number.



  





  



  

    
      


10
11
12

    		
    
      
# File 'lib/fraction_tree/node.rb', line 10

def number
  @number
end

    		
  





    
      
      
      

  

  
    #numerator  ⇒ Object  (readonly)
  

  

  


  

    

Returns the value of attribute numerator.



  





  



  

    
      


10
11
12

    		
    
      
# File 'lib/fraction_tree/node.rb', line 10

def numerator
  @numerator
end

    		
  





    
  



  

    
Class Method Details


    
      

  

  
    .decimal_power(logarithmand)  ⇒ Integer 
  

  

  


  

    

Returns the decimal power of the provided number.



  





  
  

    
Examples:

    
      
      
FractionTree::Node.decimal_power(1000) => 3

    
  


Parameters:


    
  
    
  • 
      
        logarithmand
      
      
        
      
      
      
        —
        
    

    the number from which the log base 10 is obtained
    

    
      
    
    • 
  




Returns:


    
  
    
  • 
      
      
        (Integer)
      
      
      
        —
        
    

    the decimal power of the provided number
    

    
      
    
    • 
  





  

    
      


85
86
87

    		
    
      
# File 'lib/fraction_tree/node.rb', line 85

def decimal_power(logarithmand)
  Math.log10(logarithmand.abs).floor
end

    		
  





    
      

  

  
    .decode(string)  ⇒ FractionTree::Node 
  

  

  


  

    

Returns the fraction decoded from the given string.



  





  
  

    
Examples:

    
      
      
FractionTree::Node.decode("RLL") => (4/3)

    
  



Returns:





  

    
      


28
29
30
31
32
33
34
35
36
37
38
39
40

    		
    
      
# File 'lib/fraction_tree/node.rb', line 28

def decode(string)
  result = IDENTITY_MATRIX

  string.split("").each do |direction|
    case direction
    when "L", "0", "l"
      result = result * LEFT_MATRIX
    when "R", "1", "r"
      result = result * RIGHT_MATRIX
    end
  end
  FractionTree.node(Rational(result.row(1).sum, result.row(0).sum))
end

    		
  





    
      

  

  
    .encode(number, limit: Float::INFINITY)  ⇒ String 
  

  

  


  

    

Returns the Stern-Brocot encoding of number.



  





  
  

    
Examples:

    
      
      
FractionTree::Node.encode(4/3r) => "RLL"

    
  


Parameters:


    
  
    
  • 
      
        limit
      
      
        
      
      
        (defaults to: Float::INFINITY)
      
      
        —
        
    

    of codes to generate
    

    
      
    
    • 
  




Returns:


    
  
    
  • 
      
      
        (String)
      
      
      
        —
        
    

    the Stern-Brocot encoding of number
    

    
      
    
    • 
  





  

    
      


47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

    		
    
      
# File 'lib/fraction_tree/node.rb', line 47

def encode(number, limit: Float::INFINITY)
  return nil if (number.infinite? || number.zero?)

  m = number.numerator
  n = number.denominator

  return "I" if m == n

  "".tap do |string|
    while m != n && string.length < limit
      if m < n
        string << "L"
        n = n - m
      else
        string << "R"
        m = m - n
      end
    end
  end
end

    		
  





    
      

  

  
    .plus_minus(num, diff)  ⇒ Array 
  

  

  


  

    

Returns pair of numbers less and greater than the provided number by provided difference.



  





  
  

    
Examples:

    
      
      
FractionTree::Node.plus_minus(3, 2) => [1, 5]

    
  


Parameters:


    
  
    
  • 
      
        num
      
      
        
      
      
      
        —
        
    

    the base diff the number subtracted and added to base
    

    
      
    
    • 
  




Returns:


    
  
    
  • 
      
      
        (Array)
      
      
      
        —
        
    

    pair of numbers less and greater than the provided number by provided difference
    

    
      
    
    • 
  





  

    
      


75
76
77

    		
    
      
# File 'lib/fraction_tree/node.rb', line 75

def plus_minus(num, diff)
  [num - diff, num + diff]
end

    		
  





    
  


  

    
Instance Method Details


    
      

  

  
    #+(rhs)  ⇒ FractionTree::Node 
  

  

  


  

    

Returns sum of self and another node.



  





  
  

    
Examples:

    
      
      
FractionTree.node(5/4r) + FractionTree.node(3/2r)
=> (4/3)

    
  



Returns:





  

    
      


210
211
212

    		
    
      
# File 'lib/fraction_tree/node.rb', line 210

def +(rhs)
  tree.node(Rational(self.numerator+rhs.numerator, self.denominator+rhs.denominator))
end

    		
  





    
      

  

  
    #-(rhs)  ⇒ FractionTree::Node 
  

  

  


  

    

Returns difference of self and another node.



  





  
  

    
Examples:

    
      
      
FractionTree.node(5/4r) - FractionTree.node(3/2r)
=> (1/1)

    
  



Returns:





  

    
      


219
220
221

    		
    
      
# File 'lib/fraction_tree/node.rb', line 219

def -(rhs)
  tree.node(Rational((self.numerator-rhs.numerator).abs, (self.denominator-rhs.denominator).abs))
end

    		
  





    
      

  

  
    #<=>(rhs)  ⇒ Object 
  

  

  


  

    
      


228
229
230

    		
    
      
# File 'lib/fraction_tree/node.rb', line 228

def <=>(rhs)
  self.number <=> rhs.number
end

    		
  





    
      

  

  
    #==(rhs)  ⇒ Object 
  

  

  


  

    
      


232
233
234

    		
    
      
# File 'lib/fraction_tree/node.rb', line 232

def ==(rhs)
  self.number == rhs.number
end

    		
  





    
      

  

  
    #child_with(num)  ⇒ FractionTree::Node 
  

  

  


  

    
  

    Note:
    


return nil if bc - ad |= 1, for a/b, c/d



  




Returns child of self and given number.



  





  
  

    
Examples:

    
      
      
FractionTree.node(5/4r).child_with(4/3r)
=> (9/7)

    
  



Returns:





  

    
      


192
193
194

    		
    
      
# File 'lib/fraction_tree/node.rb', line 192

def child_with(num)
  tree.child_of(number, num)
end

    		
  





    
      

  

  
    #common_ancestors_with(num)  ⇒ Array 
  

  

  


  

    

Returns the ancestors shared by self and the given number.



  





  
  

    
Examples:

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

    
  


Parameters:


    
  
    
  • 
      
        num
      
      
        (Numeric)
      
      
      
        —
        
    

    other number sharing descendants with self
    

    
      
    
    • 
  




Returns:


    
  
    
  • 
      
      
        (Array)
      
      
      
        —
        
    

    the ancestors shared by self and the given number
    

    
      
    
    • 
  





  

    
      


158
159
160

    		
    
      
# File 'lib/fraction_tree/node.rb', line 158

def common_ancestors_with(num)
  path & tree.node(num).path
end

    		
  





    
      

  

  
    #descendancy_from(depth: 5)  ⇒ Array 
  

  

  


  

    

Returns of fraction tree nodes, descending from parents of number.



  





  
  

    
Examples:

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

    
  


Parameters:


    
  
    
  • 
      
        depth
      
      
        (Integer)
      
      
        (defaults to: 5)
      
      
        —
        
    

    how many nodes to collect
    

    
      
    
    • 
  




Returns:


    
  
    
  • 
      
      
        (Array)
      
      
      
        —
        
    

    of fraction tree nodes, descending from parents of number
    

    
      
    
    • 
  





  

    
      


181
182
183
184

    		
    
      
# File 'lib/fraction_tree/node.rb', line 181

def descendancy_from(depth: 5)
  (parent1, parent2) = parents
  tree.descendants_of(parent1.number, parent2.number, depth:)
end

    		
  





    
      

  

  
    #encoding(limit: Float::INFINITY)  ⇒ String 
  

  

  


  

    

Returns encoding of self.



  





  
  

    
Examples:

    
      
      
FractionTree.node(Math.log2(5/4r)).encoding(limit: 30) => "LLLRRRRRRRRRLLRRLLLLRRRRRRLLRL"

    
  


Parameters:


    
  
    
  • 
      
        limit
      
      
        
      
      
        (defaults to: Float::INFINITY)
      
      
        —
        
    

    of codes to generate
    

    
      
    
    • 
  




Returns:


    
  
    
  • 
      
      
        (String)
      
      
      
        —
        
    

    encoding of self
    

    
      
    
    • 
  





  

    
      


201
202
203

    		
    
      
# File 'lib/fraction_tree/node.rb', line 201

def encoding(limit: Float::INFINITY)
  self.class.encode(number, limit:)
end

    		
  





    
      

  

  
    #eql?(rhs)  ⇒ Boolean 
  

  

  


  

    

Needed for intersection operations to work. blog.mnishiguchi.com/ruby-intersection-of-object-arrays shortrecipes.blogspot.com/2006/10/ruby-intersection-of-two-arrays-of.html Also, allows using with Set, which uses Hash as storage and equality of its elements is determined according to Object#eql? and Object#hash.



  





  

Returns:


    
  
    
  • 
      
      
        (Boolean)
      
      
      
    
    • 
  





  

    
      


241
242
243

    		
    
      
# File 'lib/fraction_tree/node.rb', line 241

def eql?(rhs)
   rhs.instance_of?(self.class) && number == rhs.number
end

    		
  





    
      

  

  
    #hash  ⇒ Object 
  

  

  


  

    
      


245
246
247
248
249

    		
    
      
# File 'lib/fraction_tree/node.rb', line 245

def hash
   p, q = 17, 37
   p = q * @id.hash
   p = q * @name.hash
end

    		
  





    
      

  

  
    #inspect  ⇒ Object 
  

  
    Also known as:
    to_s
    
  

  


  

    
      


223
224
225

    		
    
      
# File 'lib/fraction_tree/node.rb', line 223

def inspect
  "(#{numerator}/#{denominator})"
end

    		
  





    
      

  

  
    #nearest_common_ancestor_with(num)  ⇒ FractionTree::Node 
  

  
    Also known as:
    nca_with
    
  

  


  

    

Returns the nearest common ancestor of self and the given number.



  





  
  

    
Examples:

    
      
      
FractionTree.node(4/3r).nearest_common_ancestor_with(7/4r)
=> (3/2)

    
  


Parameters:


    
  
    
  • 
      
        num
      
      
        (Numeric)
      
      
      
        —
        
    

    other number sharing descendants with self
    

    
      
    
    • 
  




Returns:





  

    
      


169
170
171

    		
    
      
# File 'lib/fraction_tree/node.rb', line 169

def nearest_common_ancestor_with(num)
  common_ancestors_with(num).last
end

    		
  





    
      

  

  
    #neighbors(r = 10**(self.class.decimal_power(number.numerator)+2))  ⇒ Array 
  

  

  


  

    

Returns of [FractionTree::Node], sequence of Farey neighbors to self. A Farey neighbor is a number c/d, who’s relationship to a/b is such that ad − bc = 1, when c/d < a/b and bc − ad = 1 when c/d > a/b.



  





  
  

    
Examples:

    
      
      
FractionTree.node(3/2r).neighbors(10)
=> [(1/1), (2/1), (4/3), (5/3), (7/5), (8/5), (10/7), (11/7), (13/9), (14/9)]

    
  


Parameters:


    
  
    
  • 
      
        r
      
      
        
      
      
        (defaults to: 10**(self.class.decimal_power(number.numerator)+2))
      
      
        —
        
    

    range of harmonic series to search
    

    
      
    
    • 
  




Returns:


    
  
    
  • 
      
      
        (Array)
      
      
      
        —
        
    

    of [FractionTree::Node], sequence of Farey neighbors to self. A Farey neighbor is a number c/d, who’s relationship to a/b is such that ad − bc = 1, when c/d < a/b and bc − ad = 1 when c/d > a/b.
    

    
      
    
    • 
  





  

    
      


138
139
140
141
142
143
144
145
146
147
148
149

    		
    
      
# File 'lib/fraction_tree/node.rb', line 138

def neighbors(r = 10**(self.class.decimal_power(number.numerator)+2))
  ratio = number.to_r
  denominator = ratio.denominator

  [].tap do |collection|
    (1..r-1).each do |i|
      lower, upper = self.class.plus_minus(ratio, Rational(1,i*denominator))
      collection << tree.node(lower) if tree.neighbors?(ratio, lower)
      collection << tree.node(upper) if tree.neighbors?(ratio, upper)
    end
  end
end

    		
  





    
      

  

  
    #parents  ⇒ Array 
  

  

  


  

    

Returns a pair of fraction tree nodes leading to the given number.



  





  
  

    
Examples:

    
      
      
FractionTree.node(15/13r).parents => [(8/7), (7/6)]
FractionTree.node(Math::PI).parents => [(1181999955934188/376242271442657), (1959592697655605/623757728557343)]

    
  



Returns:


    
  
    
  • 
      
      
        (Array)
      
      
      
        —
        
    

    a pair of fraction tree nodes leading to the given number.
    

    
      
    
    • 
  





  

    
      


127
128
129
130

    		
    
      
# File 'lib/fraction_tree/node.rb', line 127

def parents
  tmp = path
  [tmp[-2], tmp[-2..-1].inject(&:-)].sort
end

    		
  





    
      

  

  
    #path(limit: Float::INFINITY)  ⇒ Array 
  

  

  


  

    

Returns set of fraction tree nodes leading to the given number.



  





  
  

    
Examples:

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

    
  


Parameters:


    
  
    
  • 
      
        limit
      
      
        
      
      
        (defaults to: Float::INFINITY)
      
      
        —
        
    

    of nodes to generate
    

    
      
    
    • 
  




Returns:


    
  
    
  • 
      
      
        (Array)
      
      
      
        —
        
    

    set of fraction tree nodes leading to the given number
    

    
      
    
    • 
  





  

    
      


96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

    		
    
      
# File 'lib/fraction_tree/node.rb', line 96

def path(limit: Float::INFINITY)
  return nil if infinite? || zero?

  ln = tree.node(FractionTree.left_node)
  rn = tree.node(FractionTree.right_node)
  mn = ln + rn
  return [ln, rn, mn] if mn == tree.node(number)

  result = IDENTITY_MATRIX
  m = numerator
  n = denominator
  [].tap do |p|
    p << ln << rn << mn
    while m != n && p.length < limit
      if m < n
        result = result * LEFT_MATRIX
        n = n - m
      else
        result = result * RIGHT_MATRIX
        m = m - n
      end
      p << tree.node(Rational(result.row(1).sum,result.row(0).sum))
    end
  end
end