[plt-scheme] order of magnitude

Jens,
Interesting, but as time complexity is the same, I prefer to use the difference between the base 10 logarithm of the numerator and 
denominator as a first guess. In this way I use the wisdom of the mathematicians/programmers of the log function for a fast first 
guess. My experience is that this first guess seldomly has an absolute error greater than 1 (in fact I never encountered a greater 
error in PLT (provided the argument is exact)) This means I need (only counting operations on or producing possibly very big cq very 
small positive numbers)
1 time numerator/denominator
2 times log
1 time expt
2 to 4 times <= cq >=
2 to 3 times *

At first sight it seems to me that your method works for q>=10 only (e.g with your function  (order 1/1000) --> 1, which should 
be -3 and (order 1) --> 1, which should be 0 and (order #e9.99999999999999999) --> 1, which should be 0 too)
Jos

Robby
A proposal is coming up soon. I have to extract it from a more specialized piece of code.
And BTW, you certainly are not a PITA :)
Jos

All
Thanks to all who replied or otherwise showed interest to my question.
Jos

----- Original Message ----- 
From: "Jens Axel Søgaard" <jensaxel at soegaard.net>
To: "Jos Koot" <jos.koot at telefonica.net>
Cc: <plt-scheme at list.cs.brown.edu>
Sent: Thursday, November 05, 2009 5:11 PM
Subject: Re: [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.


----- Original Message ----- 
From: "Robby Findler" <robby at eecs.northwestern.edu>
To: "Jos Koot" <jos.koot at telefonica.net>
Cc: "Matthew Flatt" <mflatt at cs.utah.edu>; "Eli Barzilay" <eli at barzilay.org>; "Matthias Felleisen" <matthias at ccs.neu.edu>
Sent: Thursday, November 05, 2009 5:20 PM
Subject: Re: [plt-scheme] order of magnitude


Not to be a PITA, but I guess that you, Jos, would probably be one of
the best equipped people to write such a function and I'm sure we
could get it put into scheme/math if you were to.

Robby