[plt-scheme] order of magnitude

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

        _________________________________________________
        Β For list-related administrative tasks:
        Β http://list.cs.brown.edu/mailman/listinfo/plt-scheme





    _________________________________________________
     For list-related administrative tasks:
     http://list.cs.brown.edu/mailman/listinfo/plt-scheme



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20091105/a56e8328/attachment.html>