incorrect simple floating point math

Discussion of Common Lisp
Paul Donnelly
Posts: 148
Joined: Wed Jul 30, 2008 11:26 pm

Re: incorrect simple floating point math

Post by Paul Donnelly » Wed Jun 24, 2009 2:34 pm

findinglisp wrote:
simon wrote:If you're actually doing this stuff "for real", you probably want a BCD representation.
I can't think of a reason why you would prefer BCD over pure binary integers.
To my understanding, some accounting methods involve very specific rounding techniques based on base-10 encoding probably antedating computers in finance. Easier to execute this technique when your numbers are already base 10.

IANAA though, so I'm hazy on the details of this, if it's even right.

simon
Posts: 16
Joined: Wed May 13, 2009 9:12 am

Re: incorrect simple floating point math

Post by simon » Wed Jun 24, 2009 3:12 pm

findinglisp wrote:I can't think of a reason why you would prefer BCD over pure binary integers....
I wasn't as clear as I should have been, relying on the context of the rest of the thread. My commentary was also more general than lisp specific...

If you are doing serious accounting computations, you don't want to use floats, and you can't use 32 bit integers because they are just too small. As I understand it, the historical fix for this was to use BCD types, often assembly coded based on native integer types, or split bytes (4 bits per BCD digit). So setting this all up is a bit hairy but a) it's fast b) it's accurate c) the big accounting firms, govt. etc. already were happy with how it worked and would accept that.

As I (obliquely) pointed out earlier, though, these days with 64 bit machines heading toward ubiquity the issue is a bit different. Even a 64-bit lisp fixnums are probably big enough for most uses, you've got rounding room on trillions. You might have to resort to (unsigned-byte 64) to figure out the US budget though.

Of course nominally with common lisps numeric tower you could always have just resorted to bignums and used rationals to keep error at bay. As I understand it though, for "real" work of this type that would never have had a hope of being fast enough.

This is all sort of speculative, to be fair, from half remembered conversations who actually did code this stuff up for the big players. So I could be off somewhere....


Paul is also right, aiui, that there are very specific rounding rules, which can end up making you hand-roll a data type anyway.

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Re: incorrect simple floating point math

Post by findinglisp » Wed Jun 24, 2009 5:35 pm

