# [plt-scheme] order of magnitude

 From: Jos Koot (jos.koot at telefonica.net) Date: Thu Nov 5 10:51:19 EST 2009 Previous message: [plt-scheme] order of magnitude Next message: [plt-scheme] Why is (require (planet untyped/snooze:2) so slow? Messages sorted by: [date] [thread] [subject] [author]

```I guess that's exactly what I showed in my first post in this thread. However, notice that in my post to Phil, I reduced the problem to taking floors of base 10 logarithms of exact positive integers. For a positive exact rational, take the difference between the floors of the base 10 logarithms of the numerator and denominator, and subsequently iterate in order to overcome inaccuracy. However, these iterations, few as they may be, may require exact computations on very large integer numbers. That makes them slow.

I have a method that works and can be proven to be correct. I started this thread, because I wondered whether or not it is possible to do the computation in a more efficient way.
Jos
----- Original Message -----
From: Laurent
To: Jos Koot
Cc: Phil Bewig ; plt-scheme at list.cs.brown.edu
Sent: Thursday, November 05, 2009 4:39 PM
Subject: Re: [plt-scheme] order of magnitude

Would it be possible to use the log method as a first approximation, take the number that is 1 or 2 orders lower, then use the iteration method on only the last few iterations?

Laurent

2009/11/5 Jos Koot <jos.koot at telefonica.net>

Hi Phil,

Yes, that is an exact method (provided b is exact) and the code is straight forward indeed. As you say, it takes a while. That's why I try to use primitive log. In fact I use a method that computes the logarithms (base 10) of the numerator and nominator of rationals separately such as to avoid -inf.0 for (positive) rational numbers very close to zero (not shown in my example)

We have something like integer-sqrt/remainder for square roots. It would be nice to have something like (integer-log-base-10/remainder n) --> p r such that (+ (expt 10 p) r) exactly equals n, where n, p and r are positive exact integer numbers and p is computed to be maximal.

Jos
----- Original Message -----
From: Phil Bewig
To: Jos Koot
Cc: plt-scheme at list.cs.brown.edu
Sent: Thursday, November 05, 2009 4:02 PM
Subject: Re: [plt-scheme] order of magnitude

(define (ilog b n)
Β  (let loop ((n n) (i -1))
Β Β Β  (if (zero? n) i
Β Β Β Β Β  (loop (quotient n b) (+ i 1)))))

(ilog 10 #e1000e1000000) => 1000003

It does take a while....

On Thu, Nov 5, 2009 at 5:04 AM, Jos Koot <jos.koot at telefonica.net> wrote:

Some browsing did not lead me to finding a function that accepts an exact positive rational number and returns its order of magnitude (an exact integer number) Something like:

(define log10 (inexact->exact (log 10)))
(define (order-of-magnitude q) (floor (/ (inexact->exact (log q)) log10)))

However, due to inexactness of function log we find:

(/ (inexact->exact (log #e1000e1000000)) log10) --> close to but sligtly less than 1000003

and hence:

(order-of-magnitude #e1000e1000000) ; --> 1000002

The wanted answer is 1000003. So I did the following:

(define order-of-magnitude

Β (let*
Β  ((log10 (inexact->exact (log 10)))
Β Β  (10log (Ξ» (q) (/ (inexact->exact (log q)) log10))))
Β  (Ξ» (q)
Β Β  (unless (and (rational? q) (exact? q) (positive? q))
Β Β Β  (raise-type-error 'magnitude "positive exact rational number" q))
Β Β  (let* ((m (floor (10log q))) (k (expt 10 m)))
Β Β Β  ; >From now on all arithmetic operations and their operands are exact.
Β Β Β  (let loop ((m m) (lower (* k 1/10)) (middle k) (upper (* k 10)))
Β Β Β Β  (cond
Β Β Β Β Β  ((<= q lower) (loop (sub1 m) (* lower 1/10) lower middle))
Β Β Β Β Β  ((>= q upper) (loop (add1 m) middle upper (* upper 10)))
Β Β Β Β Β  (else m)))))))

(order-of-magnitude #e1000e1000000) ; --> 1000003

However, this seems rather complicated. Does someone have or know of a simpler and faster function for this purpose?

Thanks, Jos

_________________________________________________
Β http://list.cs.brown.edu/mailman/listinfo/plt-scheme

_________________________________________________