# [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.