[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