# [plt-scheme] order of magnitude

 From: Jens Axel Søgaard (jensaxel at soegaard.net) Date: Thu Nov 5 11:11:25 EST 2009 Previous message: [plt-scheme] order of magnitude Next message: [plt-scheme] order of magnitude Messages sorted by: [date] [thread] [subject] [author]

```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.

```

 Posted on the users mailing list. Previous message: [plt-scheme] order of magnitude Next message: [plt-scheme] order of magnitude Messages sorted by: [date] [thread] [subject] [author]