rick@tetrauk.UUCP (Rick Jones) (08/06/90)
Thanks to all those who responded to my query about exactness (or lack of it) in FP numbers. It has confirmed my suspicion that there isn't a clean solution to this problem. The responses can be grouped into 3 broad categories: a. "The effective precision is a function of the algorithm and initial data, not just the representation" While this is true, the representation puts a limit on the precision even when the algorithm may suggest something higher. But more fundamentally, this is an issue of _precision_ as opposed to _exactness_, which are not quite the same. If the context is dealing with real-world values, they can all be assumed to be irrational, and known only to within some understood precision. When dealing with more artificial numbers (see below), they are presumed to be exact, and unexpected problems arise because there is not a 1-1 correspondence between exact decimal numbers and exact binary FP numbers. As my example showed, you don't _expect_ to get into precision issues when checking if .291/2 = .1455 b. "Analyse the bit-pattern of the IEEE format" This came from Stefan & Carlos at U. of Basel, and although possible, it feels a bit non-portable & hardware specific. We write portable packages which run on all sorts of hardware - just how universal IS the IEEE format? (that's not an entirely rhetorical question) c. The "constructive reals" solution This is interesting, and I will follow up the various references. It seems quite well-known, but sounds a bit computationally expensive, though I don't know enough yet to make a qualified comment. d. The "continued fractions" solution The reference to this came from Colin Plumb, and is also something I shall follow up. It appears to have an advantage that all rational numbers have a finite representation. For interest (if anyone's still with me :-), I'll explain the problem domain. I deliberately omitted this from my initial query to get as wide a response as possible. This is nothing more taxing (!) than business systems, which are not known for requiring complex mathematics. They don't, but they do require exactness. Auditors have this annoying view that accounts must balance to the penny, not 1 part in 10 to-the-something. There is a good case for using some form of BCD representation, but there are many programming advantages in using the embedded numerical types of the language (yes, I do know about OOP and building a BCD class with overloaded operators, that's one of my options). In fact, the only disadvantage of FP is the exactness issue. 15 significant digits is enough, the 8-byte repesentation is compact and fixed, the arithmetic operators are embedded and the computation done in an FPP in all except toy computers. Unfortunately, exactness cannot be controlled by applying a system-wide precision in terms of decimal places. To illustrate: My system may be handling currency values in units of Lira, Yen, or some other inconsiderate currency with a very small basic denomination, and need to go up to quantities of 10^9 or more. I may also have some stock kept in bulk, and need to account for quantities down to 4 decimal places. This total range is pushing the limits, but no one figure needs that total range of precision - I never account for less than 1 Yen, and I'm not going to have a billion tons of bulk stock. Andrew Koenig appreciated this problem; as he said: Floating point arithmetic is *hard*. Precision is dealt with in the appropriate places by rounding, but even this causes a problem. I notice that no one tried to provide a solution to the second, and in many ways more subtle, problem in my original posting. Given that the supposed exact but unrepresentable value of .1455 has been arrived at by two different means where the actual values are incrementally above and below, and we simply want to round the result to 3 decimal places: simplistic rounding will actually _increase_ the discrepancy by yielding .145 and .146 respectively. Comparison of the values before rounding would indicate them equal within 15 significant digits. After rounding, they show a difference in the 3rd digit. Accountants find this sort of thing difficult to grasp! I actually have a general solution for this, but it involves sprintf() and some sneaky string manipulation, and is hardly elegant. Thanks for the ideas, they have provided food for thought. I shall be on holiday for the next 3 weeks; if you have any Earth-shattering solutions which haven't come up so far, could you e-mail me please? -- Rick Jones You gotta stand for something Tetra Ltd. Maidenhead, Berks Or you'll fall for anything rick@tetrauk.uucp (...!ukc!tetrauk.uucp!rick) - John Cougar Mellencamp
henry@zoo.toronto.edu (Henry Spencer) (08/08/90)
In article <713@tetrauk.UUCP> rick@tetrauk.UUCP (Rick Jones) writes: >... This is nothing more taxing (!) than business systems, which are not >known for requiring complex mathematics. They don't, but they do require >exactness. Auditors have this annoying view that accounts must balance to the >penny, not 1 part in 10 to-the-something. There is a good case for using some >form of BCD representation, but there are many programming advantages in using >the embedded numerical types of the language... Our own experience, in building accounting systems for our own use, is that the problem can often be eliminated by ignoring the decimal point in dollar currencies and thinking of money as measured in pennies. Then integer arithmetic suffices, if amounts are not huge. If amounts *are* huge, note that most floating-point boxes will do precise integer arithmetic if you are careful to avoid operations that necessarily produce fractions. Yes, you get fractional amounts if you (say) buy 3.5 tons of stuff that is priced at $1.17 per ton... but there really *is* a fractional amount there, and the proper response is to explicitly round it in whatever way is appropriate to the problem (in this case, the standard business approach of rounding up). This isn't necessarily an adequate solution to tricky cases involving things like multiple currencies, but for simple stuff, it's amazing how much simpler the problem gets if you don't insist on representing money as a fraction just because it's written that way. -- The 486 is to a modern CPU as a Jules | Henry Spencer at U of Toronto Zoology Verne reprint is to a modern SF novel. | henry@zoo.toronto.edu utzoo!henry
johnb@srchtec.UUCP (John Baldwin) (08/09/90)
In article <1990Aug7.173030.2823@zoo.toronto.edu> henry@zoo.toronto.edu (Henry Spencer) writes: >In article <713@tetrauk.UUCP> rick@tetrauk.UUCP (Rick Jones) writes: >> Auditors have this annoying view that accounts must balance to the >>penny, not 1 part in 10 to-the-something. There is a good case for using some >>form of BCD representation, but there are many programming advantages in using >>the embedded numerical types of the language... > >Our own experience, in building accounting systems for our own use, is that >the problem can often be eliminated by ignoring the decimal point in dollar >currencies and thinking of money as measured in pennies. Doesn't this push him back into the "continued sums" implementation? Remember, conversion rates between different currencies "slide" up and down at a fairly high frequency. (Does anybody know just HOW frequently the exchange rates change?) This would require an INTERNAL currency which would probably NOT be the same as a recognized world currency; one in which any unit of any other world currency can be expressed as an integer. This is probably tricky enough to find WITHOUT having the conversions changing on you all the time! Rick: how many currencies do you have to deal with and how often do they change? Maybe this *would* be a feasible approach: if the numbers are too big for a (long), store them in a struct. Have a multidimensional array of structs containing numerators and denominators for conversions. -- John T. Baldwin | johnb@srchtec.uucp Search Technology, Inc. | johnb%srchtec.uucp@mathcs.emory.edu standard disclaimer: | ...uunet!samsung!emory!stiatl!srchtec.. opinions and mistakes purely my own. | ...mailrus!gatech!stiatl!srchtec...