incorrect simple floating point math

I am using Lisp-in-a-box (Clisp) and it is a hit and miss kind of thing with doing simple math. Sometimes I would get the correct answer and other times I get odd results. Here are a few examples of what I actually typed:

Correct:
(+ 2 2.4 5.1)
9.5

Wrong:
(+ 2 4.2 8.4)
14.599999

Any idea what is going on?

There is nothing incorrect in the examples you posted. Please review the following links.

Wikipedia
http://en.wikipedia.org/wiki/Floating_point

"What Every Computer Scientist Should Know About Floating-Point Arithmetic"
http://docs.sun.com/source/806-3568/ncg_goldberg.html

~ Tom

speech impediment wrote:I get odd results

If these kinds of floating point errors are actually a problem, you have the option of avoiding floating point all together. You could use rational number arithmetic.

(+ 2 12/5 51/10)
(+ 2 46/5 42/5)

...which could be facilitated by using the RATIONALIZE function in CL.

(apply #'+ (mapcar #'rationalize '(2 2.4 5.1)))

If these kinds of floating point errors are actually a problem, you have the option of avoiding floating point all together. You could use rational number arithmetic.

Wow... is this how most programmers program mathematically when using numbers with decimal points? If not, how does one generally program with mathematical accuracy? I've been reading links for a while and it seems like there isn't an easy solution to doing accurate math. Maybe Vedic Mathematics?

Financial calculations are performed using decimal (base10) as opposed to binary (base 2) arithmetic. In decimal arithmetic, your examples would give the same results you learned in school. In binary arithmetic, there are no exact representations for 1/5, 1/25, 1/125, etc.; thus you see "errors" in the calculation.

Most decimal calculations are done using "binary coded decimal", where each 4 binary bits (0-15) is used to store one decimal digit (0-9).

Surprisingly, a bit of searching around didn't turn up any decimal arithmetic libraries for CL. If someone wanted to write one, I would recommend that they start by reading the docs on the following page.
http://speleotrove.com/decimal/

speech impediment wrote:

If these kinds of floating point errors are actually a problem, you have the option of avoiding floating point all together. You could use rational number arithmetic.

Wow... is this how most programmers program mathematically when using numbers with decimal points? If not, how does one generally program with mathematical accuracy? I've been reading links for a while and it seems like there isn't an easy solution to doing accurate math. Maybe Vedic Mathematics?

Most programmers just get it wrong.

The ones who really care about numerical results have scars to prove it.

speech impediment wrote:

Wow... is this how most programmers program mathematically when using numbers with decimal points? If not, how does one generally program with mathematical accuracy? I've been reading links for a while and it seems like there isn't an easy solution to doing accurate math. Maybe Vedic Mathematics?

If you want "mathematical accuracy" then you need rational numbers. Any floating point arithmetic will need to round numbers (and this will inevitably make the sum operation not associative). The decimal base is no less of an issue than binary base (there is no way represent 1/3 or 2/3 in a finite decimal number, but in base 3 this is an easy task). The difference in this problem is that you are providing simple decimal numbers and converting them to binary representation.

I also faced this problem once, when I made a simple money change calculator - you provide an amount of money and it returns how many and which coins you should use to pay. For instance:

(exchange 0.64) =>
1 coin of 50 cents
1 coin of 10 cents
4 coins of 1 cent

The solution I came up with was to multiply the number by 100 and round it before calculating the amount of coins.

Wow... is this how most programmers program mathematically when using numbers with decimal points? If not, how does one generally program with mathematical accuracy? I've been reading links for a while and it seems like there isn't an easy solution to doing accurate math. Maybe Vedic Mathematics?

Floating point numbers are extremely useful, but in order to get sensible results you need to know what they are and what you are doing.

People have noted things like BCD and other techniques, but the thing you have to realize is that there is no single "right" answer to the fundamental problem that you can't represent an arbitrary real number to full precision in a computer.

BCD works well because the fractional part is of known magnitude.

Basically, floating point numbers are rational approximations to real numbers that a) have a fixed precision and b) are logarithmically distributed over a large range of magnitudes. This is extremely useful but as you've already found out, if you just treat them as real numbers you'll run into grief easily.

