I happened to observe this commit from today by Neil Toronto:<br><br><a href="http://git.racket-lang.org/plt/commitdiff/47fcdd4916a2d33ee5c28eb833397ce1d2a515e2">http://git.racket-lang.org/plt/commitdiff/47fcdd4916a2d33ee5c28eb833397ce1d2a515e2</a><br>
<br>I may have some useful input on this, having dealt with similar problems myself.<br><br>The problem: Given b and x, you want to find the largest integer n such that b^n &lt;= x (or, for the ceiling problem, the smallest integer n such that b^n ≥ x).  This can profitably be viewed as a case of a more general problem: given a monotonically increasing but otherwise opaque function f, find the largest integer n such that f(n) ≤ x.  The previous algorithm to solve this can now be viewed as a linear search, taking n steps.  This took too long, and Neil Toronto replaced it with an algorithm that depended on floating-point numbers; but I hate to see that happen, because floats will screw up when the numbers get too large; careful reasoning may prove that floats will be sufficiently accurate for a given application, but it would be nice to have an exact algorithm so that one didn&#39;t have to do that.<br>
<br>I come here to present such an algorithm.  Simply put: Use a binary search rather than a linear search.  How do we do binary search on &quot;the nonnegative integers&quot;?  Well, start with 0 and 1 as your bounds, and keep doubling the 1 until you get something that&#39;s actually too high; then you have a real lower and upper bound.  This will take log(n) steps to find the upper bound, and then a further log(n) steps to tighten the bounds to a single integer.  Thus, this takes roughly 2*log(n) steps, where each step involves calculating (expt b n) plus a comparison.  It might be possible to do slightly better by not treating b^n as a black box (e.g. by using old results of b^n to compute new ones rather than calling &quot;expt&quot; from scratch, or by using &quot;integer-length&quot; plus some arithmetic to get some good initial bounds), but I suspect this is good enough and further complexity is not worth it.<br>
<br>Note that this algorithm should work perfectly with any nonnegative rational arguments [other than 0 for b or x, and 1 for b], and should give as good an answer as any with floating-point arguments.  Also, &quot;integer-finverse&quot;, as I called it, might be useful for many other &quot;floor&quot;-type computations with exact numbers (I have so used it myself in an ad hoc Arc math library).<br>
<br>;Finds n such that n &gt;= 0 and f(n) &lt;= x &lt; f(n+1) in about 2*log(n) steps.<br>;Assumes f is monotonically increasing.<br>(define (integer-finverse f x)<br>  (define upper-bound<br>    (let loop ((n 1))<br>      (if (&gt; (f n) x)<br>
n<br>          (loop (* n 2)))))<br>  (define (search a b) ;b is too big, a is not too big<br>    (let ((d (- b a)))<br>      (if (= d 1)<br>          a<br>          (let ((m (+ a (quotient d 2))))<br>            (if (&gt; (f m) x)<br>
(search a m)<br>                (search m b))))))<br>  (search (quotient upper-bound 2) upper-bound))<br><br>(define (floor-log/base b x)<br>  (cond ((&lt; b 1) (- (ceiling-log/base (/ b) x)))<br>        ((= b 1) (error &quot;Base shouldn&#39;t be 1.&quot;))<br>
((&lt; x 1) (- (ceiling-log/base b (/ x))))<br>        (else (integer-finverse (lambda (n) (expt b n)) x))))<br><br>(define (ceiling-log/base b x)<br>  (cond ((&lt; b 1) (- (floor-log/base (/ b) x)))<br>        ((= b 1) (error &quot;Base shouldn&#39;t be 1.&quot;))<br>
((&lt; x 1) (- (floor-log/base b (/ x))))<br>        (else<br>         (let ((u (floor-log/base b x)))<br>           (if (= x (expt b u))<br>               u<br>               (+ u 1))))))<br><br><br>Testing:<br><br>
&gt; (floor-log/base 10 3)<br>0<br>&gt; (floor-log/base 3 10)<br>2<br>&gt; (ceiling-log/base 3 10)<br>3<br>&gt; (ceiling-log/base 1/3 10)<br>-2<br>&gt; (floor-log/base 1/3 10)<br>-3<br>&gt; (floor-log/base 2/3 10)<br>-6<br>
&gt; (ceiling-log/base 2/3 10)<br>-5<br>&gt; (exact-&gt;inexact (expt 3/2 6))<br>11.390625<br>&gt; (exact-&gt;inexact (expt 3/2 5))<br>7.59375<br><br>I might add, by the way, that I&#39;m inclined to expect the base to be a second, optional argument (perhaps defaulting to 10) to a function called simply &quot;floor-log&quot; or &quot;ceiling-log&quot;.  I don&#39;t know if that fits with desired conventions, though.<br clear="all">
<font face="arial, sans-serif">--John Boyle</font><div></div><div><font face="arial, sans-serif"><i>Science is what we understand well enough to explain to a computer. Art is everything else we do.</i> --Knuth</font></div>
<br>