<!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,&nbsp;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>&nbsp;</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>&lt;<A 
  href="mailto:jos.koot@telefonica.net">jos.koot@telefonica.net</A>&gt;</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>&nbsp;</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>&nbsp;</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>&nbsp;for 
    square roots. It would be nice to have something like 
    (integer-log-base-10/remainder n) --&gt; 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>&nbsp;</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>&nbsp; 
      (let loop ((n n) (i -1))<BR>&nbsp;&nbsp;&nbsp; (if (zero? n) 
      i<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (loop (quotient n b) (+ i 
      1)))))<BR><BR>(ilog 10 #e1000e1000000) =&gt; 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>&lt;<A href="mailto:jos.koot@telefonica.net" 
      target=_blank>jos.koot@telefonica.net</A>&gt;</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-&gt;exact (log 10)))<BR>(define (order-of-magnitude q) (floor 
        (/ (inexact-&gt;exact (log q)) log10)))<BR><BR>However, due to 
        inexactness of function log we find:<BR><BR>(/ (inexact-&gt;exact (log 
        #e1000e1000000)) log10) --&gt; close to but sligtly less than 
        1000003<BR><BR>and hence:<BR><BR>(order-of-magnitude #e1000e1000000) ; 
        --&gt; 1000002 <BR><BR>The wanted answer is 1000003. So I did the 
        following:<BR><BR>(define 
        order-of-magnitude<BR></DIV>&nbsp;(let*<BR>&nbsp; ((log10 
        (inexact-&gt;exact (log 10)))<BR>&nbsp;&nbsp; (10log (λ (q) (/ 
        (inexact-&gt;exact (log q)) log10))))<BR>&nbsp; (λ 
        (q)<BR>&nbsp;&nbsp; (unless (and (rational? q) (exact? q) (positive? 
        q))<BR>&nbsp;&nbsp;&nbsp; (raise-type-error 'magnitude "positive 
        exact rational number" q))<BR>&nbsp;&nbsp; (let* ((m (floor (10log 
        q))) (k (expt 10 m)))<BR>&nbsp;&nbsp;&nbsp; ; &gt;From now on all 
        arithmetic operations and their operands are 
        exact.<BR>&nbsp;&nbsp;&nbsp; (let loop ((m m) (lower (* k 1/10)) 
        (middle k) (upper (* k 10)))<BR>&nbsp;&nbsp;&nbsp;&nbsp; 
        (cond<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ((&lt;= q lower) (loop 
        (sub1 m) (* lower 1/10) lower 
        middle))<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ((&gt;= q upper) (loop 
        (add1 m) middle upper (* upper 
        10)))<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (else m)))))))
        <DIV class=im><BR><BR>(order-of-magnitude #e1000e1000000) ; --&gt; 
        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>&nbsp;For 
        list-related administrative tasks:<BR>&nbsp;<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>&nbsp;For 
    list-related administrative tasks:<BR>&nbsp;<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>