[plt-scheme] order of magnitude

2009/11/5 Jos Koot <jos.koot at telefonica.net>:
> Mathematically your derivation is correct, but computationally it may be
> incorrect. The problem is that in an actual computation, e.g. in Scheme,
>
> (expt 10 (/ (log q) (log 10)))
>
> may be
> slightly  less than q
> or exactly equal to q
> or slightly greater than q.
>
> This holds even when q is exact, for log is not required to and often even
> cannot produce an exact result. In fact I do not even trust that the
> absolute error of (/ (log q) (log 10)) is allways less than one, where
> absolute error is the difference between mathematical value and actually
> computed value.

Now I see what you were worried about.
The following solution uses nothing but exact computations.
The time complexity is the same as your solution.

(define (order q)
  (define (bisection-search m 10^m n 10^n)
    (cond [(= m n)       m]
          [(= (+ m 1) n) (if (> 10^n q) m n)]
          [else          (let* ([t (quotient (+ m n) 2)]
                                [10^t (* 10^m (expt 10 (- t m)))])
                           (if (> 10^t q)
                               (bisection-search m 10^m t 10^t)
                               (bisection-search t 10^t n 10^n)))]))
  (define (find-upper-limit m 10^m)
    (let ([10^2m (* 10^m 10^m)])
      (if (> 10^2m q)
          (bisection-search m 10^m (* 2 m) 10^2m)
          (find-upper-limit (* 2 m) 10^2m))))
  (find-upper-limit 1 10))

NB:  I was toying with integer-length to start the search,
       but it made very little difference.