[
Date Prev][
Date Next][
Thread Prev][
Thread Next][
Date Index][
Thread Index]
Re: Mixed radix arithmetic
>To: "Ivan Godard" <igodard@xxxxxxxxxxx>
>Cc: stds-754@xxxxxxxx, dan@xxxxxxxxx
>Subject: Re: Mixed radix arithmetic
>From: Dan Zuras <dan@xxxxxxxxx>
>X-Resent-To: Multiple Recipients <stds-754@xxxxxxxxxxxxxxxxxx>
>X-Listname: stds-754
>X-Info: [Un]Subscribe requests to majordomo@xxxxxxxxxxxxxxxxxx
>X-Moderator-Address: stds-754-approval@xxxxxxxxxxxxxxxxxx
>
>
>> From: "Ivan Godard" <igodard@xxxxxxxxxxx>
>> To: "Dan Zuras" <dan@xxxxxxxxx>
>> Cc: <stds-754@xxxxxxxx>
>> Subject: Mixed radix arithmetic
>> Date: Thu, 27 Mar 2003 12:22:57 -0800
>>
>> Been thinking a little about the mixed radix problem, and have got this far:
>>
>> 1) I agree that mixed radix arithmetic operations are a language issue and
>> should not be addressed by the standard.
>
> Well, its only a problem in weak typed languages such as C
> since such expressions can't be formed in strong typed
> languages.
I don't see weak vs strong typing as an issue; there is no fundamental reason a
language couldn't have both binary and decimal floating-point types and define
automatic conversions between them.
[snip]
> BTW, although the known methods are all software methods, I
> believe it will soon be possible to implement them efficiently
> in hardware. Usually, base conversion is thought to be rare
> enough not to need hardware implementation. But, if mixed radix
> expressions start to be routine, someone will rethink that idea.
I believe all the known algorithms require extended precision operations; so
perhaps designing primitives to speed this sort of computation along would be a
more general approach.
>> 4) There should be a defined union set of NaNs, so that all NaNs are
>> representable in either radix implementation, whether they can be created in
>> the native radix or not.
>
> The radix of a Not a Number. An interesting concept, that.
>
> I believe I will disagree that this is necessary in any
> meaningful way but bring it up at the next meeting.
>
> After all, I may be wrong.
Preserving NaN bits through various conversions strikes me as more of a quality
of implementation issue rather than a spec issue since we have not imparted any
semantics to NaN bits other than a signaling/quiet distinction.
>> 5) I don't think that it is sufficient to define conversion as the result of
>> converting the sourse to a print string per the standard and then converting
>> the string to the destination. Intuition says that this will produce
>> conversions that are not the closest representable value, and maybe not even
>> very close at all.
If you want the "shortest string" to recover the original value, see Guy's
Steele's paper or David Gay's refinement. (Steele's algorithm determines the
exponent before the significand while Gay's algorithm sets the exponent
dependent on the significand; the latter gives shorter strings in some cases
near certain powers of 10.) If you want a fixed precision output, the issues
are a little different.
[snip]
> I believe someone posted a good bibliography on the subject
> [of base conversion] recently. As you are new to this discussion,
> perhaps that person could re-post them.
See attached.
Another reference,
I. B. Goldberg, "27 Bits are Not Enough for 8-Digit Accuracy," CACM, 10, 2,
February 1967, pp. 105-106.
-Joe
--- Begin Message ---
>X-Unix-From: dan@xxxxxxxxx Mon Jan 27 15:17:34 2003
>To: Eric Schwarz <eschwarz@xxxxxxxxxx>
>Cc: stds-754@xxxxxxxx, dan@xxxxxxxxx
>Subject: Re: first attempt at revised 754R draft with decimal formats
>From: Dan Zuras <dan@xxxxxxxxx>
>X-Resent-To: Multiple Recipients <stds-754@xxxxxxxxxxxxxxxxxx>
>X-Listname: stds-754
>X-Info: [Un]Subscribe requests to majordomo@xxxxxxxxxxxxxxxxxx
>X-Moderator-Address: stds-754-approval@xxxxxxxxxxxxxxxxxx
>
>> In regards to Dan's comments on conversions, note that conversion between
>> decimal internal and external decimal format as well as conversions to and
>> from integers will be exactly rounded. In regards to the general problem
>> with conversion of binary floating point to decimal floating point whether
>> external or internal, it is difficult. I am not sure we want to be exact
>> here since it may require thousands of execution cycles.
>
> When I mentioned the developments of the last 20
> years I was talking about the discovery of efficient
> algorithms for base conversion. Ask almost anyone
> about it at the next meeting. I'm sure someone can
> provide a current bibliography on the subject. - Dan
Matula published early work about base conversion:
David W. Matula, In-and-out conversions, Communications of the
ACM, vol. 11, no. 1, January 1968, pp. 47-50.
David W. Matula, A formalization of floating-point numeric base
conversion, IEEE Transactions on Computers, vol. C-19, no. 8,
August 1970, pages 681-692.
Algorithms in Coonen's thesis gave rise the the bounds in 754:
Jerome Coonen, Contributions to a Proposed Standard for
Binary Floating-Point Arithmetic, Ph.D. Thesis, University
of California, Berkeley 1984.
The main citations for correctly rounded input/output implementations are
William D Clinger, How to Read Floating Point Numbers Accurately,
Proceedings of the ACM Conference on Programming Language Design
and Implementation, June 20-22 1990, pp. 92-101.
Guy L. Steele, Jr., Jon L White, How to Print Floating-Point
Numbers Accurately, Proceedings of the ACM Conference on
Programming Language Design and Implementation, June 20-22 1990,
pp. 112-123.
David M. Gay, Correctly Rounded Binary-Decimal and Decimal-Binary
Conversions, Numerical Analysis Manuscript No. 90-10, AT&T Bell
Laboratories, Murray Hill NJ, 1990.
David Gay's algorithm is used in the gnu tool chain.
The more recent paper
Robert G. Burger, R. Kent Dybvig, Printing Floating-Point Numbers
Quickly and Accurately, Proceedings of the ACM SIGPLAN 96
Conference on Programming Language Design and Implementation, May
21-24, 1996, pp. 108-116.
has some misconceptions about the significance of the digits printed.
-Joe
>From mfc@xxxxxxxxxx Tue Jan 28 01:24:23 2003
X-Unix-From: mfc@xxxxxxxxxx Tue Jan 28 01:24:23 2003
Return-Path: <owner-stds-754@xxxxxxxxxxxxxxxxxx>
Received: from sfbaymail1sca.SFBay.Sun.COM (sfbaymail1sca [129.145.154.35])
by ha2sca-mail1.SFBay.Sun.COM (8.11.6+Sun/8.10.2/ENSMAIL,v2.1p1) with ESMTP id h0S9OMY23608
for <darcy@xxxxxxxxxxxxxxxxxxxxxxxxxx>; Tue, 28 Jan 2003 01:24:22 -0800 (PST)
Received: from sunmail3.sfbay.sun.com (sunmail3.SFBay.Sun.COM [129.149.247.180])
by sfbaymail1sca.SFBay.Sun.COM (8.12.2+Sun/8.12.2/ENSMAIL,v2.2) with ESMTP id h0S9OLg4008284;
Tue, 28 Jan 2003 01:24:21 -0800 (PST)
Received: from kathmandu.sun.com (kathmandu.Central.Sun.COM [129.147.5.36])
by sunmail3.sfbay.sun.com (8.11.6+Sun/8.11.6/ENSMAIL,v2.2) with ESMTP id h0S9OKB21329;
Tue, 28 Jan 2003 01:24:20 -0800 (PST)
Received: from ruebert.ieee.org (ruebert.ieee.org [140.98.193.10])
by kathmandu.sun.com (8.9.3+Sun/8.9.3) with ESMTP id CAA07456;
Tue, 28 Jan 2003 02:24:20 -0700 (MST)
Received: (from daemon@localhost)
by ruebert.ieee.org (Switch-2.2.4/Switch-2.2.4) id h0S9Mh120939
for stds-754-resent; Tue, 28 Jan 2003 04:22:44 -0500 (EST)
Importance: Normal
Sensitivity:
Subject: Re: first attempt at revised 754R draft with decimal formats
To: Dan Zuras <dan@xxxxxxxxx>
Cc: "Eric Schwarz" <eschwarz@xxxxxxxxxx>, stds-754@xxxxxxxx, dan@xxxxxxxxx
X-Mailer: Lotus Notes Release 5.0.7 March 21, 2001
Message-ID: <OF3B37E333.0BBAE004-ON80256CBC.0033389E@xxxxxxxxxxxxxxxxxxxxx>
From: "Mike Cowlishaw" <mfc@xxxxxxxxxx>
Date: Tue, 28 Jan 2003 09:22:08 +0000
X-MIMETrack: Serialize by Router on d06ml005/06/M/IBM(Release 5.0.9a |January 7, 2002) at
28/01/2003 09:22:31
MIME-Version: 1.0
Content-type: text/plain; charset=us-ascii
Sender: owner-stds-754@xxxxxxxxxxxxxxxxxx
Precedence: bulk
X-Resent-To: Multiple Recipients <stds-754@xxxxxxxxxxxxxxxxxx>
X-Listname: stds-754
X-Info: [Un]Subscribe requests to majordomo@xxxxxxxxxxxxxxxxxx
X-Moderator-Address: stds-754-approval@xxxxxxxxxxxxxxxxxx
Content-Length: 656
Status: RO
> When I mentioned the developments of the last 20
> years I was talking about the discovery of efficient
> algorithms for base conversion. Ask almost anyone
> about it at the next meeting. I'm sure someone can
> provide a current bibliography on the subject. - Dan
There's a partial bibliography on conversions (with abstracts) in my
decimal
bibliography, at:
http://www2.hursley.ibm.com/decimal/decbibconversion.html
Mike
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Mike Cowlishaw, IBM Fellow
IBM UK (MP5), PO Box 31, Birmingham Road, Warwick, CV34 5JL
mailto:mfc@xxxxxxxxxx -- http://www2.hursley.ibm.com/decimal
--- End Message ---