[Haskell-cafe] k-th floorRoot

fool at sdf-eu.org fool at sdf-eu.org
Tue Sep 28 22:58:25 EDT 2004


Hi.

> floorRootDef, floorRoot :: Integer -> Integer -> Integer
> 
> floorRootDef k n | k>=1 && n>=1 = last (takeWhile (\x->x^k<=n) [1..])
> 
> floorRoot k n | k>=1 && n>=1 = h n where
>   h x = let y=((k-1)*x+n`div`x^(k-1))`div`k in if y<x then h y else x

(Oddly enough, you get an iteration formula for the _floor_ of the
k-th root just by putting _floor_ brackets around every quotient in
Newton's iteration formula for the k-th root.)

Exercise: Transform floorRootDef into floorRoot by
extensional-equality-preserving steps.  I don't know how to do this.

To conventionally prove the correctness of floorRoot, it suffices to
show for all integers k>=1, n>=1, x>=1, y:=[((k-1)*x+[n/x^(k-1)])/k],
r:=[n^(1/k)] ([] denoting floor):
  (1)  r<=y    (so r<=x is preserved in the iteration)
and
  (2)  x<=y --> x<=r    (so r<=x<=r when the break condition is met).
Using
       a<=[b] <--> a<=b
for all integers a and reals b, (2) is straightforward
and (1) is equivalent to
       k*r-(k-1)*x <= n/x^(k-1),
which by r^k<=n can be sharpened to
  (3)  k*(r-x)+x <= r^k/x^(k-1),
which is true by induction over k if (3) implies
       k*(r-x)+x + r-x <= r^k/x^(k-1) * r/x,
which indeed by (3) can be sharpened to
       k*(r-x)+r <= (k*(r-x)+x)*r/x,
equivalently (multiply by x and collect terms)
       0 <= k*(r-x)^2, done.

-- 
fool at sdf-eu.org
SDF-EU Public Access UNIX System - http://sdf-eu.org


More information about the Haskell-Cafe mailing list