Fast algorithm for double->string conversion.

tools/generate-ten-powers.scm

+;; Copyright 2010 the V8 project authors. All rights reserved.
+;; Redistribution and use in source and binary forms, with or without
+;; modification, are permitted provided that the following conditions are
+;; met:
+;;
+;;     * Redistributions of source code must retain the above copyright
+;;       notice, this list of conditions and the following disclaimer.
+;;     * Redistributions in binary form must reproduce the above
+;;       copyright notice, this list of conditions and the following
+;;       disclaimer in the documentation and/or other materials provided
+;;       with the distribution.
+;;     * Neither the name of Google Inc. nor the names of its
+;;       contributors may be used to endorse or promote products derived
+;;       from this software without specific prior written permission.
+;;
+;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+;; LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+;; DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+;; THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+;; (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+;; OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+;; Generate approximations of 10^k.
+;; Requires Bigloo to compile:
+;;   bigloo -static-bigloo -o generate-ten-powers generate-ten-powers.scm
+
+(module gen-ten-powers
+   (static (class Cached-Fast
+              v::bignum
+              e::bint
+              exact?::bool))
+   (main my-main))
+
+
+;;----------------bignum shifts -----------------------------------------------
+(define (bit-lshbx::bignum x::bignum by::bint)
+   (if (<fx by 0)
+       #z0
+       (*bx x (exptbx #z2 (fixnum->bignum by)))))
+
+(define (bit-rshbx::bignum x::bignum by::bint)
+   (if (<fx by 0)
+       #z0
+       (/bx x (exptbx #z2 (fixnum->bignum by)))))
+
+;;----------------the actual power generation -------------------------------
+
+;; e should be an indication. it might be too small.
+(define (round-n-cut n e nb-bits)
+   (define max-container (- (bit-lshbx #z1 nb-bits) 1))
+   (define (round n)
+      (case *round*
+         ((down) n)
+         ((up)
+          (+bx n
+               ;; with the -1 it will only round up if the cut off part is
+               ;; non-zero
+               (-bx (bit-lshbx #z1
+                               (-fx (+fx e nb-bits) 1))
+                    #z1)))
+         ((round)
+          (+bx n
+               (bit-lshbx #z1
+                          (-fx (+fx e nb-bits) 2))))))
+   (let* ((shift (-fx (+fx e nb-bits) 1))
+          (cut (bit-rshbx (round n) shift))
+          (exact? (=bx n (bit-lshbx cut shift))))
+      (if (<=bx cut max-container)
+          (values cut e exact?)
+          (round-n-cut n (+fx e 1) nb-bits))))
+
+(define (rounded-/bx x y)
+   (case *round*
+      ((down)  (/bx x y))
+      ((up)    (+bx (/bx x y) #z1))
+      ((round) (let ((tmp (/bx (*bx #z2 x) y)))
+                  (if (zerobx? (remainderbx tmp #z2))
+                      (/bx tmp #z2)
+                      (+bx (/bx tmp #z2) #z1))))))
+
+(define (generate-powers from to mantissa-size)
+   (let* ((nb-bits mantissa-size)
+          (offset (- from))
+          (nb-elements (+ (- from) to 1))
+          (vec (make-vector nb-elements))
+          (max-container (- (bit-lshbx #z1 nb-bits) 1)))
+      ;; the negative ones. 10^-1, 10^-2, etc.
+      ;; We already know, that we can't be exact, so exact? will always be #f.
+      ;; Basically we will have a ten^i that we will *10 at each iteration. We
+      ;; want to create the matissa of 1/ten^i. However the mantissa must be
+      ;; normalized (start with a 1). -> we have to shift the number.
+      ;; We shift by multiplying with two^e. -> We encode two^e*(1/ten^i) ==
+      ;;  two^e/ten^i.
+      (let loop ((i 1)
+                 (ten^i #z10)
+                 (two^e #z1)
+                 (e 0))
+         (unless (< (- i) from)
+            (if (>bx (/bx (*bx #z2 two^e) ten^i) max-container)
+                ;; another shift would make the number too big. We are
+                ;; hence normalized now.
+                (begin
+                   (vector-set! vec (-fx offset i)
+                                (instantiate::Cached-Fast
+                                   (v (rounded-/bx two^e ten^i))
+                                   (e (negfx e))
+                                   (exact? #f)))
+                   (loop (+fx i 1) (*bx ten^i #z10) two^e e))
+                (loop i ten^i (bit-lshbx two^e 1) (+fx e 1)))))
+      ;; the positive ones 10^0, 10^1, etc.
+      ;; start with 1.0. mantissa: 10...0 (1 followed by nb-bits-1 bits)
+      ;;      -> e = -(nb-bits-1)
+      ;; exact? is true when the container can still hold the complete 10^i
+      (let loop ((i 0)
+                 (n (bit-lshbx #z1 (-fx nb-bits 1)))
+                 (e (-fx 1 nb-bits)))
+         (when (<= i to)
+            (receive (cut e exact?)
+               (round-n-cut n e nb-bits)
+               (vector-set! vec (+fx i offset)
+                            (instantiate::Cached-Fast
+                               (v cut)
+                               (e e)
+                               (exact? exact?)))
+               (loop (+fx i 1) (*bx n #z10) e))))
+      vec))
+
+(define (print-c powers from to struct-type
+                 cache-name max-distance-name offset-name macro64)
+   (define (display-power power k)
+      (with-access::Cached-Fast power (v e exact?)
+         (let ((tmp-p (open-output-string)))
+            ;; really hackish way of getting the digits
+            (display (format "~x" v) tmp-p)
+            (let ((str (close-output-port tmp-p)))
+               (printf "  {~a(0x~a, ~a), ~a, ~a},\n"
+                       macro64
+                       (substring str 0 8)
+                       (substring str 8 16)
+                       e
+                       k)))))
+   (define (print-powers-reduced n)
+      (print "static const " struct-type " " cache-name
+             "(" n ")"
+             "[] = {")
+      (let loop ((i 0)
+                 (nb-elements 0)
+                 (last-e 0)
+                 (max-distance 0))
+         (cond
+            ((>= i (vector-length powers))
+             (print "  };")
+             (print "static const int " max-distance-name "(" n ") = "
+                 max-distance ";")
+             (print "// nb elements (" n "): " nb-elements))
+            (else
+             (let* ((power (vector-ref powers i))
+                    (e (Cached-Fast-e power)))
+             (display-power power (+ i from))
+             (loop (+ i n)
+                   (+ nb-elements 1)
+                   e
+                   (cond
+                      ((=fx i 0) max-distance)
+                      ((> (- e last-e) max-distance) (- e last-e))
+                      (else max-distance))))))))
+   (print "// ------------ GENERATED FILE ----------------")
+   (print "// command used:")
+   (print "// "
+          (apply string-append (map (lambda (str)
+                                       (string-append " " str))
+                                    *main-args*))
+          "  // NOLINT")
+   (print)
+   (print-powers-reduced 1)
+   (print-powers-reduced 2)
+   (print-powers-reduced 3)
+   (print-powers-reduced 4)
+   (print-powers-reduced 5)
+   (print-powers-reduced 6)
+   (print-powers-reduced 7)
+   (print-powers-reduced 8)
+   (print-powers-reduced 9)
+   (print-powers-reduced 10)
+   (print-powers-reduced 11)
+   (print-powers-reduced 12)
+   (print-powers-reduced 13)
+   (print-powers-reduced 14)
+   (print-powers-reduced 15)
+   (print-powers-reduced 16)
+   (print-powers-reduced 17)
+   (print-powers-reduced 18)
+   (print-powers-reduced 19)
+   (print-powers-reduced 20)
+   (print "static const int GRISU_CACHE_OFFSET = " (- from) ";"))
+
+;;----------------main --------------------------------------------------------
+(define *main-args* #f)
+(define *mantissa-size* #f)
+(define *dest* #f)
+(define *round* #f)
+(define *from* #f)
+(define *to* #f)
+
+(define (my-main args)
+   (set! *main-args* args)
+   (args-parse (cdr args)
+      (section "Help")
+      (("?") (args-parse-usage #f))
+      ((("-h" "--help") (help "?, -h, --help" "This help message"))
+       (args-parse-usage #f))
+      (section "Misc")
+      (("-o" ?file (help "The output file"))
+       (set! *dest* file))
+      (("--mantissa-size" ?size (help "Container-size in bits"))
+       (set! *mantissa-size* (string->number size)))
+      (("--round" ?direction (help "Round bignums (down, round or up)"))
+       (set! *round* (string->symbol direction)))
+      (("--from" ?from (help "start at 10^from"))
+       (set! *from* (string->number from)))
+      (("--to" ?to (help "go up to 10^to"))
+       (set! *to* (string->number to)))
+      (else
+       (print "Illegal argument `" else "'. Usage:")
+       (args-parse-usage #f)))
+   (when (not *from*)
+      (error "generate-ten-powers"
+             "Missing from"
+             #f))
+   (when (not *to*)
+      (error "generate-ten-powers"
+             "Missing to"
+             #f))
+   (when (not *mantissa-size*)
+      (error "generate-ten-powers"
+             "Missing mantissa size"
+             #f))
+   (when (not (memv *round* '(up down round)))
+      (error "generate-ten-powers"
+             "Missing round-method"
+             *round*))
+
+   (let ((dividers (generate-powers *from* *to* *mantissa-size*))
+         (p (if (not *dest*)
+                (current-output-port)
+                (open-output-file *dest*))))
+      (unwind-protect
+         (with-output-to-port p
+            (lambda ()
+               (print-c dividers *from* *to*
+                        "GRISU_CACHE_STRUCT" "GRISU_CACHE_NAME"
+                        "GRISU_CACHE_MAX_DISTANCE" "GRISU_CACHE_OFFSET"
+                        "GRISU_UINT64_C"
+                        )))
+         (if *dest*
+             (close-output-port p)))))