[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 <pbewig at gmail.com>
> *To:* Jos Koot <jos.koot at telefonica.net>
> *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/0da64856/attachment.html>