With apologies to George McFarland...
Alan Watson asked another excellent question:
> The description of number->string in section 11.7.4.4 says:
>
> "If a precision is specified, then the representations of the inexact
> real components of the result, unless they are infinite or NaN, specify
> an explicit <mantissa width> p, and p is the least p >= precision for
> which the above expression [read-write invariance] is true."
>
> Once we agree (!) what |p means, can someone point me to an algorithm to
> calculate "the least p >= precision" for which read-write invariance is true?
There are two different questions you might be asking.
I will attempt to answer both. First, though, let's
look at the first two levels of the Farscape taxonomy
of programming language conformance and safety.
(Why conformance and safety? Because I think some of
the R6RS editors think those concepts are closely
related.)
Spanky, also known as Dominar Rygel XVI, was born to
rule over the 600 billion subjects of the Hynerian
Empire [1]. Alas, his royal highness was deposed long
ago, and he alone remembers his greatness. Life is so
*unfair*.
Spanky has rules, and will let you know if you do not
show him enough respect by obeying them. "Spank, spank,
don't touch." [2] And so will Larceny's R6RS-conforming
mode, code-named Spanky [3].
Ka D'Argo's attitude is more pragmatic [4]. Rules are
for wimps. And so Larceny's R6RS-compatible mode [5]
is code-named D'Argo. D'Argo's goal is to run any
reasonable R6RS program, but who cares about the
unreasonable stuff some character like Spanky might
write into a conformance test suite?
Getting back to Alan's question: He might have been
asking for some mathematical algorithm that achieves
the strictest possible reading of the draft R6RS, the
sort of thing you would expect to be implemented by
Spanky mode. Or he might have been asking for some
practical algorithm that runs in O(finite) time, the
sort of thing you'd expect in D'Argo mode.
Spanky's answer to Alan's question is easy: Algorithm
Bellerophon [6] is parameterized by the precision p,
and Larceny already implements the necessary floating
point operations in software [7,8], so it's just a matter
of running Algorithm Bellerophon for the various values
of p, starting with the specified precision, until a
precision p is found that makes the expression true.
(I think p = precision should always work, but maybe
I'm missing something.)
D'Argo's answer is more interesting. Let's dispatch
the weakest cases first, under the simplifying
assumption that our implementation supports only
IEEE double precision. If precision = 53, then the
standard Algorithm Bellerophon or David Gay's dtoa.c
will do the job. If precision > 53, then you do the
best you can with 53 bits and add |precision at the
end.
If precision < 53, then you start out as you would in
R5RS Scheme, by converting an inexact real component x
to the shortest string that reads as x:
s := (number->string x);
p := precision;
#| this loop terminates with p <= 53 |#
while (not (eqv? (string->number
(string-append s "|" (number->string p)))
x)) {
p := p + 1;
}
s2 := trimFinalDigitRoundingDown (s);
s3 := trimFinalDigitRoundingUp (s);
#| now trim as many digits from s as you can |#
while (or (eqv? (string->number
(string-append s2 "|" (number->string p)))
x)
(eqv? (string->number
(string-append s3 "|" (number->string p)))
x))
if (eqv? (string->number
(string-append s2 "|" (number->string p))))
then s := s2
else s := s3;
}
return (string-append s "|" (number->string p));
That's pretty horrible. It wouldn't surprise me a bit
if it's slower than Spanky's algorithm.
D'Argo doesn't like the algorithm either, but he also
thinks anyone who passes the precision argument to
number->string should be taken out and shot, so he
doesn't let it bother him.
Getting back to Alan's previous question, about the input
problem of reading x|p: D'Argo would ignore the |p stuff
and compute the best 53-bit approximation y. Then he
would round to p+1 bits and examine the last 53-p bits,
the ones you would be discarding if you rounded to p bits.
Unless those bits consist of a 1 followed by all zeros,
rounding y to p bits will definitely give you the correct
answer. If bits consist of a 1 followed by all zeros,
however, then x lies almost exactly halfway between the
two nearest p-bit approximations.
So what would D'Argo do in that case? He'd round to p+1
bits instead of p. That might displease some armchair
language designer, but D'Argo is a warrior. He doesn't
care.
Because D'Argo's algorithm is more accurate than correct
rounding to p bits, which is what we can assume Spanky would
do, you would have an extremely hard time finding programs
for which Spanky's algorithm would work better than D'Argo's.
Will
[1]
http://en.wikipedia.org/wiki/Dominar_Rygel_XVI
[2]
http://en.wikipedia.org/wiki/George_McFarland
[3]
http://larceny.ccs.neu.edu/larceny-trac/wiki/SpankyMode
[4]
http://en.wikipedia.org/wiki/Ka_D%27Argo
[5]
http://larceny.ccs.neu.edu/larceny-trac/wiki/ConformanceModes
[6]
ftp://ftp.ccs.neu.edu/pub/people/will/howtoread.ps
[7]
http://larceny.ccs.neu.edu/larceny-trac/browser/trunk/larceny_src/src/Lib/Common/belle.sch
[8] That's one reason Larceny performs so poorly on the
sum1 benchmark [9].
[9]
http://www.ccs.neu.edu/home/will/Twobit/benchmarksAbout.html#sum1
Received on Thu Jun 28 2007 - 22:41:58 UTC