Happy PI day ! (in QiII)

Mon, Mar 14, 2011

Qi is the future of Lisp.
It is Lisp with many great features such as pattern-matching, a turing complete static type system (even more powerful than Haskell’s type system) and many others.

So in the spirit of PI day, here’s an implementation that calculates PI using Machin’s formula.

(define ceiling
  X -> (CEILING X))
(declare ceiling [number --> number])
(define expt
  X Y -> (EXPT X Y))
(declare expt [number --> number --> number])
(define floor
  X Y -> (FLOOR X Y))
(declare floor [number --> number --> number])
(define log
  X Y -> (LOG X Y))
(declare log [number --> number --> number])
(tc +)
(define arccot-
  {number --> number --> number --> number --> number --> number}
  X N XPOWER    0 _ -> 0
  X N XPOWER TERM 1 -> (+ (arccot- X (+ N 2) (floor XPOWER X)
                                     (floor XPOWER N) 0) (floor XPOWER N))
  X N XPOWER TERM 0 -> (- (arccot- X (+ N 2) (floor XPOWER X)
                                      (floor XPOWER N) 1) (floor XPOWER N)))
(define arccot
  {number --> number --> number}
  X UNITY -> (let XPOWER (floor (/ UNITY X) 1)
                  (arccot- (* X X) 1 XPOWER (floor XPOWER 1) 1)))
(define machin-pi
  {number --> number}
  DIGITS -> (let GUARD (+ 10 (ceiling (log DIGITS 10)))
                 UNITY (expt 10 (+ DIGITS GUARD))
                 (floor (* 4 (- (* 4 (arccot 5 UNITY))
                                (arccot 239 UNITY))) (expt 10 GUARD))))

And the output …

(time (machin-pi 10000))
Evaluation took:
  0.379 seconds of real time
  0.372112 seconds of total run time (0.269730 user, 0.102382 system)
  [ Run times consist of 0.055 seconds GC time, and 0.318 seconds non-GC time. ]
  98.15% CPU
  903,769,308 processor cycles
  78,698,160 bytes consed
314159265358979323846264338327950 ... 1655256375678 : number

Compared with Common Lisp, Haskell and Clojure.