The definition of BCD is simply hexadecimal where you ignore all values in the range of 11 - 15. That is, 0x0123 is the 16-bit BCD representation of 123. BCD doesn't imply bignums; you can have a 32-bit BCD number, representing quantities up to 0x99999999. To go over that limit, you either need to use 64-bit BCD or you need a bignum representation. Older mainframes actually had BCD arithmetic hardware to assist with BCD calculations (even the old 8-bit 6502 has some flags and helper instructions that made using BCD a bit easier), but they are never faster than using raw binary integers on the same machines, and sometimes slower depending on the implementation (on the 6502, for instance, where the support is only partial, basically handling carries out of one BCD digit to the next). If you do BCD in software, it's always slower than binary on any standard machine (again, because the native arithmetic doesn't handle the carries and borrows correctly, and no machine I know of has native multiply/divide instructions that work on BCD, so you have to do extra work to use BCD).

Paul D might be right that there are some odd rounding rules that are specific to financial calculations. I wouldn't know about that. It would be interesting to see some examples if anybody has any.
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

simon
Posts: 16
Joined: Wed May 13, 2009 9:12 am

Re: incorrect simple floating point math

Post by simon » Wed Jun 24, 2009 7:49 pm

Dave, I suspect we may be in violent agreement here.

Obviously BCD doesn't imply bignums, it's just an encoding. You can pack it two to a byte or not, that's not required either. But 32 bits just isn't big enough regardless --- they're fast but it doesn't matter ---so yes you're into bignum territory, or 64 bit BCD or whatever. And this has always been true, it's only recently that 64 bit native ints were available. So people wrote (typically asm) routines that would manipulate larger encodings, and yes some cpu's added support to hep you with the operations (including intel) . You could have done something similar with a bignum, but the related industry chose BCD over it, and I'm not sure why. If you're doing this for people who care about the details though, they'll be happy with a BCD lib, they might be happy by now with 64 bit ints unless they're super conservative or something, but they'll laugh at you if you wanted to use 32 bit or floats. So take that for whatever it's worth. I'm not sure how much of it is historical, fallout of everyone doing things for the z900s or something.

Lots of cpus have had at least some support for it though. Heck even x86 has rudimentary opcode support including somewhat limited support for bcd multiply/divide (unpacked only? I can't remember). So it's not quite ass exotic as you seem to suggest....

Anyway, the point isn't that there is native support for everything you want, historically there hasn't been, and I hope I didn't seem to suggest there was. However, once you accepted the fact that none of the native computations your CPU could do were acceptable, there were well understood ways to get implementations (taking what advantage of CPU features you could) of BCD operations that were both correct and fast.

[edit]
I forgot to add earlier, about rounding: I certainly don't know all the details, but I do know that different countries and even industries have different rounding conventions, particularly you may have variations on truncation at a certain precision, unbiased rounding (i.e. round to closest next unit, on 5's round up or down if odd or even), biased rounding (always round up on a trailing 5). I believe the 2nd of these is known as bankers rounding if it goes to the nearest even digit, so 0.035 -> 0.04 but so does 0.045. Sometimes you'll have different rules for tax computations and accounting. It gets worse though, the US stock market only recently became decimal! 2002 or so iirc.

Here is IBM's take on the subject.http://speleotrove.com/decimal/decifaq1.html, and more generally on decimal representations http://speleotrove.com/decimal/

This stuff comes up outside of finance too, of course, which is why for example IEEE-754 has multiple (4 iirc) rounding modes.

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Re: incorrect simple floating point math

Post by findinglisp » Thu Jun 25, 2009 10:43 am

simon wrote:Dave, I suspect we may be in violent agreement here.
We probably are. Apologies. I wasn't trying to hammer you. I was simply trying to dispute the notion that BCD must be chosen because of performance reasons. That simply isn't true. As Paul D said, there may be other reasons to choose it, but not performance.
Here is IBM's take on the subject.http://speleotrove.com/decimal/decifaq1.html, and more generally on decimal representations http://speleotrove.com/decimal/
Yup. That article is good, and it basically supports what I was saying. If you'll notice, most of it talks about BCD floating point, which I said was the one place were I could see BCD being interesting. IMO, BCD fixed point is basically a waste of time unless you need a particular special rounding mode that would depend on a BCD representation. Otherwise, it would seem that you're better off going with a binary fixed point representation.
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

simon
Posts: 16
Joined: Wed May 13, 2009 9:12 am

Re: incorrect simple floating point math

Post by simon » Thu Jun 25, 2009 3:07 pm

findinglisp wrote:I was simply trying to dispute the notion that BCD must be chosen because of performance reasons.
Which isn't actually a claim I ever made. Or at least, not one I meant to, I may have worded things badly. My point was always that you couldn't use native integers anyway, so with BCD you had a wider format with known correct properties that was fast enough, and with (pretty common) hardware support for some operations at least, much faster than anything you would do purely in software with a wider type. Now historically why exactly these decisions were made, I don't know.
findinglisp wrote:If you'll notice, most of it talks about BCD floating point
It talks about both, but again, it's not a distinction I claimed any differently about. Which is why I was a bit surprised at your seemingly vehement agreement with me :)

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: incorrect simple floating point math

Post by gugamilare » Thu Jun 25, 2009 6:52 pm

Well, here is what I think. BCD do have speed advantages over rationals and bignums under certain circunstances.

If you use rationals and make too many operations (without rounding the result), its numerator and its denominator usually grow indefinitelly (since the probability of the division to be simplifiable is low). Not to mention that a generic sum of rationals need two multiplications (to equalize the denominator of the fractions), a calculation of a gcd and two divisions of integers (to simplify the resulting fraction - divide it by the gcd). The result of every operation is potencially bigger than its operands. This means consing and having bigger and bigger numbers. If the numbers are growing, it means they are chewing up memory and operations with then get slower.

An alternative approach to this problem is to work with a structure like this:

Code: Select all

(defstruct decimal-float val exp)
to represent the number val*10^exp . With the appropriate roundings, it would be as realiable as BCDs, but this can be a speed headache for big numbers as well, since, for instance, every time you sum two numbers, you need to calculate a power (say, to sum 3*10^-3 with 2*10^-100 you need to multiply 3 with 10^97, and therefore you need to calculate 10^97 (unless you store a vector with the results, but this may chew up your memory pretty fast)). A power is a slow operation compared to a sum. Also, when you operate on two numbers, you will need to divide the value by the bigger power of 10 possible (so the result can ocuppy as little memory as possible and so that operations with these numbers are faster).

And, for the last in this analisys, bignums. If you are using bignums supposing that every number is a multiple of some pre-defined epsilon (say, 10^-100). I can see two problems. First, as the name says, epsilon is predefined. If you change it, it will ruin you available data. Second, if you want a small epsilon, then the representation of small integers will be multiples of a big quantity (in the example, 10^100), therefore slowing you computations for normal and big numbers and will chew up memory.

OTOH, a BCD float (using the same struct as before, with a BCD val and a base 10 exp) will be much more realiable. A sum will need a shift and a bignum-like sum (which is O(log(n)) just like a normal bignum sum) and a final shift to normalize the number. A multiplication will need a sum (of the exponents) and a bignum-like multiplication (which is O(log(n)* log(m)) when you multiply n by m), and then a normalization. And so on. It will also occupy as much memory as you need, not more, if you round them appropriately.

Ok, all these issues only appear if you are working with big numbers or need a big precision. But, in these case, I believe BCD would be faster than all these solutions in general operations. And, in general, it shouldn't be much slower than regular integers and rationals.

Just a final idea I've just had right now. Instead of assuming that 4 bits represent a digit, you can separate the number every 32 bits like if the numbers where coded in base 10^9 instead of base 10 (10^9 ocuppy 30 bits, since 2^30 bytes = 1 Mib ~ 1*10^9 bytes). (Hum, here 64 bits architecture win because a 64-bit number can represent a 19-digit decimal, and you don't just throw away any bits). For instance, if you have a bignum with 2 fields of 32 bits, then

