4 people like it.

Enumerating the Rationals

How to enumerate the rational numbers without duplication using a Calkin–Wilf tree.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
65: 
66: 
67: 
68: 
69: 
70: 
open System.Numerics

// http://fsharpnews.blogspot.com/2013/08/implementing-rationals-in-f.html
type Rational(p: BigInteger, q: BigInteger) =
  let rec gcd a (b: BigInteger) =
    if b.IsZero then a else
      gcd b (a % b)

  let fixSign(p: BigInteger, q: BigInteger) =
    if q.Sign > 0 then p, q else -p, -q

  let p, q =
    if q.IsZero then raise(System.DivideByZeroException())
    let g = gcd q p
    fixSign(p/g, q/g)

  member __.Numerator = p
  member __.Denominator = q

  override __.ToString() =
    if q.IsOne then p.ToString() else sprintf "%A/%A" p q

  static member (+) (m: Rational, n: Rational) =
    Rational(m.Numerator*n.Denominator + n.Numerator*m.Denominator,
             m.Denominator*n.Denominator)

  static member (-) (m: Rational, n: Rational) =
    Rational(m.Numerator*n.Denominator - n.Numerator*m.Denominator,
             m.Denominator*n.Denominator)

  static member (*) (m: Rational, n: Rational) =
    Rational(m.Numerator*n.Numerator, m.Denominator*n.Denominator)

  static member (/) (m: Rational, n: Rational) =
    Rational(m.Numerator*n.Denominator, m.Denominator*n.Numerator)

let recip (r : Rational) =
    Rational(r.Denominator, r.Numerator)

let fromInteger n =
    Rational(n, 1I)

let properFraction (r : Rational) =
    let whole = r.Numerator / r.Denominator
    let part = Rational(r.Numerator % r.Denominator, r.Denominator)
    whole, part

let one = fromInteger 1I

let iterate f x =
    let rec loop x =
        seq {
            yield x
            yield! loop (f x)
        }
    loop x

/// https://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals.pdf
let next x =
    let n, y = properFraction x
    recip (fromInteger n + one - y)

let rationals =
    iterate next one

[<EntryPoint>]
let main argv =
    for r in rationals do
        printfn "%A" r
    0
namespace System
namespace System.Numerics
Multiple items
type Rational =
  new : p:BigInteger * q:BigInteger -> Rational
  override ToString : unit -> string
  member Denominator : BigInteger
  member Numerator : BigInteger
  static member ( + ) : m:Rational * n:Rational -> Rational
  static member ( / ) : m:Rational * n:Rational -> Rational
  static member ( * ) : m:Rational * n:Rational -> Rational
  static member ( - ) : m:Rational * n:Rational -> Rational

Full name: Script.Rational

--------------------
new : p:BigInteger * q:BigInteger -> Rational
val p : BigInteger
Multiple items
type BigInteger =
  struct
    new : value:int -> BigInteger + 7 overloads
    member CompareTo : other:int64 -> int + 3 overloads
    member Equals : obj:obj -> bool + 3 overloads
    member GetHashCode : unit -> int
    member IsEven : bool
    member IsOne : bool
    member IsPowerOfTwo : bool
    member IsZero : bool
    member Sign : int
    member ToByteArray : unit -> byte[]
    ...
  end

Full name: System.Numerics.BigInteger

--------------------
BigInteger()
BigInteger(value: int) : unit
BigInteger(value: uint32) : unit
BigInteger(value: int64) : unit
BigInteger(value: uint64) : unit
BigInteger(value: float32) : unit
BigInteger(value: float) : unit
BigInteger(value: decimal) : unit
BigInteger(value: byte []) : unit
val q : BigInteger
val gcd : (BigInteger -> BigInteger -> BigInteger)
val a : BigInteger
val b : BigInteger
property BigInteger.IsZero: bool
val fixSign : (BigInteger * BigInteger -> BigInteger * BigInteger)
property BigInteger.Sign: int
val raise : exn:System.Exception -> 'T

Full name: Microsoft.FSharp.Core.Operators.raise
Multiple items
type DivideByZeroException =
  inherit ArithmeticException
  new : unit -> DivideByZeroException + 2 overloads

Full name: System.DivideByZeroException

--------------------
System.DivideByZeroException() : unit
System.DivideByZeroException(message: string) : unit
System.DivideByZeroException(message: string, innerException: exn) : unit
val g : BigInteger
member Rational.Numerator : BigInteger

Full name: Script.Rational.Numerator
val __ : Rational
member Rational.Denominator : BigInteger

Full name: Script.Rational.Denominator
override Rational.ToString : unit -> string

Full name: Script.Rational.ToString
property BigInteger.IsOne: bool
BigInteger.ToString() : string
BigInteger.ToString(format: string) : string
BigInteger.ToString(provider: System.IFormatProvider) : string
BigInteger.ToString(format: string, provider: System.IFormatProvider) : string
val sprintf : format:Printf.StringFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf
val m : Rational
val n : Rational
property Rational.Numerator: BigInteger
property Rational.Denominator: BigInteger
val recip : r:Rational -> Rational

Full name: Script.recip
val r : Rational
val fromInteger : n:BigInteger -> Rational

Full name: Script.fromInteger
val n : BigInteger
val properFraction : r:Rational -> BigInteger * Rational

Full name: Script.properFraction
val whole : BigInteger
val part : Rational
val one : Rational

Full name: Script.one
val iterate : f:('a -> 'a) -> x:'a -> seq<'a>

Full name: Script.iterate
val f : ('a -> 'a)
val x : 'a
val loop : ('a -> seq<'a>)
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
val next : x:Rational -> Rational

Full name: Script.next


 https://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals.pdf
val x : Rational
val y : Rational
val rationals : seq<Rational>

Full name: Script.rationals
Multiple items
type EntryPointAttribute =
  inherit Attribute
  new : unit -> EntryPointAttribute

Full name: Microsoft.FSharp.Core.EntryPointAttribute

--------------------
new : unit -> EntryPointAttribute
val main : argv:string [] -> int

Full name: Script.main
val argv : string []
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
Raw view New version

More information

Link:http://fssnip.net/7VB
Posted:19 days ago
Author:Brian Berns
Tags: gcd , numbers , rational