<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META http-equiv=Content-Type content="text/html; charset=iso-8859-7"> <META content="MSHTML 6.00.6000.16939" name=GENERATOR> <STYLE></STYLE> </HEAD> <BODY bgColor=#ffffff> <DIV><FONT face="Courier New" size=2>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.</FONT></DIV> <DIV><FONT face="Courier New" size=2></FONT> </DIV> <DIV><FONT face="Courier New" size=2>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.</FONT></DIV> <DIV><FONT face="Courier New" size=2>Jos</FONT></DIV> <BLOCKQUOTE style="PADDING-RIGHT: 0px; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #000000 2px solid; MARGIN-RIGHT: 0px"> <DIV style="FONT: 10pt arial">----- Original Message ----- </DIV> <DIV style="BACKGROUND: #e4e4e4; FONT: 10pt arial; font-color: black"><B>From:</B> <A title=laurent.orseau@gmail.com href="mailto:laurent.orseau@gmail.com">Laurent</A> </DIV> <DIV style="FONT: 10pt arial"><B>To:</B> <A title=jos.koot@telefonica.net href="mailto:jos.koot@telefonica.net">Jos Koot</A> </DIV> <DIV style="FONT: 10pt arial"><B>Cc:</B> <A title=pbewig@gmail.com href="mailto:pbewig@gmail.com">Phil Bewig</A> ; <A title=plt-scheme@list.cs.brown.edu href="mailto:plt-scheme@list.cs.brown.edu">plt-scheme@list.cs.brown.edu</A> </DIV> <DIV style="FONT: 10pt arial"><B>Sent:</B> Thursday, November 05, 2009 4:39 PM</DIV> <DIV style="FONT: 10pt arial"><B>Subject:</B> Re: [plt-scheme] order of magnitude</DIV> <DIV><BR></DIV>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?<BR><BR>Laurent<BR><BR> <DIV class=gmail_quote>2009/11/5 Jos Koot <SPAN dir=ltr><<A href="mailto:jos.koot@telefonica.net">jos.koot@telefonica.net</A>></SPAN><BR> <BLOCKQUOTE class=gmail_quote style="PADDING-LEFT: 1ex; MARGIN: 0pt 0pt 0pt 0.8ex; BORDER-LEFT: rgb(204,204,204) 1px solid"> <DIV bgcolor="#ffffff"> <DIV><FONT face="Courier New" size=2>Hi Phil,</FONT></DIV> <DIV><FONT face="Courier New" size=2></FONT> </DIV> <DIV><FONT face="Courier New" size=2>Yes, that is an exact method (provided b is exact) and the code is straight forward indeed. </FONT><FONT face="Courier New" size=2>As you say, it takes a while. That's why I try to use primitive log. </FONT><FONT face="Courier New" size=2>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)</FONT></DIV> <DIV><FONT face="Courier New" size=2></FONT> </DIV> <DIV><FONT size=2><FONT face="Courier New">We have something like <SPAN title="Provided from: scheme/base, scheme"><SPAN><A>integer-sqrt/remainder</A> for square roots. It would be nice to have something like (integer-log-base-10/remainder n) --> p r </SPAN></SPAN></FONT></FONT><FONT size=2><FONT face="Courier New"><SPAN title="Provided from: scheme/base, scheme"><SPAN>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.</SPAN></SPAN></FONT></FONT></DIV> <DIV><FONT face="Courier New" size=2></FONT> </DIV> <DIV><FONT face="Courier New" size=2>Jos</FONT></DIV> <BLOCKQUOTE style="PADDING-RIGHT: 0px; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: rgb(0,0,0) 2px solid; MARGIN-RIGHT: 0px"> <DIV class=im> <DIV style="FONT: 10pt arial; font-size-adjust: none; font-stretch: normal">----- Original Message ----- </DIV> <DIV style="BACKGROUND: rgb(228,228,228); FONT: 10pt arial; font-size-adjust: none; font-stretch: normal; -moz-background-clip: border; -moz-background-origin: padding; -moz-background-inline-policy: continuous"><B>From:</B> <A title=pbewig@gmail.com href="mailto:pbewig@gmail.com" target=_blank>Phil Bewig</A> </DIV> <DIV style="FONT: 10pt arial; font-size-adjust: none; font-stretch: normal"><B>To:</B> <A title=jos.koot@telefonica.net href="mailto:jos.koot@telefonica.net" target=_blank>Jos Koot</A> </DIV> <DIV style="FONT: 10pt arial; font-size-adjust: none; font-stretch: normal"><B>Cc:</B> <A title=plt-scheme@list.cs.brown.edu href="mailto:plt-scheme@list.cs.brown.edu" target=_blank>plt-scheme@list.cs.brown.edu</A> </DIV></DIV> <DIV class=im> <DIV style="FONT: 10pt arial; font-size-adjust: none; font-stretch: normal"><B>Sent:</B> Thursday, November 05, 2009 4:02 PM</DIV> <DIV style="FONT: 10pt arial; font-size-adjust: none; font-stretch: normal"><B>Subject:</B> Re: [plt-scheme] order of magnitude</DIV> <DIV><BR></DIV></DIV><CODE style="FONT-FAMILY: courier new,monospace">(define (ilog b n)<BR>Ā  (let loop ((n n) (i -1))<BR>Ā Ā Ā  (if (zero? n) i<BR>Ā Ā Ā Ā Ā  (loop (quotient n b) (+ i 1)))))<BR><BR>(ilog 10 #e1000e1000000) => 1000003<BR></CODE><BR style="FONT-FAMILY: courier new,monospace"> <DIV class=gmail_quote> <DIV class=im><SPAN style="FONT-FAMILY: courier new,monospace">It does take a while....</SPAN><BR><BR>On Thu, Nov 5, 2009 at 5:04 AM, Jos Koot <SPAN dir=ltr><<A href="mailto:jos.koot@telefonica.net" target=_blank>jos.koot@telefonica.net</A>></SPAN> wrote:<BR></DIV> <BLOCKQUOTE class=gmail_quote style="PADDING-LEFT: 1ex; MARGIN: 0pt 0pt 0pt 0.8ex; BORDER-LEFT: rgb(204,204,204) 1px solid"> <DIV bgcolor="#ffffff"><FONT face="Courier New" size=2> <DIV class=im>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:<BR><BR>(define log10 (inexact->exact (log 10)))<BR>(define (order-of-magnitude q) (floor (/ (inexact->exact (log q)) log10)))<BR><BR>However, due to inexactness of function log we find:<BR><BR>(/ (inexact->exact (log #e1000e1000000)) log10) --> close to but sligtly less than 1000003<BR><BR>and hence:<BR><BR>(order-of-magnitude #e1000e1000000) ; --> 1000002 <BR><BR>The wanted answer is 1000003. So I did the following:<BR><BR>(define order-of-magnitude<BR></DIV>Ā (let*<BR>Ā  ((log10 (inexact->exact (log 10)))<BR>Ā Ā  (10log (Ī» (q) (/ (inexact->exact (log q)) log10))))<BR>Ā  (Ī» (q)<BR>Ā Ā  (unless (and (rational? q) (exact? q) (positive? q))<BR>Ā Ā Ā  (raise-type-error 'magnitude "positive exact rational number" q))<BR>Ā Ā  (let* ((m (floor (10log q))) (k (expt 10 m)))<BR>Ā Ā Ā  ; >From now on all arithmetic operations and their operands are exact.<BR>Ā Ā Ā  (let loop ((m m) (lower (* k 1/10)) (middle k) (upper (* k 10)))<BR>Ā Ā Ā Ā  (cond<BR>Ā Ā Ā Ā Ā  ((<= q lower) (loop (sub1 m) (* lower 1/10) lower middle))<BR>Ā Ā Ā Ā Ā  ((>= q upper) (loop (add1 m) middle upper (* upper 10)))<BR>Ā Ā Ā Ā Ā  (else m))))))) <DIV class=im><BR><BR>(order-of-magnitude #e1000e1000000) ; --> 1000003<BR><BR>However, this seems rather complicated. Does someone have or know of a simpler and faster function for this purpose?<BR><BR>Thanks, Jos</DIV></FONT></DIV><BR>_________________________________________________<BR>Ā For list-related administrative tasks:<BR>Ā <A href="http://list.cs.brown.edu/mailman/listinfo/plt-scheme" target=_blank>http://list.cs.brown.edu/mailman/listinfo/plt-scheme</A><BR><BR></BLOCKQUOTE></DIV><BR></BLOCKQUOTE></DIV><BR>_________________________________________________<BR> For list-related administrative tasks:<BR> <A href="http://list.cs.brown.edu/mailman/listinfo/plt-scheme" target=_blank>http://list.cs.brown.edu/mailman/listinfo/plt-scheme</A><BR><BR></BLOCKQUOTE></DIV><BR></BLOCKQUOTE></BODY></HTML>