0x0000 0001 0000 0000

represents the number 10^9, while

0x0000 0000 0000 000A

is valid and represents the number 10 as usual. This way you gain one more digit every 32 bits than normal BCDs and you can use hardware sum of numbers of 32 bits. But you throw away 2 precious bits. And the exp value of the struct could represent a power of 10^9 as well.It is even not hard to use, say, SBCL's internals to operate on bignums this way in a very similar way normal bignums are already implemented. Operations will be very much alike, except the normalization, so I bet the time taken for operations will not be greater than a factor of 1.5 that normal bignum operations take (bignums representing integers, not in a structure like the one above).

Well, I guess I'll just save you all from reading an even longer post. This seems to be a neat project for lisp, perhaps I'll do it during my vacations ;)

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: incorrect simple floating point math

Post by nuntius » Fri Jun 26, 2009 9:48 am

gugamilare wrote:This seems to be a neat project for lisp, perhaps I'll do it during my vacations ;)
If you tackle this, please read the specs on http://speleotrove.com/decimal/ first. They represent an IEEE standard decimal encoding much like what you are thinking about. Implementing specs is generally more useful (if less fun) than reinventing your own; you learn different things through both approaches.

BTW, the IEEE spec has several opportunities to show off CL's features. For example, special variables could specify rounding modes, etc. Likewise restartable conditions could handle the various error cases.

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Re: incorrect simple floating point math

Post by findinglisp » Fri Jun 26, 2009 11:24 pm

simon wrote:
findinglisp wrote:I was simply trying to dispute the notion that BCD must be chosen because of performance reasons.
Which isn't actually a claim I ever made. Or at least, not one I meant to, I may have worded things badly. My point was always that you couldn't use native integers anyway, so with BCD you had a wider format with known correct properties that was fast enough, and with (pretty common) hardware support for some operations at least, much faster than anything you would do purely in software with a wider type. Now historically why exactly these decisions were made, I don't know.
findinglisp wrote:If you'll notice, most of it talks about BCD floating point
It talks about both, but again, it's not a distinction I claimed any differently about. Which is why I was a bit surprised at your seemingly vehement agreement with me :)
Okay, we're in agreement. Sorry for the confusion. :)
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

Post Reply