Since someone mentioned financial calculations: Never do financial calculations with floats!

Floats are just a representation for non-integer, non-rational measurements. Their accuracy is, of course, limited by the number of places after the point. A base 2 float with x places after the point naturally has less precision than a base 10 float with x places. If you are converting a base 2 float with 10 places to base 10, then anything after the first 3 places of the result cannot be actual information coming from the base 2 float.

If you have precise fractions, don't use floats. The simplest way in Common Lisp is to use rationals, and convert input with RATIONALIZE and output for display with FLOAT. For fixed-point arithmetic (like financials), just using integers as multiples of the lowest unit (e.g. cents) is also a good way.

nuntius wrote:Most decimal calculations are done using "binary coded decimal", where each 4 binary bits (0-15) is used to store one decimal digit (0-9).

Surprisingly, a bit of searching around didn't turn up any decimal arithmetic libraries for CL. If someone wanted to write one, I would recommend that they start by reading the docs on the following page.
http://speleotrove.com/decimal/

Interestingly, old HP calculators used to use a form of "floating point BCD" (my term, not HP's), if I remember correctly. Each number was stored internally as a significand, represented in BCD, and an exponent, just like an IEEE float, but for the change of representation of the significand. It was sort of a best-of-both worlds technique that allowed the calculators to avoid many of the binary representation hiccups that have been discussed in this thread, but still gave them a large range for calculations. If you're seriously interested in numerical work, studying these old calculators is really eye opening. They were remarkably well-engineered. I honestly wish I still had my old HP-15C. It was the best calculator I ever owned and only died sometime in the middle of college, circa 1988.

Harleqin wrote:Since someone mentioned financial calculations: Never do financial calculations with floats!
...
If you have precise fractions, don't use floats. The simplest way in Common Lisp is to use rationals, and convert input with RATIONALIZE and output for display with FLOAT.

You know, the RATIONALIZE and FLOAT combo seems to be the most sensible way. It's funny that I thought it was a good idea for stock prices to move from fractions to decimals. If I remember correctly, Bernie Madoff was partly responsible for stock prices being quoted in decimals. I'm not sure how the programmers at NASDAQ responded to that idea... hehe.

Harleqin wrote:For fixed-point arithmetic (like financials), just using integers as multiples of the lowest unit (e.g. cents) is also a good way.

I was pondering about this solution as well. I figure I could have a program count the decimal places, multiply them, and finally convert the results of operations back to decimal numbers, but I'm not sure how efficient it is compared to the RATIONALIZE-FLOAT combo...

speech impediment wrote:

Harleqin wrote:

Harleqin wrote:For fixed-point arithmetic (like financials), just using integers as multiples of the lowest unit (e.g. cents) is also a good way.

I was pondering about this solution as well. I figure I could have a program count the decimal places, multiply them, and finally convert the results of operations back to decimal numbers, but I'm not sure how efficient it is compared to the RATIONALIZE-FLOAT combo...

As long as the numbers stay inside the FIXNUM range, calculating in cents should be faster. Beyond that, it is a tradeoff between BIGNUM and RATIO arithmetic overhead.

Harleqin wrote:As long as the numbers stay inside the FIXNUM range, calculating in cents should be faster. Beyond that, it is a tradeoff between BIGNUM and RATIO arithmetic overhead.

Which is why it often is a good idea to use floats...use them as 53 bit hardware-supported big-fixnums...

Paul wrote: Which is why it often is a good idea to use floats...use them as 53 bit hardware-supported big-fixnums...

Paul is quite right, the "never use floating point for financial computations" idea is overly stated. Floats are perfectly accurate and fast for integer and decimal computations like this so long as you can be certain to stay in the representable range. Which isn't always the case.

Of course these days you may not even need to resort to floats:

* (log most-positive-fixnum 2)
60.0

simon wrote: Paul is quite right, the "never use floating point for financial computations" idea is overly stated. Floats are perfectly accurate and fast for integer and decimal computations like this so long as you can be certain to stay in the representable range. Which isn't always the case.

By representable range you mean a bit less than (* 1d-2 (/ long-float-epsilon)), right? The whole deal with "never use floating point for financial computations" is that money violates the pretty fundamental assumption of floating point values, that we don't care about numbers sufficiently smaller than the most significant digit. People for some reason care about pennies even when dealing with millions. Of course, the representable range on my imp seems to be around 10^14 dollars, which is a lot of money.

If you must store money with a binary type, its probably better to store integers representing cents (or tenths or hundredths of a cent -- i.e. fixed-point) than to store doubles representing dollars. For addition and subtraction, it doesn't matter; but for multiplication (interest, taxes, etc), proper rounding is critical.

smithzv wrote: By representable range you mean a bit less than (* 1d-2 (/ long-float-epsilon)), right? The whole deal with "never use floating point for financial computations" is that money violates the pretty fundamental assumption of floating point values, that we don't care about numbers sufficiently smaller than the most significant digit. People for some reason care about pennies even when dealing with millions. Of course, the representable range on my imp seems to be around 10^14 dollars, which is a lot of money.

No, not at all.

Recall that floating point representations are by nature capable of storing a certain range of integers exactly. In an IEEE 754 double precision float there are 53 (52 without hidden bit) bits representing the significand, and a sign bit. This is much larger than 32 bit integers. So if you are careful , it is entirely possible to to error free computations on integer values while taking advantage of both the speed and width available in your FPU. You still have to shift the computations to account for decimals. You've got a range of a little under 10^16, so even with 5 significant decimal digits (you could still count up to ten billion dollars or so, maybe drop another one for safe bound. I forget if banks use more than 5 decimal digits (i.e. 1000th of cent), adjust if needed. So this really doesn't run into trouble except at the nation level or very large financial company. But it does come up there, so you couldn't do it in any system that might be used for large transactions, or other ways to bump you out of the range (currency conversions could do it).

You do have to be careful though, because if you screw up and have any operation go outside the range of exactly representable integers, you've had it.

nuntius wrote:If you must store money with a binary type, its probably better to store integers representing cents (or tenths or hundredths of a cent -- i.e. fixed-point) than to store doubles representing dollars. For addition and subtraction, it doesn't matter; but for multiplication (interest, taxes, etc), proper rounding is critical.

Right, when I referred to using floats, obviously I meant that you can use floats to exactly represent integers which represent (fractions of a ) cents or whatever.

However, rounding is also something you have to be careful with. FPUs generally have various possible settings for this, and different floating point standards have different ways of dealing with it. If you're writing code with currency computations, you'll need to familiarize yourself with how to make your system behave in the right way to match the definitions your system must adhere to, which as I understand it are not universal (but I could be wrong about that).

All in all, floats probably are the wrong way to go about this --- but not for the reasons mostly given here. Many programmers are fundmentally pretty confused about what floating point numbers are. Many are also a bit confused about currency computations, if they've thought about them at all. Putting those two together can't help.

In case anyone is at all confused about this, I should note I really don't recommend using floats for currency computations, for several reasons. I just think if you're going to reject something, you should reject it for the right reasons, and not propagate more misunderstandings. I was also noting that with 64 bit systems the same sort of games can be played with native ints and you get the speed and width with less hassle.

If you're actually doing this stuff "for real", you probably want a BCD representation.

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. Rounding and division problems only occur for the fractional part of the computation, so IMO the only reason to use BCD would be with the interesting BCD+floating point scheme I described previously with HP calculators, so the representation of a fractional number can be exactly the same as with standard decimal arithmetic. Even if you're doing currency calculations and you store all numbers as an integer number hundredths of a cent ($0.0001), I'm guessing you would have enough precision for basic rounding for most computations. In other words, bignums plus a large scaling factor should work for just about all financial calculations; no need to use BCD. If you're doing a long chain of calculations and want to avoid intermediate round-off, then rationals are also your friend.

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.

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.

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.

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.

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.

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

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:

(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

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.

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.