Hello, I'm working in MacGambit scheme where I found that CEILING
for reasons I don't understand doesn't return an integer, and as I
need to depend on this I decided to code ceiling myself. It only need
take positive flonums, and it should round upwards to the smallest
int greater than its input.
This is what I came up with and I'm wondering whether it's correct
from a number theoretical point of view. (pardon my scheme, it's no
longer obvious to me how to rewrite this without the named let):
(define (ceil x)
(let loop ((c 1) (two-to-the-c-minus-1 1))
(let ((two-to-the-c (expt 2 c)))
;; find the least power of 2 > x
(cond ((= two-to-the-c x) two-to-the-c) ; win
((< two-to-the-c x) ; try next power of 2
(loop (+ 1 c) two-to-the-c))
((> x (- two-to-the-c 1)) ; win
two-to-the-c)
;; x is between 2^C-1 and 2^C
(else (ceil-2 x two-to-the-c-minus-1 (- c 2) +))))))
(define (ceil-2 x low mod f)
(LET ((try (f low (expt 2 mod))))
(cond ((= try x) try) ; win
((< try x) ; too small,
; so add 2^mod-1
(ceil-2 x try (- mod 1) +))
((> x (- try 1)) ; win
try)
(else
(> try x) (ceil-2 x try (- mod 1) -))))) ; too big, subtract
; 2^mod-1
This is ok:
: (ceil 8888888.8)
8888889
But what's happnening here?
: (ceil 87283974957892374892574380975.9)
87283974957892377030546161664
-- eliot
Eliot Handelman <·····@generation.NET> writes:
> Hello, I'm working in MacGambit scheme where I found that CEILING
> for reasons I don't understand doesn't return an integer, and as I
> need to depend on this I decided to code ceiling myself.
[...]
Being a Scheme programmer, haven't you found that you often need to
implement or reimplement a lot of functions that should either "just
be there" or "just work right"?
My suggestion would be to ditch this "MacGambit scheme" and migrate to
Lisp, or another Scheme with correct library support for your
application, or some other language if this is an option. I recently
had to waste a lot of time programming my own MOD and a number of
other similar procedures for SIOD because I needed to automate a
number of procedures for the The GIMP.
[Since The GIMP also supports extension through Perl and Python, I
will be using one of these instead of God-awful SIOD for future work
with it.]
Christopher
In article <··············@2xtreme.net>, ······@2xtreme.net
(Christopher R. Barry) wrote:
;Eliot Handelman <·····@generation.NET> writes:
;
;> Hello, I'm working in MacGambit scheme where I found that CEILING
;> for reasons I don't understand doesn't return an integer, and as I
;> need to depend on this I decided to code ceiling myself.
;
;[...]
;
;Being a Scheme programmer, haven't you found that you often need to
;implement or reimplement a lot of functions that should either "just
;be there" or "just work right"?
;
I'm basically a lisp programmer, I got into scheme because MacGambit is
the most robust free (or whatever the arrangement is) "lisp" for the
mac
and I've come to like theleanness of the language. The only thing that
stands in the way of getting CLtL to run in scheme is the distinction
between #f and (), but I think scheme's right about that. Otherwise I
have most of CL up. The only thing I haven't altered is the reader, but
that wouldn't be hard. The only thing I really miss is a good emacs
editor.
* Eliot Handelman wrote:
> This is what I came up with and I'm wondering whether it's correct
> from a number theoretical point of view. (pardon my scheme, it's no
> longer obvious to me how to rewrite this without the named let):
I think something like this is `right'. I wrote this function (in CL)
for truncate (which, OK, is not what you want, but the idea of hunting
up powers of two is right I think):
(defun trunk (x)
(flet ((flaw (y)
;; Y assumed +ve.
;;
;; Find the biggest non-negative integer power of 2 less
;; than y, or zero if there is no such power, call this
;; g.
;; If g + 1 > x
;; then floor(y) = g,
;; else floor(y) = g + floor(y - g).
(let ((g (loop for i = 1 then (ash i 1)
while (<= i y)
finally (return (if (= i y) i (ash i -1))))))
(if (> (1+ g) y)
g
(+ g (flaw (- y g)))))))
(if (>= x 0)
(flaw x)
(- (flaw (- x))))))
But:
> : (ceil 87283974957892374892574380975.9)
> 87283974957892377030546161664
You're running out of float precision -- the best representation you
have of this number is probably equivalent to:
(ash 4961519548367754 44)
Which has a whole lot less precision (and is, not surprisingly, the
answer you got!). Which is why algorithms like mine and yours are
probably not really any good I think -- you end up doing lots of
integer/float comparisons, and those are fraught with danger, not to
mention you may well end up with floating overflow (at least in mine,
if you look at single-floats within a power of 2 of the top of the
single-float range.
However, the answers we both got are the same that the three Lisps I
tried got for their native TRUNCATE functions, so perhaps I'm wrong
and this is an OK way of doing it -- I think I'd need to read a bunch
of how-to-do-floating-point-right books to know -- perhaps the chapter
at the end of Hennessey & Patterson on floating point would be a place
to start.
--tim
Eliot Handelman wrote:
> Hello, I'm working in MacGambit scheme where I found that CEILING
> for reasons I don't understand doesn't return an integer,
I expect the reason is that Scheme distinguishes between
"exact" and "inexact" numbers, and CEILING probably isn't
supposed to return an exact answer when given an inexact
value, and most Schemes don't have inexact integers or
exact floating-point numbers. You could try sticking a
call to inexact->exact somewhere?
--
Gareth McCaughan ················@pobox.com
sig under construction
In article <··············@g.local>, Gareth McCaughan
<················@pobox.com> wrote:
;Eliot Handelman wrote:
;
;> Hello, I'm working in MacGambit scheme where I found that CEILING
;> for reasons I don't understand doesn't return an integer,
;
;I expect the reason is that Scheme distinguishes between
;"exact" and "inexact" numbers, and CEILING probably isn't
;supposed to return an exact answer when given an inexact
;value, and most Schemes don't have inexact integers or
;exact floating-point numbers. You could try sticking a
;call to inexact->exact somewhere?
You're right -- I guess is one of those scheme things that
I never bothered to look into when I switched from lisp. Thanks
for pointing that out.
-- eliot