Class: Nio::Rtnlzr

Inherits:
Object
  • Object
show all
Includes:
StateEquivalent
Defined in:
lib/nio/rtnlzr.rb,
lib/nio/rtnlzr.rb

Overview

This class provides conversion of fractions (as approximate floating point numbers) to rational numbers.

Defined Under Namespace

Modules: Mth

Class Method Summary collapse

Instance Method Summary collapse

Methods included from StateEquivalent

#==, #===, #eql?, #hash

Constructor Details

#initialize(tol = Flt.Tolerance(:epsilon)) ⇒ Rtnlzr

Create Rationalizator with given tolerance.



153
154
155
 
# File 'lib/nio/rtnlzr.rb', line 153

def initialize(tol=Flt.Tolerance(:epsilon))
  @tol = tol
end

Class Method Details

.max_denominator(f, max_den = 1000000000, num_class = nil) ⇒ Object

Best fraction given maximum denominator Algorithm Copyright © 1991 by Joseph K. Horn.

The implementation of this method uses floating point arithmetic which limits the magnitude and precision of the results, specially using Float values.



343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
 
# File 'lib/nio/rtnlzr.rb', line 343

def Rtnlzr.max_denominator(f, max_den=1000000000, num_class=nil)
  return nil if max_den<1
  num_class ||= f.class
  context = num_class.context
  return mth.ip(f),1 if mth.fp(f)==0

  cast = lambda{|x| context.Num(x)}

  one = cast.call(1)

   sign = f<0
   f = -f if sign

   a,b,c = 0,1,f
   while b<max_den and c!=0
     cc = one/c
     a,b,c = b, mth.ip(cc)*b+a, mth.fp(cc)
   end


   if b>max_den
     b -= a*mth.ceil(cast.call(b-max_den)/a)
   end


   f1,f2 = [a,b].collect{|x| mth.abs(cast.call(mth.rnd(x*f))/x-f)}

   a = f1>f2 ? b : a

   num,den = mth.rnd(a*f).to_i,a
   den = 1 if mth.abs(den)<1

   num = -num if sign

  return num,den
end

Instance Method Details

#rationalize(x) ⇒ Object

Rationalization method that finds the fraction with smallest denominator fraction within the tolerance distance of an approximate (floating point) number.

It uses the algorithm which has been found most efficient, rationalize_Knuth.



162
163
164
 
# File 'lib/nio/rtnlzr.rb', line 162

def rationalize(x)
  rationalize_Knuth(x)
end

#rationalize_Horn(x) ⇒ Object

This is algorithm PDQ2 by Joe Horn.



220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
 
# File 'lib/nio/rtnlzr.rb', line 220

def rationalize_Horn(x)
  

  num_tol = @tol.kind_of?(Numeric)
  if !num_tol && @tol.zero?(x)
    # num,den = x.nio_xr.nio_num_den
    num,den = 0,1
  else
    negans=false
    if x<0
      negans = true
      x = -x
    end
    dx = num_tol ? @tol : @tol.value(x)

    
    z,t = x,dx # renaming

    a,b = t.nio_xr.nio_num_den
    n0,d0 = (n,d = z.nio_xr.nio_num_den)
    cn,x,pn,cd,y,pd,lo,hi,mid,q,r = 1,1,0,0,0,1,0,1,1,0,0
    begin
      q,r = n.divmod(d)
      x = q*cn+pn
      y = q*cd+pd
      pn = cn
      cn = x
      pd = cd
      cd = y
      n,d = d,r
    end until b*(n0*y-d0*x).abs <= a*d0*y
    
    if q>1
      hi = q
      begin
        mid = (lo+hi).div(2)
        x = cn-pn*mid
        y = cd-pd*mid
        if b*(n0*y-d0*x).abs <= a*d0*y
          lo = mid
        else
          hi = mid
        end
      end until hi-lo <= 1
      x = cn - pn*lo
      y = cd - pd*lo
    end
    
    num,den = x,y # renaming
    

    num = -num if negans
  end
  return num,den
  
  
end

#rationalize_HornHutchins(x) ⇒ Object

This is from a RPL program by Tony Hutchins (PDR6).



278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
 
# File 'lib/nio/rtnlzr.rb', line 278

def rationalize_HornHutchins(x)
  

  num_tol = @tol.kind_of?(Numeric)
  if !num_tol && @tol.zero?(x)
    # num,den = x.nio_xr.nio_num_den
    num,den = 0,1
  else
    negans=false
    if x<0
      negans = true
      x = -x
    end
    dx = num_tol ? @tol : @tol.value(x)

    
    z,t = x,dx # renaming

    a,b = t.nio_xr.nio_num_den
    n0,d0 = (n,d = z.nio_xr.nio_num_den)
    cn,x,pn,cd,y,pd,lo,hi,mid,q,r = 1,1,0,0,0,1,0,1,1,0,0
    begin
      q,r = n.divmod(d)
      x = q*cn+pn
      y = q*cd+pd
      pn = cn
      cn = x
      pd = cd
      cd = y
      n,d = d,r
    end until b*(n0*y-d0*x).abs <= a*d0*y
    
    if q>1
      hi = q
      begin
        mid = (lo+hi).div(2)
        x = cn-pn*mid
        y = cd-pd*mid
        if b*(n0*y-d0*x).abs <= a*d0*y
          lo = mid
        else
          hi = mid
        end
      end until hi-lo <= 1
      x = cn - pn*lo
      y = cd - pd*lo
    end
    
    num,den = x,y # renaming
    

    num = -num if negans
  end
  return num,den
  
  
end

#rationalize_Knuth(x) ⇒ Object

This algorithm is derived from exercise 39 of 4.5.3 in “The Art of Computer Programming”, by Donald E. Knuth.



168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
 
# File 'lib/nio/rtnlzr.rb', line 168

def rationalize_Knuth(x)
  

  num_tol = @tol.kind_of?(Numeric)
  if !num_tol && @tol.zero?(x)
    # num,den = x.nio_xr.nio_num_den
    num,den = 0,1
  else
    negans=false
    if x<0
      negans = true
      x = -x
    end
    dx = num_tol ? @tol : @tol.value(x)

    
      x = x.nio_xr
      dx = dx.nio_xr
      xp,xq = (x-dx).nio_num_den
      yp,yq = (x+dx).nio_num_den

        a = []
        fin,odd = false,false
        while !fin && xp!=0 && yp!=0
          odd = !odd
          xp,xq = xq,xp
          ax = xp.div(xq)
          xp -= ax*xq

          yp,yq = yq,yp
          ay = yp.div(yq)
          yp -= ay*yq

          if ax!=ay
            fin = true
            ax,xp,xq = ay,yp,yq if odd
          end
          a << ax # .to_i
        end
        a[-1] += 1 if xp!=0 && a.size>0
        p,q = 1,0
        (1..a.size).each{|i| p,q=q+p*a[-i],p}
        num,den = q,p
    

    num = -num if negans
  end
  return num,den
  
  
end