The Trouble With Rounding Floats

lukfil writes "We all know of floating point numbers, so much so that we reach for them each time we write code that does math. But do we ever stop to think what goes on inside that floating point unit and whether we can really trust it?"

Comments

Decimal Arithmetic

[(1 -sqrt(5))*(2**-1)]

From TFA:

Example 1: showing approximation error.

// some code to print a floating point number to a lot of
// decimal places
int main()
{
float f = .37;
printf("%.20f\n", f);
}

The main problem with that example, I take it, is that single-precision datatypes are only guaranteed for roughly seven decimal places; using double, of course, only defers the problem.

What about encoding floats as a pair of ints or longs: one to express the numerical value, and the other its tenth power; id est, decimal arithmetic?

Re:Decimal Arithmetic

[Anonymous Coward]

That gives you a much narrower range. Which is fine if it suits your application, but it's not sufficient for general use.

Re:Decimal Arithmetic

[Anonymous Coward]

That wastes a lot of bits.

Re:Decimal Arithmetic

[Anonymous Coward]

This is not newsworthy. This is computer science 101.

Re:Decimal Arithmetic

[Anomie-ous Cow-ard]

Since these are computers, and they deal primarily with binary internally, why not store the numerical value and the 2nd power instead? Oh, and since we generally need more bits of accuracy in the numerical value than the exponent (do you often deal with numbers 2**(2**32)?), why not allocate a "reasonable" number of bits to the exponent and leave more for the numerical value.

Uh oh, we just re-invented floating point. Oh well, nice try.

If you were just trying to get better accuracy by using base 10 rather than base 2, you're just hiding the problem (and making the hardware quite a bit more complex). If you want true accuracy, abandon floating point and use a bignum system.

Re:Decimal Arithmetic

[Anonymous Coward]

the real problem is that the person who started this thread DOESN'T think, most of us do. I can't believe that this is a "story" today. UGH!

Re:Decimal Arithmetic

[Waffle Iron]

What about encoding floats as a pair of ints or longs: one to express the numerical value, and the other its tenth power; id est, decimal arithmetic?

Is there any fundamental reason why decimal arithmetic in a computer should be more accurate than binary arithmetic in a computer? Both are approximations that use some small subset of the rational numbers to try to represent the entire continuous range of real numbers. Probably the only reason that decimal computer arithmetic seems better to people like accountants is that the errors it generates are the same errors that they've been manually creating for centuries.

Re:Decimal Arithmetic

[Anonymous Coward]

The problem of using your suggested method is that it is much much slower because there's no hardware implementation (and even the hardware implementation would, I imagine, be slower than the floating point one). It is slower, requires more die space (in terms of register storage & the size of the ALU), and is more complicated to design. I'm not saying that there's no point to implementing this in hardware (or increasing the precision), but there's reasons why it's not supported (and regardless of what representation you choose, you should always be aware of the limitations of the number system your using).

Re:Decimal Arithmetic

[Anonymous Coward]

Nah, this isn't 101. This isn't typically taught in 101. Floating point (the real floating point, not just using 'float' or 'double' keywords) is usually taught in computer hardware classes or scientific computing classes. Even there, they usually don't teach COBOL numbering system either.

Anyway, the article is stupid, probably geared toward people who haven't had the hardware classes.

Re:Decimal Arithmetic

[SageMusings]

Okay,

Show of hands: Who did not already understand that floats are approximations? Anyone? I didn't think so. I've gotta wonder why this story ever made it into Slashdot. This is more worthy of Time magazine where it can be spun as a startling new revelation into the dirtier corners of computer science and foisting a lie on the public.

Re:Decimal Arithmetic

[JNighthawk]

Example 1: showing approximation error. // some code to print a floating point number to a lot of // decimal places
int main()
{
float f = .37;
printf("%.20f\n", f);
}

I'd say the problem is they're trying to store a double in a float. If they wanted to store a float, they should have done:

float f = 0.37f;

Re:Decimal Arithmetic

[tomstdenis]

My college taught "numerical analysis" in the software comp.eng side. You learn the format of IEEE types, the range, accuracy, precision issues, etc.

We had assignments to not only perform matrix ops but also give the expected error, etc.

Maybe the author of the article should either go to a better school or pay more attention to the classes.

Tom

Re:Decimal Arithmetic

[Duhavid]

It is a little newsworthy.

I bothered to ask the question of what to use for monitary
usage at a financial institution in my recent past. I was
a bit ( pardon the pun ) suprised to get a blank stare, to
have to explain what I was talking about. Floats where good
enough. Course, I had a problem in .net with iterating thru
a list of values ( testing, each was .1, for 10% ), and the
sum wasnt 1.0. Had to do a bunch of

decimal.parse(value.ToString())

to get things to sum up correctly.

Re:Decimal Arithmetic

[Bender0x7D1]

Exactly. Unfortunately, there are too many people out there who are programmers, even good ones, who don't know, or understand, the basics. While I'm not claiming that formal education is the only way to get the knowledge you need, it is a good way to avoid gaps in your knowledge. I hated some of the computer science classes I had to take, but I did learn something important in each and every one of them.

Another advantage in the formal classes is you get the theory that allows you to make decisions on what data types to use and when. Sometimes you need the precision of BigNum systems, (crypto for example), and sometimes the accuracy of float is enough. For example, in a lot of financial applications, float would be good enough since 2 decimal places is enough. If you need performance, float will beat any BigNum system hands down. However, if you are dealing with decimals on top of decimals, (such as calculating someone's dividend from a mutual fund where they own partial shares), you might need BigNum. Either way, with the proper theory and good understanding of the formats, you can make these decisions.

These situations are why I am a big supporter of actual software engineering instead of programming. Sure, standard programming is great for a lot of situations, but serious applications need to use software engineering practices. You wouldn't build a bridge without an engineer, so why build an application that handles billions of dollars without applying the same rules and principles?

Re:Decimal Arithmetic

[Anonymous Coward]

From TFA: More important, perhaps, how do we avoid this problem? In a follow-up article I'm going to look at a different way of doing arithmetic (decimal arithmetic), used by lots of real world software, that avoids the approximation error in floats.

Re:Decimal Arithmetic

[Omega1045]

I have to agree. If I did not know this in high school, I certainly knew it in the first week or two of the first CompSci class I took my first semester at school. Not trying to be snotty, but this is really obvious stuff in the CompSci world.

Re:Decimal Arithmetic

[gweihir]

What about encoding floats as a pair of ints or longs: one to express the numerical value, and the other its tenth power

Old news. Of course that is the way to do it if you need exact decimals. If you have a limited range, then you can also just use one int and a fixed exponent, i.e. fixed-point arithmetric. Ise a long-number package (e.g. GNU mp) if you need more precision.

The whole article is about a very old and very well known and understood porblem. My guess is the real problem is the quality of the programmers that run into this and do not expect it.

Re:Decimal Arithmetic

[gweihir]

These situations are why I am a big supporter of actual software engineering instead of programming. Sure, standard programming is great for a lot of situations, but serious applications need to use software engineering practices. You wouldn't build a bridge without an engineer, so why build an application that handles billions of dollars without applying the same rules and principles?

I could not agree more. The issue is not to get it done fast or cheap. The issue is that the person designing the solution does understand what the limitations of the tools used are. Anybody that builds mission critical stuff without good engineers as designers and supervisors gets what they deserve. Same is true anywhere. Trouble with programming is that bridges collapse far more newsworthy than software.

Re:Decimal Arithmetic

[gweihir]

Is there any fundamental reason why decimal arithmetic in a computer should be more accurate than binary arithmetic in a computer?

No, no, the problem is not with the precision! The problem is that when input and output is decimal, but the calculation is binary, then you get additional errors from the conversion that badly educated programmers do not expect.

Re:Decimal Arithmetic

[Fordiman]

They kinda are...

IEEE floats are encoded as binary data, that is, as a base-2 fixed-point number. We first assume that the first bit (the only one before the decimal (binimal?) point) is 1. We can assume this because, in base 2, a properly aligned SCI number will have 1 as its first digit. As such, we don't have to store it.

The later digits represent sucessive divisions of base-2: 1/2, 1/4, 1/8, 1/16, etc. There is also stored the shift.

So, basically, they're stored as 1.BBBB x 2^N

Is this the most efficient? Well, for a computer, yes. It makes math using them a hell of a lot easier.

It's also storage efficient for the free bit we get.

Of course, this means that many decimal numbers are innaccurately stored; 0.37, for example, would need stored as:
(1.)011110101110000100100011... (x2^)-10

Is this good? bad? Well, I don't know. In Base 15, to pick a number at random, 1/3 is stored as 0.5, while in decimal it's 0.333333....

You could use fractional math, but even in higher level code it's a freaky amount of work (getting LCD and GCD for fractional reduction and such is messy in code). You could store everything as decimal, but you end up with the same inaccuaracies as with binary, just with different characteristics.

Talk to anyone who uses noninteger math on a regular basis. They'll tell you that when dealing with floats, you always expect some error; the way to handle it is to determine what your maximum percent error is, and add one significant bit past that.

Re:Decimal Arithmetic

[Anonymous Coward]

Maybe there should be an entrance exam to become a Slashdot participant. :)

Re:Decimal Arithmetic

[no-body]

The link text is a misnomer: "what goes on inside that floating point unit"

I was expecting some information about a FPU unit - parallel processing, pipelining and all that.

But it links to: "The trouble with rounding floating point numbers"

Kind of shallow...

Re:Decimal Arithmetic

[Fordiman]

No, C will automatically recast a number as needed in cases like the above.

The issue is actually a pretty commonly understood situation when going from decimal floating point numbers to binary IEEE floats (I have another comment on here describing how they're stored), and it basically comes down to this:

Floats of any sort are stored as an int with an int shift (a.aa x b^c). As such, there will be aliasing problems based on the prime components of b. A known percentage of divisors will produce repeating numbers. For example, any division of 3,5,7,11.... in base 2 will be repeating. Any division of 3,7,11,13... in base 10 will be repeating.

No, there's nothing you can do about it. Use higher precision if needed, and otherwise get over it.

Re:Decimal Arithmetic

[modeless]

Floats where [sic] good enough. [...] Had to do a bunch of

decimal.parse(value.ToString())

to get things to sum up correctly.

Oh god. Please tell us which financial institution you worked for so we can all avoid it like the plague.

Re:Decimal Arithmetic

[Nutria]

I bothered to ask the question of what to use for monitary
usage at a financial institution in my recent past.

http://en.wikipedia.org/wiki/Packed_decimal

All CISC CPUs had opcodes to do the work, but AFAICT only COBOL (being, of course, a Business Oriented Language) implemented BCD as a primary data type.

Damned shame, too, since it eliminates all the hassle of working with financial software.

Re:Decimal Arithmetic

[Fulcrum of Evil]

For example, in a lot of financial applications, float would be good enough since 2 decimal places is enough.

No, if anything has to add up, then it's BigNums only. Financial apps grow, and choosing doubles to store your money is just asking for trouble.

Re:Decimal Arithmetic

[Andrew Tanenbaum]

An IEEE-754 float (32 bits) can represent any integer value, exactly, that a short can hold.
An IEEE-754 double (64 bits) can represent any integer value, exactly, that an integer can hold.
If the programmer knows what (s)he is doing, this isn't a problem.

Re:Decimal Arithmetic

[dubbreak]

I think it was a second or third year course for me. Still pretty basic stuff. However if you don't know it and are a "programmer"...

Re:Decimal Arithmetic

[MobileTatsu-NJG]

"This is not newsworthy. This is computer science 101."

Yeah, we get it. Slashdot doesn't always post news stories. This has been going on for YEARS. Your post isn't newsworhty, either.

Re:Decimal Arithmetic

[kfg]

Who did not already understand that floats are approximations?

Read the very first sentence of the article.

Apparently that would be "we all," Whitey.

Perhaps the rest of the article got better, but I admit I didn't read it. My eyes went all blurry from the tears.

KFG

Re:Decimal Arithmetic

[gstoddart]

Since these are computers, and they deal primarily with binary internally

Last I checked, they use binary internally exclusively, not primarily. ;-)

Unless things have changed and nobody told me. :-P

Cheers

Re:Decimal Arithmetic

[innosent]

For the uneducated, the reason that this is stupid is that IEEE-754 floating point numbers cannot REPRESENT all values, they APPROXIMATE them. There is no way to properly represent the value 0.01 as a float (0.01 is best approximated by 3C23D70A, or 9.9999998e-3). So, for instance, if you were to add up 100 pennies, you would have 99.999998 cents, not 100. Repetitive additions (like credits and debits from an account) or multiplications (interest calculations, amortizations, etc.) simply make the problem worse, which is why floats should NEVER be used to track money. A fixed decimal system should always be used for financial systems.

Re:Decimal Arithmetic

[Anonymous Coward]

LCD and GCD are easily done with Euclid's algorithm. I would hardly call that a messy approach.

Re:Decimal Arithmetic

[dnoyeb]

But since we are not using infinite number of decimal places, you are basically asking for a bigger float no?

Re:Decimal Arithmetic

[KDR_11k]

Fixed point, of course. How many decimals do you need for money values? All values of existing money (account balance and such) have two decimals, exchange rates can have like 6 or so. If the maximum number of digits is known you can use fixed point and be guaranteed that you won't encounter float errors.

Re:Decimal Arithmetic

[KDR_11k]

Thanks, now I know what a nybble is...

Re:Decimal Arithmetic

[pcgabe]

But since we are not using infinite number of decimal places, you are basically asking for a bigger float no?

No.

Re:Decimal Arithmetic

[DeadChobi]

I believe that we solved that problem in my first Computer Science course by using Integers and long integers. Essentially we took the monetary value, turned it from dollars into cents for calculation, then back into dollars for output. The only error would be in our method of using division for conversion, which could have been remedied by some other methods I can think of which are probably solved by much better people than I.

Re:Decimal Arithmetic

[innosent]

no, although a double or larger increases the precision, all floating point-style numbers suffer from this problem. You might get away with it for a larger number, but you are wasting bits, and stil cannot guarantee that the number is always going to be accurate. In addition, as the number gets larger, more precision is lost. For instance, 782533.37 as a float is 493F0C55, or 782533.31, and as a rounded float is 493F0C56, or 782533.38. Neither would be acceptable, and even a double will lose precision at about 16 significant digits, which could be a problem for daily interest calculations or another high-precision calculation. What should be used is a packed decimal (BCD) or fixed decimal (int or long and an associated scale factor). The whole point is that for a financial institution, there is likely a fixed precision level that is acceptable, but floats, doubles, etc., cannot guarantee that any given precision will be maintained, as it depends upon all of the factors involved (value and size of each number in the calculation). For the same reasons, floating point numbers should never be used in program flow control, either, as doing a for(float x = 0.0; x 1.0; x = x + 0.01) will iterate 101 times, since the first time x is not less than 1.0 is when it reaches 1.00999..., and if you are looking for a specific value, it may never reach it (like for(x = 0.0; x != 1.0; x = x + 0.01)). If you instead assume that you will always deal with 2 decimal places (or 3, or whatever), you can guarantee that your addition or multiplication will be accurate, and can scale the answer later if necessary.

Re:Decimal Arithmetic

[Anonymous Coward]

Is this that new fancy AJAX thing where you can count hands-up on the web?

Re:Decimal Arithmetic

[innosent]

The RPG language also had an implementation of BCD, and probably any compiler for the IBM S/370 line would at least have a library for it, as I believe the IBM mini/mainframe architectures had implemented it in hardware.

Re:Decimal Arithmetic

[jZnat]

A nibble is half a bite (note the spellings to see the bad pun if you hadn't already).

Re:Decimal Arithmetic

[Duhavid]

I knew that. I was hoping that they would say something like
"Yeah, we use ". The blank stare was
a bit suprising.

Re:Decimal Arithmetic

[Eivind]

It's not more "accurate". It's just that the inputs and outputs are often decimal, in which case using something other than decimal can give "unexpected" results.

For example for finance, floating-point is useless, people generally do something like use a single int to store number-of-cents.

The issue ain't accuracy per se, it's accuracy with *certain* numbers (thous representable in base10).

In a financial program people expect $0.40 * 1000000000 to come out as *precisely* 400000000 and not 399999999.99

There's lots of numbers that base10 can't accurately represent, such as 1/3. The thing is, you'll never have those as inputs if the inputs are stuff like, for example, prices.

Re:Decimal Arithmetic

[Duhavid]

See, I knew that, hence the question to them.

I was suprised that they didnt.

Re:Decimal Arithmetic

[Eivind]

There's other funkyness too, besides the precision. For example, if you're adding up a lot of floating-point numbers, it makes a difference what sequence you do the additions in.

For example, if your input consist of one large number, and tons of small ones, then rounding-errors mean that starting with the large number gives a much smaller result than starting with the small ones.

If I scale it down to smaller numbers, you see why:

1.0*10^5 + 1.0*10^1 = 1.0*10^5

So, adding a "small" number to a "large" number gives you simply the large number.

If you repeat this, a million times, your result is still simply the large number.

So you could end up concluding that 1.0*10^5 + (1.0*10^1 + 1.0*10^1 ..[1000000 times]...) = 1.0*10^5

That is an order of magnitude wrong. The correct result is 1.1*10^6

Practical result ? You need to think about your input. If it *may* look like this, you need to add up by repeatedly adding the two smallest numbers. Easy to do with a priority-tree. pseudocode like this:

• Insert all numbers in priority-tree.
• Extract two smallest numbers from tree.
• Add the two numbers, producing a new number.
• Push this single new number into the tree.
• Repeat from step 2 until you're left with a single number.

MS-Excel, by the way, does *NOT* do this in it's SUM() function, if you feed it a "large" number and *many* "small" numbers, you get horrendously wrong results. Because of the relatively high precision of floats and doubles though, you need to use larger numbers than in my example here.

Re:Decimal Arithmetic

[innosent]

To avoid this problem, you evaluate the tools you have (floats, double, fixed decimal, int, long, possibly BCD, etc) and see if they match your needs. If not, go get better tools (an arbitrary-precision number library, like java.math.BigInteger or java.math.BigDecimal). Similar libraries exist for just about any language. Decimal arithmetic is inefficient on binary systems (except for hardware-implemented BCD as in IBM S/370), as well as completely unnecessary, since the binary arithmetic functions already exist in hardware, and storing individual decimal digits will always take more space than storing the whole number in binary.

Re:Decimal Arithmetic

[demeteloaf]

A known percentage of divisors will produce repeating numbers. For example, any division of 3,5,7,11.... in base 2 will be repeating. Any division of 3,7,11,13... in base 10 will be repeating.

To clarify, any rational number with a divisor that has a different prime factor than the base you're working with (i.e. any number whose prime factorization has numbers other than 2's and 5's in base 10) will be a repeating decimal.

Which is why we should move to a base 60 decimal system! Much fewer annoying repeating decimals. ;)

Now, to think of 50 more symbols we can use as digits.

Re:Decimal Arithmetic

[prockcore]

What about encoding floats as a pair of ints or longs:

That's called fixed-point. It's a hallmark of the demoscene. One, back in the 90's (the hey-day of the demoscene), floating point math was a lot slower than fixed point, and two, precision was guaranteed.

Re:Decimal Arithmetic

[theshowmecanuck]

Occasionally I see stuff like this in the real world. For example, at a bar I was in once, the debit machine which received input from the cash register had a difference of 1 cent from the bill calculated in the register. I asked them what was up with that. They said something like "yeah, that happens every once in a while". To me it seemed obvious that whoever did the coding for the interface didn't have a clue about floating point rounding errors. So I tend to agree with the grandparent post... it seems floating point rounding errors are not always obvious to some programmers. I really can't fathom how someone who is supposed to be a professional doesn't understand how their tools work... or why they don't care to.

Re:Decimal Arithmetic

[Anonymous Coward]

Show of hands: Who did not already understand that floats are approximations?

o/ !

Re:Decimal Arithmetic

[cicadia]

in a lot of financial applications, float would be good enough since 2 decimal places is enough.

Float actually gets you just slightly less than 7 digits of precision, so, while you might think that you it's good enough (you only need two digits after the decimal point,) float will only accurately store values with five or fewer digits before the decimal point. If your financial app ever has to deal with dollar amounts greater than $99,999.99, then you'd better not go with floats.

Re:Decimal Arithmetic

[Kjella]

Which is why we should move to a base 60 decimal system! Much fewer annoying repeating decimals. ;)

Now, to think of 50 more symbols we can use as digits.

If you were serious, continue from hex and make the letters case sensitive. 0-9 + a-z + A-Z = 62. Trouble is noone would be able to give you the time of day in that system, even though we already measure minutes and seconds in multiples of 60.

Re:Decimal Arithmetic

[mypalmike]

Who did not already understand that floats are approximations?

Floats are not, in general, approximations. Any float of the form a*2^(-1) + b*2^(-2) + c*2^(-3), etc. where a, b, c, etc. are 0 or 1, up to the limits of number of bits in the fraction component of the word, is an exact representation of the number. Operations on floats can yield exact results as well.

Re:Decimal Arithmetic

[oku]

For example, in a lot of financial applications, float would be good enough since 2 decimal places is enough.

Floats are good for 7 decimal places, but in total, starting with the most sinificant digit. That means that even a number like 999999.00 cannot be represented as a float precisely. (If this number can be represented, it is by pure luck and 999999.01 will fail.) Moreover, the rounding errors will be a permanent source of trouble, even for significantly smaller numbers. That said, it is common practice to use integers (of a sufficient size, with 64 bit being enough in most cases) for financial application. Of course, your basic unit is the cent.

Re:Decimal Arithmetic

[Anonymous Coward]

Why would you need floating point in a cash register?

Re:Decimal Arithmetic

[91degrees]

To represent the cents. And possibly to account for whatever sales taxes are relevent in the country. It would probably make more sense to use integer values and calculate the cents, but not everyone is sensible.

Re:Decimal Arithmetic

[Anonymous Coward]

No, if anything has to add up, then it's BigNums only. Financial apps grow, and choosing doubles to store your money is just asking for trouble.

A 64 bit integer allows quite a bit of room for growth. Though, looking at the US national debt, we might need to inflate our way out of it hard enough to push into the quadrillion dollar range. Probably best to stick with BigNums, I guess.

Re:Decimal Arithmetic

[G3ckoG33k]

Not only that, it made it to Slashdot some years ago, with many insightful comments already then! I particulary like the analysis of wave heights over deep oceans, which gives rounding errors at 32-bit precision! 64-bit are a minimum there.

Re:Decimal Arithmetic

[StressedEd]

I suspect you will end up having to avoid most of them.

Friends of mine went off to work "In The City", when I quizzed them about their use of numbers for stock prices etc they were equally dismayed that things were being passed around as doubles. Often encoded as ASCII text in data streams as well, requiring different people to write their own ASCII->DOUBLE conversion depending on the representation of the stock tick. I think this kind of madness is quite prevelant.

As someone else pointed out, if you want to do things properly you can end up needing very big integers.

Perhaps the best option is to make sure people can only by and sell equities etc in numbers that can be exactly represented as doubles on a computer. It sounds crazy, but it's not as crazy as it looks. One of the reasons stocks etc are quoted as they are is probably due to the ease of the mental arithmetic.

Kudos to the parent of your post. At least he knows what he is having to do is dodgy and cares enough to check!

Re:Decimal Arithmetic

[Nutria]

The RPG language also had an implementation of BCD,

Argh, "forgot" about RPG.

and probably any compiler for the IBM S/370 line would at least have a library for it,

Having a library isn't the issue. Early versions of TurboPascal also had BCD libraries.

That you used via function calls. Very not useful.

To be practical, a datatype needs to be usable by the 5 base arithmetic operators.

as I believe the IBM mini/mainframe architectures had implemented it in hardware.

The System 3x0 "CPU" is extremely CISC.

Re:Decimal Arithmetic

[Nutria]

To represent the cents. And possibly to account for whatever sales taxes are relevent in the country.

Stupid responses like this are caused by elistist CompSci professors thinking that it's not really important to remind language creators that accurate decimal math is important.

There is a better way, and it's been around for 45+ years: BCD.

Re:Decimal Arithmetic

[Bloke down the pub]

All values of existing money (account balance and such) have two decimals

No they don't. Some currencies have no subunit at all. The Italian lira & Greek drachma were two well known examples that are (for the moment at least) defunct due to the euro, but there are others - the Japanese yen, for example. At less than 1 US cent, it doen't really need fractions.

Re:Decimal Arithmetic

[Bloke down the pub]

For example, in a lot of financial applications, float would be good enough since 2 decimal places is enough.

Perhaps you should take some of theose classes you're advocating. Those of us who actually work in business applications never store account balances, invoice amounts and the like in floats. Ever.

Re:Decimal Arithmetic

[Anonymous Coward]

you're a fucking idiot. BCD is shit.

Re:Decimal Arithmetic

[johnw]

Friends of mine went off to work "In The City", when I quizzed them about their use of numbers for stock prices etc they were equally dismayed that things were being passed around as doubles.

I'd be not only dismayed but very surprised to find anything which interfaces to the London Stock Exchange passing stock prices around as doubles, or as any other kind of floating point number.

The LSE feeds all use 18 digits for values, with the first 10 being implicitly before the decimal point and the remaining eight being after the implicit decimal point. This is very handy because it means all the values can be manipulated using 64 bit integers. The LSE rules also state very precisely how rounding must be handled. If you try to submit a multi-million pound deal and your calculation of the consideration is out by just one penny then the deal will be rejected.

No-one with the slightest clue about how to code would use floating point maths in any kind of financial program, particularly not one where they're working with the LSE.

Re:Decimal Arithmetic

[shabble]

single-precision datatypes are only guaranteed for roughly seven decimal places

Close, but not quite - they're guaranteed to seven significant places. If you have more than one number before the decimal point, you lose precision after the decimal point. e.g. It is capable of storing 123,456.7 but would have difficulty storing 123,456.789

Re:Decimal Arithmetic

[StressedEd]

Believe me I was surprised and dismayed as well. I don't even work in banking and this is obvious to me.

The LSE feeds all use 18 digits for values, with the first 10 being implicitly before the decimal point and the remaining eight being after the implicit decimal point.

Fixed point arithmetic... fine. I'm sure the stuff that comes in the "front door" and goes out the "back door" is appropriately conforming. It has to be. What happens in between however seems to be up to the whim of the people in the bank.

No-one with the slightest clue about how to code would use floating point maths....

Perhaps you have hit the nail on the head... ;-)

Are there any people in financial institutions that can comment (anonymously) on this? My information is limited to a handful of anecdotal evidence.

Re:Decimal Arithmetic

[91degrees]

BCD is fine, but so is fixed point if implemented correctly.

Re:Decimal Arithmetic

[johnw]

Are there any people in financial institutions that can comment (anonymously) on this?

I'm happy to comment on it without being anonymous. I designed and oversaw the implementation of the LSE feeds (to and from) for the stockbroking part of a large UK high street bank which shall be NatW^H^Hmeless. If you tried to implement the internals using floating point arithmetic it would be pretty much impossible to get it to pass the LSE's conformance tests, which all assume you will use integer arithmetic and explicit rounding according to their rules.

Re:Decimal Arithmetic

[nickos]

MS-Excel, by the way, does *NOT* do this in it's SUM() function, if you feed it a "large" number and *many* "small" numbers, you get horrendously wrong results.

This caused some big problems for me in a previous job. I was using something similar to server-side javascript to generate financial reports (including summing and currency conversion) which the customer was testing by trying to get the same results in Excel. I knew there was a floating point issue in my code, but even after I fixed it it didn't match the customer's Excel spreadsheet. Imagine trying to tell a customer that the problem is with Excel! :(

Re:Decimal Arithmetic

[StressedEd]

Interesting.

Can you outline examples of these conformance tests, or even better, are they freely available? I assume these are intended to make sure things that go on the wire have a sane value, fall between certain daily trading limits etc (to prevent things like the Mizuho cock-up) [*].

I suspect that the main culprit of "dodgy doubles" is likely to be people throwing together ad hoc codes behind the scenes, not the official interface to the exchanges.. (the "front" and "back" doors I mentioned earlier).

NatW^H^Hmeless huh? That gives me some confidence. Though it still doesn't make me happy with their online banking (the numbers don't add up). I still need to find someone that can make my balance - you know - balance..... Yes, I know, "retail" banking... Yuk!

I assume you know plenty of people that work deeper in the bowls of such organisations. Would you do an unofficial survey and find out how other people implement financial numerics? I'd wager you will be shocked!

[*] Tee hee, that story did make me smile. Poor guy I bet he felt terrible....

Re:Decimal Arithmetic

[AaronLawrence]

Of course, your basic unit is the cent

Or not, if you are writing an application that has to work in other places than Europe and the US.
You can see the full range from zero decimal places to 4 decimal places for currency amounts, and sometimes prices will be of greater precision than the normal currency figures.

Microsoft made the "CURRENCY" data type which is indeed a 64 bit integer with 4 digits implicit to the right of the decimal. This is enough for most cases.

Re:Decimal Arithmetic

[k8to]

It's worse than that. In some kinds of calculations, the error can be so large that the result is entirely meaningless. That is, for example when doing a subtraction between two nearly equal floating point values, both of which were approximated, the result may have more noise than signal. This isn't the usual case, but when writing general code that cares about precise values, you can code yourself a beartrap that only springs in rare circumstances.

There is an excellent article about all of this detail, linked from TFA at sun: http://docs.sun.com/source/806-3568/ncg_goldberg.h tml

Granted, I have never written any code where this matters, but I had never realized really just how bad some of the implications are in some cases.

Re:Decimal Arithmetic

[Anonymous Coward]

It is a little newsworthy.

No it's not for fuck's sake, Goldberg's What Every Computer Scientist Should Know About Floating-Point Arithmetic was published more than 15 years ago, anyone who's in charge of coding anything and hasn't read it by now should be shot on the spot, nailed to a wall and shot again before having his corpse desecrated by rabid bears.

Even though it's stuff that matters this is definitely not "news for nerds", because there's no way to call youself a nerd or an IT geek if you don't know that.

Re:Decimal Arithmetic

[Anonymous Coward]

Floating point arithmetic is defined by relevant IEEE and ANSI standards.

This whole debate that's sprung up in various places, over the last few days, about whether or not we can trust the output of floating point units is illustrating very clearly, that there are more and more people emerging from computer science degrees or working as software "professionals" with no real - let alone correct - understanding of how computers actually work.

This is really, really, really simple basic stuff.

Re:Decimal Arithmetic

[xdxfp]

You can increase the number of bits, but again it's only going to put off the problem. This is the kind of stuff that video card designers deal with all the time. A .0000001 difference early in the calculations can cause a 30% shift later on. For most of us though, who cares if my income taxes are two pennies over?

Re:Decimal Arithmetic

[petermgreen]

But since we are not using infinite number of decimal places, you are basically asking for a bigger float no?
NO

what matters in money is predictable behaviour according to specified rules, those rules are decimal based so the system needs to operate with a (generally fixed) decimal exponent.

bigger binary exponent floats will give a better approximation of 0.01 but the error is still there and will still add up over time.

Re:Decimal Arithmetic

[Anonymous Coward]

The only error would be in our method of using division for conversion

Of course, the simple thing to do would be to always use cents, and just remember to print a . in the right place. "Fixed point" math has been around for a long time, and was really popular in games before we had stuff like 3d accelerators and the like ;)

Doesn't help with dealing with stuff like interest though. What's 1.27% of 24592 cents?

Re:Decimal Arithmetic

[Fordiman]

Easily is a relative term. Euclid's algorithm is usually implemented recursively, and I think its Big O is something like N*log(N) at minimum.

Perhaps you don't consider that messy. It's not something anyone wants done before/after each operation.

Re:Decimal Arithmetic

[Anonymous Coward]

The problem is that all the arbitrary values are chosen by people who tend to use base 10. 0.1 in decimal is accurate to whatever precision level you choose in decimal, but if it's converted to binary, it's a recurring number and gets truncated at some point.

Re:Decimal Arithmetic

[Eivind]

Excel is mindbogglingly dumb from a CompSci or mathemathical POV. It's incomprehensible to make a spreadsheet and then fail to understand even the basics of floating-point arithmethic.

Demonstrating it to the customer shouldn't be a problem. Make a *trivial* Excel-spreadsheet that gives an obviously wrong result, you need nothing more than a table of numbers and a single call to SUM() for this.

Used to work correctly in 123 for DOS 6.22 by the way, (and works correctly in OpenOffice Calc) so it's not as if this is something new....

Re:Decimal Arithmetic

[hughk]

No-one with the slightest clue about how to code would use floating point maths in any kind of financial program.

Not quite correct. You calculate real money using big integers as you suggest. Some systems use variably scaled integers to get over the problem of representing different currencies.

On the other hand, when you start working on derived data such as pricing models or risk then you end up using floats.

Re:Decimal Arithmetic

[Nutria]

BCD is fine, but so is fixed point if implemented correctly.

Fixed Point has typically been implemented using 32-bit integers with a scale of 2.

BCD is much more flexible.

Re:Decimal Arithmetic

[grimarr]

all floating point-style numbers suffer from this problem.

Not exactly. The real problem is that people use decimal numbers, and computers use binary numbers. Each numbering system has some numbers that the other one cannot represent exactly. If computers used floating-point DECIMAL calculations, this would be avoided. I've never seen that done, but I have seen fixed-point decimal, and it usually solves this problem nicely. But modern computers don't do decimal arithmetic as fast as they do binary arithmetic, so it's not used as often as it should be.

Re:Decimal Arithmetic

[Anonymous Coward]

I worked for a year at a major financial services company. They were using floating point math when figuring out how to split your money between accounts/funds/companies. The developers on my team had no idea that floating point math and money don't mix.

Re:Decimal Arithmetic

[EatHam]

The most often used way to do this in finance is to make your price an int, and multiply it by whatever factor of 10 you need for your application. Just FYI.

Re:Decimal Arithmetic

[StrongAxe]

which is why floats should NEVER be used to track money. A fixed decimal system should always be used for financial systems.

If you store you values in cents, and use double-precision floating point, you get 53 bits (around 16 digits) of accuracy, which can exactly express any value up to 8 trillion dollars. OK, so if you're computing the GNP of the United States, you might be off by half a penny. Is anyone really going to sweat that? Then again, you could just use extended-precision (long doubles), which give you 64 bits of precision - this would let you calculate the GNP to within 1/2000th part of a cent. Is that accurate enough for you?

Similar arguments are raised against using digital sampling for audio - if your quantization error is more than one place smaller than anything discernable by the best human ear, who really cares? Things that cannot be distinguished may be treated as if they are the same.

Re:Decimal Arithmetic

[Citizen of Earth]

To produce decimal output from a 'double' value, I have written a function that printf()s it to 16 significant digits and if it has a decimal and the last two digits are "01" or "99", I reprint it with 15 digits and use that string. This gives strings that are ususally 16 digits in precision to avoid unnecessary truncation when converting the numbers back into doubles, and also avoids ugly eye sores when printing out common short decimal numbers.

Re:Decimal Arithmetic

[Duhavid]

Thanks.

I had expected them to have a library of such things,
since that was their business.

Re:Decimal Arithmetic

[91degrees]

Why is BCD more flexible? It only seems to be able to represent base 10, and if stored with the same precision, will have a smaller limit.

Re:Decimal Arithmetic

[sjames]

Who did not already understand that floats are approximations?

I don't know about the /. readers, but I have seen way too many examples in the industry where someone who needed to understand this obviously didn't.

By far the most common case of floating point problems is FORTRAN programs written by physicists and chemists. Sometimes they are somewhat aware of the problem and ovcer the years add little hacks here and there to make it produce what they presume to be correct values (when many million iterated calculations are involved, it can be hard to be sure). Then, someone compiles it with a newer and "better" compiler. The program's performance doubles and everyone rejoices until 6 months later when they discover that -O6 may do unsafe things with floats (and has produced 6 months worth of worthless results).

It's a bit unintuitive to be sure. For everything but floating point, correctness is nearly 100% solved for commercial compilers and most free ones as well. No integer operation will ever have 2*2 come out as 5 or 3. An if never screws up and reverses the logic, there is one right thing to do and it does it every time.

Underlying hardware makes a big difference as well. Some old dinosaur machines used BCD for all numbers, and the FORTRAN compilers on those glossed over it to handle floating point (often with scaled BCD). On those machines, 0.37 would always be 0.37. The only thing to watch for would be over/underflows (which produced an execution error) or not having enough significant digits (unlikely).

IEEE floats are fast on modern hardware, but can go wrong in many subtle ways. Imagine a program that ran correctly for years on one of those old dinosaurs recompiled for use on a modern PC! Good luck with that.

I'll bet there are plenty of people who would be REALLY happy if CPUs added hardware support for fast and accurate floating point.

Second best would be compilers that emulated accurate floating point at reasonable speeds.

Re:Decimal Arithmetic

[saider]

This is where the dilution of the word "engineer" rears its ugly head. It has been so overused that most people (especially human resources folks that do the hiring) do not understand the difference between a software engineer and a programmer.

Software Engineers design the system.
Programmers write the code.

Designing the system is an engineering role and you should have someone trained in engineering concepts performing this task. Implementing the design can be done by anyone trained in the use of the tools and a good set of dcoumentation produced by the previous step. Engineers can implement the code, but generally not the other way around.

Re:Decimal Arithmetic

[zippthorne]

Your bank does. Sure it's not important if the multiplication operation is two pennies over, in fact, it's guaranteed that you're going to have to round your taxes somewhere unless your income is an exact multiple of the tax rate (which you could probably arrange with the proper amount of charatable giving). But the calculation that matters is the transfer of funds from the bank to the government. (or your matress to the government I suppose...) That calculation has to be exact to the penny. (or at least, there can be gaps, but no overlaps.)

That said, this whole discussion is rather meaningless. For applications where floating point numbers are sufficient (i.e. low numbers of additive operations, which will be between like-sized numbers only) It doesn't matter whether you use binary or binary coded decimal. It simply doesn't matter that you cannot properly represent .1 in base 2 numbers of finite length because .09998 +/- (floating point precision) gets the point across. In fact, if you're dealing with real physical phenomena, all that matters is that you choose a representation under which the ambiguity of the storage format is smaller than the ambiguity of the measurement itself. It could be exactly the same if your measuring devices are base-2 to begin with, which realistically is pretty much all the time. (ok, I could give a whole speech about accuracy and precision here, but we're really only talking about precision, so that can be tabled for a later date.)

It makes sense to use binary coding for anything involving floating point numbers because of the bit efficiency alone. There is no collection of bits with which to represent a floating point number which couldn't be done with less ambiguity than simply using those same bits as a binary floating point number.

For all other applications, there're integers. Which also doesn't matter whether they're BCD or not (unless you're really really short on the processing power to display the nubmers, but if you're that short on processing power you should probably be asking whether you need to display the nubmers at all!

If we really want to be able to exactly specify the maximum number of fractional numbers, we should specify a base that has an extensive factorization. You can't properly represent one-third in decimal you know. Our ancestors used base-12 for instance.

Re:Decimal Arithmetic

[bwcook0]

You wouldn't build a bridge without an engineer, so why build an application that handles billions of dollars without applying the same rules and principles?

I am sure people WOULD build bridges without an engineer if it weren't against the law. Maybe it is time for computer/software engineers to join the rest of the engineering world and have licensure tests, and then require the senior engineer on a project to stamp the code.

Re:Decimal Arithmetic

[DudeTheMath]

No-one with the slightest clue about how to code would use floating point maths in any kind of financial program, particularly not one where they're working with the LSE.

Not true. It depends what, exactly, the goal of the financial software is. Yes, if you're *adding* lots of numbers, or adding a small number to a large one, floats (or doubles) are a poor choice. But when *multiplying* numbers, especially ones of different scales, doubles can be just what the doctor ordered.

The important things are to be aware of the limitations (know *when* to used integer arithmetic with fixed-point), know what the customer's tolerance is (and in my particular niche, there is always a tolerance), and apply sanity checks. Simply relegating any financial programmer who uses floating point to the rank of idiot shows a good deal of ignorance of the range of work that comes under "financial."

Re:Decimal Arithmetic

[Anonymous Coward]

For example, in a lot of financial applications, float would be good enough since 2 decimal places is enough.
No! This is completely and utterly missing the point of why floats must not be used in financial calculations.

There are no "decimal places" in floats. As soon as you put something like 0.01f into a variable or a database field, you are f*cked.
Time for you to revisit your comp.sci lessions.

Re:Decimal Arithmetic

[poot_rootbeer]

using double, of course, only defers the problem.

Which may be good enough for most uses. If the floating-point representation of a monetary value is within 1/32768th of a dollar of its true value, then errors in rounding that value to the nearest cent are going to happen with much less frequency than when it may be as much as 1/128th of a dollar away from true (almost a cent in of itself).

Of course, there are still often better ways to handle such values. Such as fixed-precision decimal values.

Re:Decimal Arithmetic

[WuphonsReach]

We also studied Numerical Analysis. Except it was only a required course for the Engineering majors (EE, ME, CE). It was a 3-week course taught in a mini January term using Fortran77.

Kind of odd that it wasn't taught to the CS folks.

Re:Decimal Arithmetic

[TheLink]

The problem is when you keep doing the sums, the errors can accumulate to a significant degree.

To reuse your analogy: when you process audio and you are interested in fidelity you try to process it the minimum number of times in order to achieve the effect you want.

If you keep playing around with the amplitudes without going back to the original sample you risk losing fidelity.

Re:Decimal Arithmetic

[rk]

Base 30 is as good as 60, since 30 = 2 * 3 * 5 and 60 only gives another factor of 2. 62 is = 2 * 31 which is actually worse, with only two prime factors.

A floating point system for a base can only precisely represent fractional values where the denominator's prime factorization contains only prime factors that the base has. This is why things like 1/3, 1/7, etc. can't be exactly represented in decimal, either.

A base 210 system would be kind of handy, having the prime factorization of the first 4 primes, which would give us a lot of exact decimals for many fractions.

Re:Decimal Arithmetic

[Anonymous Coward]

"You see, when the subroutine compounds the interest, it uses all these extra decimal places that just get rounded off. Well, we just take those extra decimal places, and put them into an account we opened."

"So, you're stealing?"

"No, it's very complicated. We're talking about fractions of a penny here."

"How is this not stealing?"

"You know the tray of pennies at store?"

"For the crippled children?"

"No, the give a penny, take a penny tray. Well, what we're doing is just like that. Except we do it from a much bigger tray, and we do it a couple million times."

Re:Decimal Arithmetic

[mrchaotica]

Weird... I'm a CS/C[ivil]E double major, and I haven't had anything like numerical analysis in my CS or engineering classes. And unless it's part of [CS] Theory 1, I don't think I ever will (or, at least, not as a required thing).

Re:Decimal Arithmetic

[tomjennings]

Absodiddlyutely. Floating point isn't arithmetic, it's a *simulation of* arithmetic. Alan Turing [and probably others] pointed this out before 1950! It trades precision for convenience and dynamic range. RTFM!

Re:Decimal Arithmetic

[mrchaotica]

To be practical, a datatype needs to be usable by the 5 base arithmetic operators.

And so the problem with just using C++ and overloading some operators is...?

Re:Decimal Arithmetic

[Anonymous Coward]

I had a big argument at my last job (rewriting the unemployment insurance system for one of the flatter states), trying to convince the other developers there (from a large "offshore" consulting company) to use Java's BigDecimal class for financial arithmetic. I eventually convinced the project architect, who informed the development lead, who sent out a memo to the development staff...which was completely ignored. ("Our development standard says to always use Float for currency amounts!") I'm glad I got out of there before it went live -- there's going to be hell to pay at the end of the first quarter when they try to reconcile their accounts...

Re:Decimal Arithmetic

[Fulcrum of Evil]

True, but Bignums are portable and easy to work with. It'll be a while before we have 64 bit everywhere.

Re:Decimal Arithmetic

[jonored]

As a contrived example, take the sum of 1000 values of .2 in two digit scientific notation - you sum the first 50 or so with no problem, getting the correct answer of 1.0*10^1, and then you add the next .2, and the answer is 10.2, which is represented as... 1.0*10^1. Then you add the next, and... again, the value doesn't change. Now, if you are doing this in binary, .2 isn't even precisely representable with a finite-length string of bits - so you are _always_ getting this problem. The example above comes out off by a factor of 20! and the problem does appear in less extreme forms in non-contrived examples - with differences in how a number gets rounded, etc. because of the sequence of values being added and other such things that should not be affecting the result.

Re:Decimal Arithmetic

[Anonymous Coward]

- You should be using something like Java's BigDecimal library.
If your language doesn't have that then you should be calling a Java module to do the work.

Re:Decimal Arithmetic

[Mr Z]

Maybe in your limited experience. Fixed point only means that the "binary point" (or in the case of BCD, the "decimal point") doesn't move relative to the accumulator. Fixed point vs. floating point is orthogonal to binary vs. BCD representations. You can have fixed-point BCD as well.

Floating point is more flexible, but comes with dynamic quantization issues when you add and subtract values that are wildly different in magnitude. Fixed point is more numerically predictable because you have static quantization: At any given step you decide how many fractional digits you wish to keep and how many you wish to discard. You need to make an a priori tradeoff between dynamic range and precision. If you're building, say, a controller circuit, you might prefer a fixed point implementation since its easier to predict the error terms, as it's not dependent on system inputs.

Separately, BCD vs. binary depends on the use. For fiduciary calculations, since finances were historically been computed by hand in decimal, adding machines, and later computers, are expected to perform rounding by the same methods as people computing by hand. The most efficient way to do this seems to be with BCD or some other decimal-derived representation. (The old TI Home Computer used a Radix-10000 representation, IIRC.) Binary representations make the most use of a given number of bits, and thus are the most generally useful outside the world of finance. That is, they offer the greatest amount of precision for a given number of mantissa bits. However, human-friendly decimal numbers seem to round "oddly." However, that's just an artifact of the fact we learn arithmetic in base 10, not base 2 or base 16.

--Joe

Re:Decimal Arithmetic

[TioBorracho]

I have to agree with this. Every serious programming course should have a subject on numeric methods and every programmer should know what a floating point number is. No news at all.

Re:Decimal Arithmetic

[Bloke down the pub]

SAP uses them too. ABAP, the language it's written in, is sort of a pascalish c0807 with objects nailed on the side. Early versions of SAP ran on IBM mainframes.

Re:Decimal Arithmetic

[Bender0x7D1]

I agree. However, if you are working with a retail website for music, books, etc. it is extremely unlikely you will see that amount. While BigNum would be safer, if you have a popular site, with an overworked server, performance would be better with float.

I think an important thing to remember is that if you design an app for a retail bookstore, you shouldn't expect that same app to work for wholesale heavy machinery. You don't expect a bridge on a county road to handle thousands of trucks a day, but a bridge on a busy interstate should.

Again, BigNum is safer, but has an overhead associated with it.

Re:Decimal Arithmetic

[gweihir]

It's worse than that. In some kinds of calculations, the error can be so large that the result is entirely meaningless.

True, but that does happen with decimaly coded floats as well. You just need to know some numerics when using floats. If you approach the precision boundaries, use, e.g., interval artithmetric. All solved problems.

Re:Decimal Arithmetic

[k8to]

Sorry, I didn't read the full context. Yes of course my comments apply to any kind of floating point number.

Re:Decimal Arithmetic

[WuphonsReach]

The college that I went to had a 2 semester system with a short 3-week semester wedged into January. The 3-week J-term was typically dedicated to a single 3-credit class or a pair of 1-credit classes. So we had to learn Fortran77 and Numerical Analysis within 3 weeks. Fortunately, Fortran77 is a pretty simple language for this purpose or things would've been a bit rough.

It was actually one of my favorite classes in college as it appealed to the geek within (learning about floating point representations) as well as being practical (estimating and bounding error values). Our textbook was called "Elementary Numerical Analysis" and had a bright green cover.

I might be off-base remembering it as being required. Half the engineering majors may have taken another course during that J-term. Other schools might lump it in with Physics 101 (along with significant digits) or one of the math classes (Calculus? Linear Algebra?).

Re:Decimal Arithmetic

[mrchaotica]

At my school, all I learned in my introductory classes was the basics of how floating point numbers worked (e.g. base and mantissa), and how to convert from binary to decimal and back. Stuff like bounding error was not covered at all.

There is one class that appears to cover it (unsurprisingly, it's called "Numerical Analysis"), but it's a full-semester 4000-level math course -- I doubt many non-math majors take it.

Re:Decimal Arithmetic

[Nutria]

SAP uses them too. ABAP, the language it's written in, is sort of a pascalish c0807 with objects nailed on the side.

Good to hear.

Unfortunately, ABAP is a pretty specialized language.

Re:Decimal Arithmetic

[Nutria]

To be practical, a datatype needs to be usable by the 5 base arithmetic operators.

And so the problem with just using C++ and overloading some operators is...?

Nothing. Have you seen it done, though?

A reference to a Java implementaion would also be tres' useful.

Re:Decimal Arithmetic

[mrchaotica]

A reference to a Java implementaion would also be tres' useful.

Unless I'm extremely out of it, Java doesn't have operator overloading. C# does though, if you want a Java-like language.

Re:Decimal Arithmetic

[jafac]

A few years back, stocks went from being represented as strictly fractional values (1/2, 1/4, sometimes down to 1/100) - and there was some kind of mandate, (I think in 1998?-ish) that dictated they go to a decimal system.

The conspiracy theorists at the time were saying that it was a scam to rip people off on all the rounding errors.

Re:Decimal Arithmetic

[Lijemo]

I am Pentium of Borg. Division is futile. You will be approximated.

Re:Decimal Arithmetic

[Lijemo]

less faciciously:

Once you get on the right side of the decimal point, things get REALL fuzzy in binary. Floats are represented in binary in terms of x(1/2) + y(1/4) + z(1/8), etc, etc, etc. Any number that isn't a fraction of a power of two (1/2, 1/4, 1/8, etc) needs a LOT of decimal places to be represented with any degree of accuracy-- and even then it's an approximation.

A fixed decimal system, on the other hand, is exact to a certain (known) number of decimal spaces. It's still a limited precision: but the limit can be to a very small fraction of a penny, and is known and predictable-- thus much more reliable for finantial transactions (since the known, limited, precision can be to a very, very small fraction of a penny).

Re:Decimal Arithmetic

[Bush Pig]

We didn't do a significant amount of numerical analysis until 2nd year at university (although the 1st year course touched on it), but it was one of my favourite subjects. The bloke who taught us (Silvan Elhay) found an error in the FP hardware on the VAX, apparently. He's pretty smart, and also a good sax player.

Also, how is this relevant to financial transactions? I thought they were all done with either BCD, or large integers scaled at the end of the calculation.

Re:Decimal Arithmetic

[DamnStupidElf]

This is not newsworthy. This is computer science 101.

This is slashdot, not CS101. There are plenty of people who haven't touched CS courses writing software that may use floating point numbers. I'd rather they knew about the potential pitfalls of floating point numbers, since I'll probably end up using their software sometime. Consider it in your best interest to educate non-CS coders.

Re:Decimal Arithmetic

[Krakhan]

Huh? The wikipedia page here gives an example implementation in C/Java (an iterative solution no less) that involves nothing less than 9 lines of code.

With a bit of elementary number theory to back up the correctness as to why it works, I would still hardly call this a difficult algorithm. If you think this is a hard algorithm, you should attempt to try to implement a linear-time planarity test for an arbitrary graph.

Re:Decimal Arithmetic

[ScrewMaster]

Trouble with programming is that bridges collapse far more newsworthy than software.

That's not really true, certainly not with embedded control systems. There's one hell of a lot of mission-critical firmware out there that, if it were to fail catastrophically, would produce far more newsworthy results than any bridge falling down. Which is, of course ... all the more reason to apply sound engineering principles, so I'm hardly disagreeing with you.

Part of the problem, really, is that applied computer science is not (in spite of some people's claims to the contrary) as mature a discipline as mechanical and structural engineering. The human race has been building bridges for thousands of years, and computers for only half a century or so. Worse yet, software engineering changes constantly as new techniques and methodologies are discovered. Still, if you're coding an application that is potentially dangerous it is best to be conservative: one of the best examples of that is the Space Shuttle's software engineering group. What they do isn't remotely sexy, but damn if it isn't reliable..

Re:Decimal Arithmetic

[Anonymous Coward]

So floats are approximately approximations.

Re:Decimal Arithmetic

[Anonymous Coward]

This is not newsworthy. This is computer science 101.

And not everyone that is interested in computers has a compsci degree jackass...

Re:Decimal Arithmetic

[aybiss]

Here here. Thanks so much for making sure this was right near the top of the comments. There was a time where the only response to this on slashdot would be 'ROFL', however it seems standards have slipped a long long way.

Re:Decimal Arithmetic

[aybiss]

Well technically, using BCD is just another approximation, again limited by bits. Its just that most humans are familiar with decimal rounding, not binary rounding. The only real way to ensure that numbers are stored exactly is not to limit the number of bits used in the first place.

Re:Decimal Arithmetic

[Schraegstrichpunkt]

If your language doesn't have that then you should be calling a Java module to do the work.

Call a Java module? You mean, like, another language? That's dirty and evil. We write all our code in rock-solid PHP 4.

-- The Management

Re:Decimal Arithmetic

[StrongAxe]

The problem is when you keep doing the sums, the errors can accumulate to a significant degree.

You missed my point: For values less than the GNP of the United States, double-precision reals can exactly represent the values with zero error. So even if you add a million such quantities, the total error will always be zero.

If you do deal with quantities as large as the GNP, the value may only be accuracy to within one cent, so if you compute the GNP of the entire planet (say) by summing up the GNP of every country in the world, your result may only be accurate to within a dollar. This is probably acceptable for any practical financial application. (If this is still not enough, extended precision reals can give you three more decimal digits of accuracy).

And as far as my audio analogy goes: if each processing step (say) can lose you up to one bit of accuracy, if your data samples contain 16 bits of accuracy more than you need, then even 16 processing steps will not compromise your data at all.

Re:Decimal Arithmetic

[Bush Pig]

You've been short-changed. Through no fault of your own, you're profoundly ignorant of something very important, to both computer scientists _and_ civil engineers.

The introductory course I did in Numerical Analysis in 2nd year uni was a semester unit, as was the slightly more advanced unit I did in 3rd year. In each case, the lecture was one of the highlights of my week.

The bloke who taught it was really cool. He's the only person I've ever seen manage to shut up the two back rows full of engineering students - just by glaring at them.

Re:Decimal Arithmetic

[billcopc]

Floats are never good enough. In fact floats are the very seeds of evil. They are inaccurate even with what should be benign numbers like 0.0001. To you and me, 0.0001 is simple. To a float, 0.0001 is something like 99999e-7 or whatever.. I suck at this type of math but just as an example, let's say you store 0.0001 in a float, it might actually end up being 0.00010132 or something. Do a bunch of additions, mults divs whatever and you end up with wacky errors. You might tell it to do 0.0001 times a million, to you and me that equals 100. The computer might say 100.7 and you wonder where the hell that .7 came from.

The way my non-math-genius mind has been doing it all these years, is with strings. If I need true arbitrary-precision math, I do it the way humans do it: visually. Take the last digit, add, carry, repeat. There are a few optimizations the careful coder can implement, like working on several digits though the added complexity can bite you in the ass. That's pretty much the only way to ensure error-free decimals. It is slow as hell which is fine for business applications since they spend most of their time waiting for stupid users, but for scientific apps you have to find a tradeoff between precision and speed.

Re:Decimal Arithmetic

[Bush Pig]

You're absolutely correct. We don't want a bigger float. Floating point numbers are just about (ah ... no ... absolutely) _the_ _most_ _innapropriate_ thing to use for financial calculations. These things can be managed much better (binary coded decimal, very long ints scaled, other stuff I can't be fucked thinking about). Maple is pretty good for HUGE numbers.

You didn't do a lot of maths at university, did you. You're probably an economist or an accountant or something. You certainly aren't a computer scientist. Or a mathematician.

Re:Decimal Arithmetic

[Bush Pig]

I think you're wasting your time. You can't educate these people.

Re:Decimal Arithmetic

[Bush Pig]

I'm sure you're wrong (but I'm too drunk to explain why). You should never ever ever ever use floats of whatever arbritary precision is available to deal wtih money. Sixteen digits of precision just doesn't cut it (considering how much information you lose adding a really big number to a really small number). If you don't get my drift you need to go back to school.

Re:Decimal Arithmetic

[Duhavid]

I knew that. I was suprised that they didnt.

FYI, you reimplemented BCD, basically, with your
string solution. There are packages to do that,
I saw a couple listed in other posts. Here is
one.

http://www2.hursley.ibm.com/decimal/decnumber.html

Re:Decimal Arithmetic

[StrongAxe]

Sixteen digits of precision just doesn't cut it (considering how much information you lose adding a really big number to a really small number).

While this maxim is often quoted, it is just a rule of thumb - you can't apply this generalization to any specific application without actually looking at the ranges of values you are going to be using and quantifying just what the error will be. If you use double-precision floats, these can totally accurately represent any integers up to 53 bits with no error. You can take quantities in the trillions of dollars (expressed in pennies) and subtract them, and get results that are exactly accurate to the penny with zero rounding error. Extended-precision floats can similarly accurately represent all 64 bit integers, and many other larger values as well.

The problems happen when you use real numbers to represent inaccurate quantities (for example, a trillion dollars plus-or-minus a penny, a trillion and one dollars plus-or-minus a penny, etc.) and then subtract them. While these two numbers express an error of one part in a hundred trillion (14 digits of accuracy), the difference (one dollar plus-or-minus two cents) represents less than two digits of accuracy - a catastrophic cancellation error.

However, if you write your application so that floating point numbers are used ONLY to represent integer values (a double-precision float is certainly better than a 32-bit integer, and an extended-precision float is just as good as a 64-bit integer, if not better, especially on systems that support extended-precision floats but not 64-bit integers), than there will never be any rounding errors, and the hardware support and language support make their use more efficient and convenient than using bignum packages.

The only pitfall happens if the programmer gets careless and thinks of the quantities as reals rather than large integers, but even worse problems happen when you ACTUALLY use integers. While extended-precision ($1trillion) / 3) will produce a result which is inaccurate after several around 6 decimal places, int64 ($1trillion) / 3 will produce a result which is inaccurate after ZERO decimal places.

Re:Decimal Arithmetic

[statusbar]

The problem is deeper than just accuracy of money, people have died because of floating point rounding errors. See Roundoff Error and the Patriot Missile. In this case the rounding error did not really cause the problem, it was that the assumptions that the programmers had made caused a delta between the calculated clock and the actual clock.

People in general have no clue about the math behind floating point.

In my opinion, it should be an error to compare two floats values for equality or inequality.

--jeffk++

Re:Decimal Arithmetic

[StrongAxe]

In this case the rounding error did not really cause the problem, it was that the assumptions that the programmers had made caused a delta between the calculated clock and the actual clock.

This is exactly right. It is not the model being used (in this case, floating point) that is at fault, it is that the programers misunderstand the model and its implications (basically, they think they are using one model, but in fact are using a similar but slightly different one).

People in general have no clue about the math behind floating point.

Sadly, this is the case.

In my opinion, it should be an error to compare two floats values for equality or inequality

While this may be true in most cases, it is not always true. In particular, where one is using floating point to represent exact values (rather than approximate ones), equality comparisons will be exactly correct, just as they are for integers.

Re:Decimal Arithmetic

[gweihir]

Part of the problem, really, is that applied computer science is not (in spite of some people's claims to the contrary) as mature a discipline as mechanical and structural engineering.

I completely agree to that. Even worse is that many people do not realise this. I would say it is another 20-50 years until important software is routinely being built with the same level of reliability as bridges. A main issue IMO is liability. Currently software makes can rid them selves of any and all liability. Bridge makers cannot. For software we need at least liability in commercial products that can only be avoided if you can demonstrate that only qualified personell was used and enough time was spent on development and Q&A. The next step then is less limited liability, but the possibility to insure your work against claims.

Don't know where free software will go, though. Maybe independent quality grading?

Re:Decimal Arithmetic

[ScrewMaster]

Even worse is that many people do not realise this.

Yes ... this is a case where ignorance is anything but bliss.

I would say it is another 20-50 years until important software is routinely being built with the same level of reliability as bridges.

Software is already routinely built to high standards, but those standards are expensive, consequently most vendors don't live up to them. Most of the problem is that the complexity of a modern operating system or major application affords so many possible failure modes that it really isn't possible to test for all of them. That puts the onus back on solid design and implementation and even then you're still taking a shot in the dark when you release your code.

Don't know where free software will go, though.

Well, free software (at least, the open source variety) could, reasonably, be expected to have less liability because you can actually see what you're getting and if your application requires more reliability have it evaluated from that perspective. When you buy a closed source product, it's caveat emptor, baby.

Re:Decimal Arithmetic

[Bush Pig]

As an aside, I'm sure you will have noticed that the value of $A is measured against other currencies to 1/100 of a cent at the end of the ABC news, and petrol prices are always given to 1/10 of a cent. (Why, I don't know, since the smallect currency in circulation is 5c ... ) As even more of an aside to the aside, my son recently spotted a petrol price of 133.7 per litre, which as you can imagine was the cause of much hilarity.

Of course, when I grew up, we had to calculate money in 3 number systems (20 shillings to the pound, 12 pence to the shilling, and you're doing it all in base 10 numbers). Decimal points in money is for poofters.

Re:Decimal Arithmetic

[Bloke down the pub]

And that thing beginning with a C (whose name I will not utter here) isn't? RPG and dialects aren't?

Re:Decimal Arithmetic

[JNighthawk]

I know. It was a joke.

Re:Decimal Arithmetic

[PaulBu]

Maple is pretty good for HUGE numbers.

Maple is good, Mathematica is good, what the heck, good old Common LISP is good (and knows about ratios) -- and Forth did not even have floating point numbers, proclaiming in its main defining book something along the lines of "real men do not use floating point" -- it was before political correctness times, when Forth was actually used to control robotics/avionics, including some Space Shuttle programs (see http://forth.gsfc.nasa.gov/ for mission list), and, of course, before it became PostScript! :-)

Paul B.

Re:Decimal Arithmetic

[Bush Pig]

Intergraph pulled the same trick with coordinates (large scaled integers) in their CAD software.

Obligatory

[karvind]

Office Space

Re:Obligatory

[TheShadowzero]

I believe you have my stapler?

Re:Obligatory

[andrewman327]

You beat me to it. I was just thinking about how much better TFA would be if they explained the specifics of how the Office Space team ripped off the banking system.

Re:Obligatory

[SinGunner]

suggesting that someone do that constitutes a terrorist act.

terrorist.

Re:Obligatory

[andrewman327]

Only it is a fictional movie, thus there is no crime. Ocean's 11 and Ocean's 12 go into detail about how they steal money from various people, but that is not considered criminal in real life.

Honestly, how many people are in a position to commit such a hack? Everyone who could do it knows exactly how to do it already. It is only through programmer honesty and code review that it does not happen.

Re:Obligatory

[SinGunner]

is your world where everyone is honest and knows everything related to their position taking applications?

Honestly

[TheShadowzero]

I can't tell if that was /.ed already or not, but all I see is:

#MenuCode a,

hmm...

Re:Honestly

[Anonymous Coward]

Their use of a floating point number backfired on them.

decNumber libary from IBM

[Not The Real Me]

This is why I use the decNumber library from IBM.

http://www2.hursley.ibm.com/decimal/decnumber.html The decNumber library implements the General Decimal Arithmetic Specification[1] in ANSI C. This specification defines a decimal arithmetic which meets the requirements of commercial, financial, and human-oriented applications.

The library fully implements the specification, and hence supports integer, fixed-point, and floating-point decimal numbers directly, including infinite, NaN (Not a Number), and subnormal values.

The code is optimized and tunable for common values (tens of digits) but can be used without alteration for up to a billion digits of precision and 9-digit exponents. It also provides functions for conversions between concrete representations of decimal numbers, including Packed Decimal (4-bit Binary Coded Decimal) and three compressed formats of decimal floating-point (4-, 8-, and 16-byte).

Re:decNumber libary from IBM

[Anonymous Coward]

and if that doesn't count as "news for nerds" I'm turning in my slide rule!

Re:decNumber libary from IBM

[piranha(jpl)]

Rational number arithmetic is a more general solution. Any number that can be expressed in decimal or floating-point notation is rational; any rational number can be expressed as (n/d), where n and d are integers. We have "bigints;" unbounded-magnitude integers constrained only by the memory of the computer they are stored on. Rational numeric data types pair two bigints together to give you unbounded magnitude and precision, and have been implemented for decades.

They probably aren't directly supported in your favorite programming language because they are slow to work with when you need very high precision; after each calculation, the rational number needs to be reduced to its lowest terms. This involves factoring, which takes time proportional to the the terms themselves.

Consider the use of integers, floats, or decimals only as an optimization when it has been shown that an application is suffering a serious performance hit because of rational arithmetic, and when you can use a faster data type knowing that your program will perform within accuracy goals.

For 90% of computing problems, monetary calculations included, you shouldn't even have to worry about what numeric type you're using. Your language should assume rationals unless told otherwise. Common Lisp, Scheme, and Nickle do exactly that.

C developers can use GMP. Other developers can use one of many bindings to GMP.

Re:decNumber libary from IBM

[Krakhan]

They probably aren't directly supported in your favorite programming language because they are slow to work with when you need very high precision; after each calculation, the rational number needs to be reduced to its lowest terms. This involves factoring, which takes time proportional to the the terms themselves.

Why would you use a factoring algorithm when you could just use the Euclidean algorithm to find the GCD of (n/d), and then divide the numerator and denominator by them? That would be far faster than factoring both the numerator and denominator and cancelling common terms in the prime factorizations.

Otherwise, I agree with everything else in your post.

Re:decNumber libary from IBM

[darenw]

after each calculation, the rational number needs to be reduced to its lowest terms. This involves factoring, which takes time proportional to the the terms themselves.

I am not so sure about that. It may be better, in some cases, to be lazy about reducing. For a simple example suppose we want to compute A+B where A and B are expressions that happen to work out to, respectively, 8/12 and 9/12. If the + operation is designed to notice that the denominators are identical, it has an easy job spitting out 17/12. OTOH if the implementation were aggressive about reducing every time it was possible, the value of A and B would be made into, respectively, 2/3 and 3/4, giving the addition operator an extra work load.

This is based on my observations of a homebrew rational number arithmetic library, more precisely, a 3D library making use of projective geometry, where a vector would be represented by four numbers (x,y,z,w) and these mapped to the usual rectangular 3-d coordinates as (x/w, y/w, z/w). This had to run fast, and it often happened that,for a given geometric model and calculation to be performed, i'd be adding and subtracting rational values with various numerators but identical denominators (well duh, all divided by some w), when no reductions were performed, and of course that ran much faster than when every calculation aggressively reduced its results.

The trade-off is that one quickly ran out of room when allowing numerators and denominators to build up out of control.

Re:decNumber libary from IBM

[Anonymous Coward]

Why would you use a factoring algorithm when you could just use the Euclidean algorithm to find the GCD of (n/d), and then divide the numerator and denominator by them?

If I had a factoring algorithm which was "proportional to the terms themselves" - that is, O(n) - I'd want to show it off, too. Though I'd probably restrain my urge until after I'd broken into RSA-protected bank systems and become ludicrously wealthy.

(Actually, I guess the commonly-stated running times are in terms of the number of bits, which is (lg n). So O(n) would be O(exp(b)), which isn't even as good as the general number field sieve. I killed my overly geeky joke. Oh well.)

Re:decNumber libary from IBM

[piranha(jpl)]

You're right; I've obviously never implemented a rational arithmetic library. Thanks for pointing that out.

Re:decNumber libary from IBM

[master_p]

Ehhhmmm, as a programmer, I have to say that all these details really detract me from doing my job. Why not have a single type 'number' which does the job as needed? without us needing to know all the gory details?

Re:decNumber libary from IBM

[Jonner]

Scheme comes pretty close.

Re:decNumber libary from IBM

[Moofie]

Perhaps for reasons similar to why a carpenter doesn't just have a tool named "tool" that just takes care of the gory details.

Re:decNumber libary from IBM

[master_p]

I don't think the analogy you present is entirely correct, for these reasons:

1) a tool named "tool" for all of carpenter's tasks would be analogous to a programming language having 'number' as the only datatype, which is not what I said.

2) the carpenter uses different tools for different jobs. The programmer is required to use different tools for the same job, i.e. arithmetic.

A good middle ground would be a programming language with a datatype 'number' to handle all numerical/arithmetic tasks along with many other specialized datatypes. Let us common folks who code the average business apps to use it, and you can use your own specialized types in any way you wish.

Use A Proper Decimal Library

[Anonymous Coward]

If you are actually concerned about rounding and precision, use decimal instead.

I am Intel of Borg

[www.sorehands.com]

I am Intel of Borg, you will be approximated.

There have been many examples, such as the original pentium bug. Of course, there was a bug in Windows Calc, it was 2.01 - 2.0 = 0 (If I remember correctly).

Re:I am Intel of Borg

[Saxophonist]

While Intel's gaffe is possibly the most famous, consider this tidbit from Applesoft Basic:

] PRINT 8 + .01 + .01
8.020000002

Granted, this was a software implementation bug, not a hardware bug. (I don't recall the exact precision of the response, but it was something of that nature.)

Re:I am Intel of Borg

[certsoft]

There was a much less public fault in some 68882 FPUs from Motorola. Back in the last century we were using VME-147 boards that used a 68030 and 68882. We were running into some problems with floating point calculations giving the wrong result. At first Motorola denied there being a problem but we were able to produce a very simple test program that showed the problem. It turns out one version of the 68882 did have a problem where there was crosstalk between bits on the die. They ended up having to replace lots of VME-147 boards.

Re:I am Intel of Borg

[Max Threshold]

It was 3.11 - 3.1 = 0. I remember because I thought the implication was funny that Windows 3.11 was no better than Windows 3.1.

Re:I am Intel of Borg

[meowsqueak]

I see this every day. As of right now, with Python 2.4.3:

>>> 8 + .01 + .01
8.0199999999999996

>>> 1.0 - 0.1
0.90000000000000002

I believe this is to do with the fact that you cannot represent 0.01 exactly in base two so Python stores 0.1 as 0.10000000000000001.

(try 1/128)
>>> 1.0 - 0.0078125
0.9921875

(change it slightly)
>>> 1.0 - 0.0078124
0.99218759999999995

Re:I am Intel of Borg

[ubeans]

Of course, there was a bug in Windows Calc, it was 2.01 - 2.0 = 0 (If I remember correctly).

Not exactly, but close enough.

Re:I am Intel of Borg

[Anonymous Coward]

Well, it is close enough for Microsoft and Intel.

The author is seriously confused

[mlyle]

Apparently the author of the article didn't read the stories in RISKS that he cited. In particular, the 'pensioners being shortchanged' one talks about them not being paid interest on 'float'-- cash flow on transactions in progress. This has little to do with floating point numbers.

Similarly, the spacecraft problem mentioned is one of an errant cast, not because of dilution of precision in floating point calculations.

The author could really pick his examples better-- as mistakes in numerical programming happen often and are often of great import.

Re:The author is seriously confused

[mlyle]

Sources for the above:

Pensioners shortchanged of 'float'

Ariane casting problem (float -> 16 bit int)

re: The author is seriously confused

[tuc]

The author could really pick his examples better

The RISKS stories aside, I think the choice to discuss rounding was an excellent pick.

Everyone learns that floating point is imprecise in cs101, but how many people realize that

int n = round( (float)int1 / int2 );

will sometimes be off by an entire unit unless they are very very careful?

In my code I haven't yet needed to care which way the rounding goes for values with fractional parts very close to .5, but not everyone has that luxury.

Not news.

[SJasperson]

This is not a new problem. Or an unsolved one. Is there any modern programming language that does not supply a data type or library with exact decimal arithmetic support? Using a float to represent monetary amounts and expecting them to be free of rounding errors is as stupid as using integers to store zip codes and wondering where the leading zeros went from all the addresses in New England. If you can't be arsed to choose the right data type get out of the business.

Re:Not news.

[SuperBanana]

Using a float to represent monetary amounts and expecting them to be free of rounding errors is as stupid as using integers to store zip codes and wondering where the leading zeros went from all the addresses in New England

For those of us who aren't programming geniuses- what would you use to store a monetary amount, besides a floating-point format?

Re:Not news.

[kingkade]

A fixed-point (or "decimal" types). see decimal in c#, BigInteger in Java, money/dec in SQL server, etc. Pay attention, and please tell me youre still in high school.

Re:Not news.

[WuphonsReach]

For those of us who aren't programming geniuses- what would you use to store a monetary amount, besides a floating-point format?

In databases? Currency formats. Which are specifically designed not to lead to rounding errors. Some of them even allow you to specify the number of places after the decimal.

In code? A numeric type designed for currency work (typically an add-in library). In a pinch you can use a 32bit integer and use the last 2 decimal digits as "cents", but you'll run the risk of overflow.

Re:Not news.

[MajroMax]

For those of us who aren't programming geniuses- what would you use to store a monetary amount, besides a floating-point format?

Without the use of any libraries? Integers -- just use cents as the base unit of currency, and convert to dollars strictly on input and display.

If you're dealing with amounts of cents that could possibly start overflowing even a 32-bit int (that is, billions of cents, or tens of millions of dollars), then the application's important enough to be worth the cost of further research on the matter.

Re:Not news.

[Anonymous Coward]

Easy. An integer. Store the value in cents, not in dollars. Then when you need to print it out, you'd do something like

printf("$%d.%2d", (val / 100), (val % 100));

(Approximately; you get the general idea.)

If you need fractions of a cent, you'd store the value as multiples of that fraction, and do the conversion to currency at the absolute last possible moment.

The only case where this would cause problems is when you need to do a division of some sort, but all of this stuff is a very well known, and already solved, problem. (Oh, irony: the captcha for this post is "divisive".)

Re:Not news.

[smallpaul]

Did anyone claim it is a new problem? Of course it will be new to some people and old hat to others. As soon as I saw the title I knew what it woudl be about, but there are always new programmers coming through the system who don't know this stuff.

Re:Not news.

[mcrbids]

Using a float to represent monetary amounts and expecting them to be free of rounding errors is as stupid as using integers to store zip codes and wondering where the leading zeros went from all the addresses in New England.

Hrrmm, well...

That would explain our lack of customer response in New England...

Re:Not news.

[Euler]

Decimal type, (not as commonly available as floating point type.) You could also store money as an integer by counting cents. Or you could use an integer for dollars and another for cents.

Re:Not news.

[colinrichardday]

In code? A numeric type designed for currency work (typically an add-in library). In a pinch you can use a 32bit integer and use the last 2 decimal digits as "cents", but you'll run the risk of overflow.

In my case, only on the negative side :-)

Re:Not news.

[Anonymous Coward]

> Or you could use an integer for dollars and another for cents.

Isn't that just like a 64-bit int except less efficient?

Re:Not news.

[gweihir]

For those of us who aren't programming geniuses- what would you use to store a monetary amount, besides a floating-point format?

E.g. long long with cents as the unit. Gives you a maximum value of 180 000 000 000 000 000 full currency units. Should be enough for most apps and gives you exact calculations. And takes only 64 bit,
same as double.

Re:Not news.

[Duhavid]

Binary Coded Decimal would be one.

I looked for a page that described the advantages
of BCD, but I could not find one. So I'll have a
stab at it myself. Basically, while slower, BCD
can maintain arbitrary precision. If you have
monitary items and you have a good handle on the
range of values, you can store and operate on these
values without any rounding losses at all.

Re:Not news.

[codegen]

For those of us who aren't programming geniuses- what would you use to store a monetary amount, besides a floating-point format?

Decimal data types. In COBOL or PLI (in which most of these applications are written in) you use a PIC data type.For example,

PIC 9999V999

says the number has 4 integer digits and 3 fractional digits. It also may not hold a negative number. You add an S character to the front to allow negative numbers.

The language runtime interprets the numbers and there is no approximation involved. There are strict rules for overflow, underflow and roundoff. You can delcare any numeric type up to a total of 18 digits in these languages. Other comments have already referred to the C library and to similar types in other programming languages.

Re:Not news.

[fm6]

Using a float to represent monetary amounts and expecting them to be free of rounding errors is as stupid as using integers to store zip codes and wondering where the leading zeros went ...

It's not stupid, it's just ignorant.

Your comparison with integer zip codes is totally bogus: that's not an arithmetic error, it's just sloppy formatting. The variable contains a perfectly accurate value — you just have to remember to output it with a %05d format. (Of course, since you don't do arithmetic on zip codes, you might as will forget the whole problem and just store the thing as a string.) On the other hand, the rounding errors you get when you try to store decimal fractions as floating point stem from an extremely unobvious fact: many common values (such as 0.1) do not have a binary representation.

Re:Not news.

[Jerry Coffin]

If you're dealing with amounts of cents that could possibly start overflowing even a 32-bit int (that is, billions of cents, or tens of millions of dollars), then the application's important enough to be worth the cost of further research on the matter.

...especially when you can find roughly 10 gazillion alternative for about $1 worth of research time.

Unfortunately, most of the obvious alternatives are either somewhat restrictive, or have relatively poor performance. For example, on a 64-bit machine, a 64-bit integer works quite nicely -- but of course, most people aren't (yet) using 64-bit machines. There are quite a few arbitrary precision integer packages available, but most of them are substantially slower than a float or a double for most calculations.

Unfortunately, quite a bit of calculation with money really will run into problems with being stored in a 32-bit integer. If you're dealing strictly with US currency, you're right: the problem only arises with quite large amounts of money. OTOH, if you have to deal with international currency, the problem can (and will) arise far sooner. Just for a couple obvious examples, there are around 27 Russian Kopecks or about 39 Zambian Kwacha to one US penny. Even inside of the US, some things have prices that include fractions of a cent (e.g. Gasoline often has .9 cents tacked onto the end of its price, and some stock/bond/commodities markets use prices in eights of a cent).

In a lot of cases, the best alternative to using floating point is to use floating point. No, that's not a typo. What you want to do is store an integer number of pennies -- but store it in a double (or on ocassion, a long double). A typical implementation of double can also be used as a 53-bit integer type. A 32-bit number is right on the edge where it's often usable, but can easily run into problems. A 53-bit integer makes those problems much more remote -- to the point that by the time you're dealing with such a large amount of money, you probably don't want to know about pennies anymore. A long double will store a 20 digit integer -- so it should be usable even for something like figuring the stock dividend of a large company.

As long as you're careful about order of calculation and when you do rounding, this gives the added bonus of working nicely for things like converting one currency to another, that are relatively difficult to do with pure integers.

Re:Not news.

[Fulcrum of Evil]

Frankly, if you can't find out on your own, you have no business writing code. This is not rocket science.

Re:Not news.

[Euler]

true. It's not the best solution, just one possible way to do it. Other posters described it better than I did - it's best to use a dedicated money-type if you can get access to it. But the topic at hand is that floating-point isn't the automatic answer just because you have a non-integer value to represent. It is a complex representation problem with non-trivial complications that include issues such as overflow, rounding, storage efficiency, cents, fractions of cents in some cases but not in others, accumulated error, internal representation, expressed representation, internationalization, etc.

Re:Not news.

[Angst Badger]

That's not a data type problem; it's being too stupid to format the output properly.

Re:Not news.

[SuperBanana]

Frankly, if you can't find out on your own, you have no business writing code.

I DON'T WRITE CODE. That's why I asked the fucking question.

Re:Not news.

[ceoyoyo]

Um, what is the problem with using a float as a currency type? Sure, you have to not be incompetent and remember to round it to two decimal places before you display it, otherwise it looks funny. You also have to not be incompetent and check to make sure you're not exceeding the maximum size.

If you use an integer and you overflow it, depending on the specifics, you'll either get a negative number or a crash. If you're using a float you'll start to get your cents rounded off, then, as things get worse, your dollars. Either way it's bad and you should be checking for that sort of thing and/or using a larger data type.

The problem is not that floats don't work, it's that they fail more gracefully than integers. Either way, somebody screwed up.

Re:Not news.

[Baki]

However, this should not lead to using decimal arithmetic in all cases. Just be sure you know about the rounding errors and deal with them.

There are a number of programming languages in use in financial institutions (cobol, pl/1) that offer built-in support for decimal arithmetic. It makes sense in some cases, but also has a drawback: e.g. the type 'decimal fixed(15,6)' always has 15 positions of which 6 are after the decimal point. This type always automatically rounds, constantly, which may lead to inaccuracies just as well.

As we know from primary school, multiplication adds the the number of digits of the arguments, dividing potentially leads to an infinite amount of digits.

The problem with decimal numbers is that the location of the decimal point is fixed (e.g. in the 15,6 case, there are always 9 places before and 6 after the decimal dot. The dot doesn't "float". In floating point numbers at least, the precision is just as limited (though quite high for doubles) but the decimal point location always floats to the optimal position.

Imagine calculating with decimal fixed for a while, and in some intermediate result you get some amount of only 0.01. Now since the dot is fixed, you're left with only 4 significant places in your intermediate result, and any result afterwards only has this amount of precision as well. I claim there are way more programming problems due to this than due to floating point representation inaccuracy.

Java and some other libraries represent decimal numbers (BigDecimal) by a string and a scale factor (how much of the number is after the decimal dot) that can be infinitely big but remain totally accurate except for divisions. A multiplication B1 * B2 generally will add the number of digits of the both, so the memory requirement of the result will be that of B1 and B2 together. For a division, you'll have to specify how many digits remain, so you'll still have rounding problems here. As you can imagine, a single number easily can get 1MB in size, and operations with these are extremely slow to the point of not being practical anymore for many purposes.

Even with financial calculations, floating point numbers often are the best and only choice. Your algorithm will have a known accuracy even if you have very small or big intermediate results. You can only use BigDecimals if you have very litte calculations and no divisions (except for scale chances, e.g. division by 100). However, be aware of the rounding and accuracy, and take care when comparing numbers. We use some simple library that compares doubles to 0, taking into account some small margin, within this margin the number is considered to be 0. You must round sometimes in between (usually there are official rules for when and how intermediate results of financial calculations have to be rounded to, e.g. one cent).

Re:Not news.

[Anonymous Coward]

Go home, asshat!

Re:Not news.

[honkycat]

Well, there is also the problem that is the central point of the linked article -- namely, you can't guarantee that you've rounded your float correctly. If you require correct rounding in all circumstances, you cannot use a float, no matter how clever you try to be about it. That is, unless you manage to out-clever everyone else who's ever tried to solve this problem. (not to say it's impossible, but for most programmers, it's probably better to find a library that's designed for accurate rounding)

Re:Not news.

[Rakshasa Taisab]

Actually, no... Storing zip codes in integers make perfect sense, assuming they are fixed-width. It is rather they formatting used to display it that is buggy if it does not show the leading zeros. But then, using integers will make it difficult if you ever need to extent it to support other formats.

Re:Not news.

[Baki]

never use integers if you're not going to calculate with them
i don't think one is ever going to add zipcode1 to zipcode2, so use a string here.
b.t.w. in many countries, zip codes may contain characters.

Re:Not news.

[danskal]

I shouldn't waste my virtual breath answering your post, but I can't resist. I truly believe you are wrong, in so many ways!

1. If this topic was so easy, there wouldn't be so many varying, and failed approaches to the problem discussed here.

2. This sort of problem should be dealt with by an architect on a project, not a coder - it is not something that coders should have to bother about.

3. This topic is only "easy" if you dealt with it at length on an appropriate course. If only computer science graduates were allowed to code, the internet as we know it would simply not exist. On most of the (large) projects I've been on, less than half or even less than a quarter had a Bachelors degree in IT.

It would be nice if everyone got the right degree before starting, but the real world just doesn't work like that.

Re:Not news.

[ynohoo]

There are a number of programming languages in use in financial institutions (cobol, pl/1) that offer built-in support for decimal arithmetic. It makes sense in some cases, but also has a drawback: e.g. the type 'decimal fixed(15,6)' always has 15 positions of which 6 are after the decimal point. This type always automatically rounds, constantly, which may lead to inaccuracies just as well.

Er, no. If you want rounding in COBOL, you explicitly say so by adding ROUNDED to the statement.

Even with financial calculations, floating point numbers often are the best and only choice. Your algorithm will have a known accuracy even if you have very small or big intermediate results.

No, never use floats for financial calculations, unless you use an algorythm to fix the known inaccuracy in the calculation, and do not compile with optimisation (which will assume it knows better than your code). Even using strict integers or packed decimals can run into some rounding problems; adding a couple of decimal places during the calculation phase can solve most of these, but cannot eliminate them completely, so sometimes you have to find a method of handling the stray pennies.

Re:Not news.

[scotch]

Never?

There are many instances when using 4 bytes to store a zip in an int would be preferrable to storing it in 5 (or more!) in a char[5] or string. In these instances you might lose even more space due to packing of the odd sided char array.

Re:Not news.

[greed]

For example, on a 64-bit machine, a 64-bit integer works quite nicely -- but of course, most people aren't (yet) using 64-bit machines.

You sure about that?

There are a lot of HP PA, Sun SPARC, and IBM POWER systems in banking and finance. All of those architectures have had 64-bit support for a long while now, even though the bulk of programs running on them still use 32-bit mode. The IBM big iron has got all sorts of toys for arbitrary precision arithmetic--they've been in banking and insurance for a while now, and it's all a solved problem on whatever the mainframes are called this month. (Still requires your programmers to use the tools available, which is always the hardest problem.)

On the desktops, it doesn't matter so much if you don't have native 64-bit support. As long as you can communicate sufficiently large numbers to the back-end system, and the safest way to do that is send the undecoded ASCII string. But even if you do convert to a 64-bit int on a 32-bit CPU, you're not doing heavy math with it on the desktop, so performance isn't a big deal.

Re:Not news.

[Fulcrum of Evil]

1. If this topic was so easy, there wouldn't be so many varying, and failed approaches to the problem discussed here.

You could say that about the many things that show up on the daily wtf. The presence of poorly coded apps doesn't mean that it's hard to do right.

3. This topic is only "easy" if you dealt with it at length on an appropriate course.

Numerical methods is a required course - if you get a CS degree, you probably saw something like this.

If only computer science graduates were allowed to code, the internet as we know it would simply not exist.

Got that right. Letting a flood of noobs code all your software is a recipe for disaster. Or did you mean this in a different way?

It would be nice if everyone got the right degree before starting, but the real world just doesn't work like that.

Yeah, it's just coding - you can pick that up anytime. Why let Joe in accounting who 'knows a little VB' write your accounting app?

Re:Not news.

[ceoyoyo]

As others have pointed out, all the article's examples of catastrophe's happening because of floating point math are bogus. The ones that have anything to do with floating point at all happened because someone careless converted FROM floating point, not because the number was floating point to begin with.

The biggest problem seems to be that the author doesn't understand something that is taught in basic mathematical science classes. You never, EVER use a calculation that's been rounded off to your significant digits. You must always carry extra precision (the more the better) until you're absolutely done your calculations. In other words, just because you round to the nearest number of cents before you pay someone doesn't mean you should do it regularly, or base any further calculations on that rounded value.

Let's take a compound interest problem and calculate it using incorrect rounding-every-transaction floating point, correct floating point and integer counting of cents as others have proposed.

Let's say I deposit $1000 in a fictional account that generates a steady 5% per annum, compounded daily. Real accounts don't do that, but I want a constant interest rate so I can use a formula to find the correct answer. I'm also using 365 days in a year for simplicity.

Using a formula (one transaction) at the end of ten years I have: $1648.66. This is the correct answer, to the nearest whole cent.

Proper floating point, with a transaction completed daily: $1648.66

Incorrect floating point, rounding each daily transaction to a whole number of cents: $1648.34

Using integer math, counting the number of cents... you can't do it. But if you keep the number as an integer most of the time and do floating point multiplication for the interest calculation, you get: $1648.34.

So the ONLY correct way to do that particular calculation is to use floating point, correctly. Naturally (so I've heard) the banks have their own way of doing it, where they truncate to the nearest whole cent, ie always round down. That gives $1624.57.

The moral of the story? Don't intermediate results! If you need that reinforced, go talk to a high school chemistry teacher.

Re:Not news.

[honkycat]

Their examples may be wrong, but the basic point is still correct. Given a float representation, you cannot guarantee correct rounding, even in your very last step. You can do everything right, preserving all the digits you've got, all the way through. At the end, your approximation may end up slightly above or slightly below your precise threshold. If your application demands that you round correctly (in base 10) 100% of the time, your float implementation cannot guarantee that. Add as much precision as you like and there's still a risk that you end up on the wrong side of the fence.

In your example, this amounts to the admittedly unlikely case that you end up with a calculation that gives 1648.659999999999999999994 instead of 1648.66000000000000002. (I did not check that to be sure it's really a pair of base-2 fractions, but that's incidental) When you round that, getting the correct answer depends on guaranteeing you get the right one of those. This has nothing to do with throwing away precision.

There are many alternatives to floating point for this. They're not as fast on the binary hardware we've got, but basically you need to avoid working in a base other than the one you need accuracy in. If you do your math using a base-10 library, then rounding is easy and can be guaranteed. Likewise, if you need accurate rounding in base-2, then go ahead and use a float (as long as your value doesn't "overflow" past the precision of your mantissa).

Most of the time, the odds of an error like this are small enough that the occasional error is tolerable. But, when it's not tolerable, it's not tolerable...

Re:Not news.

[TekPolitik]

Never?... There are many instances when using 4 bytes to store a zip in an int would be preferrable

You're right - you can store postal (ZIP) codes in an int if you can guarantee that your application will never have to deal with foreign postal codes that use letters (such as in the UK), or use the extended ZIP codes that have been available in the US for 15 or so years now. So provided the business you are writing the application for will never have a foreign customer, never have a use for extended ZIP codes, will never grow to be an international company or be acquired by one, and provided you're certain the USPS will never expand the range of characters in the ZIP code, an integer may be an appropriate choice.

This set of circumstances approximates well to "never".

Just because something looks like an integer when it's written down, that doesn't make it one. By using an integer you build in an assumption that may require extensive work later on to fix, when using a more appropriate data type up front may have avoided all that for no real cost. This is similar to the Y2K problem, caused by idiots who did not consider the true nature of the data they were dealing with. Unfortunately in that case the rest of us had to deal with the dumb questions from people wanting additional "certification" and "testing" for a problem we'd dealt with long ago.

It is, however, wrong to say that you should never use floats for financial calculations - it all depends on the degree of tolerance for error in the application. I suspect people who say not to use floats are familiar enough with them to know they have rounding errors, but not sufficiently familiar with them to know how to deal with them - that is, to them, a person who sees a floating point rounding error and does not recognise what it is looks stupid, but to others with more knowledge and experience in numerical methods the person who treats floats as anathema looks just as stupid. Numerical methods is a separate subject in Comp Sci degrees for a reason - it's a shame it's not a compulsory one in many.

Re:Not news.

[scotch]

This set of circumstances approximates well to "never".

Only for incorrect values of "never".

Your analysis of the zip-code issue is great, but not really the point. There are problem domains where storage efficiency of some data is of the upmost importance. In these domains, the cost of re-engineering is likely to be either a) acceptable or b) unavoidable if assumptions about the form and content of data like zip-codes change. There are other domains where a) and b) apply but in which storage is not so important.

The year 2k problem was costly, but that does not mean that every choice in the latter half of last century to use a 2 digit year was incorrect. Where is your analysis of the cost of putting full 4 year dates in every application written in the 20th century? Be sure to include all applications that were ephemeral and didn't make it to the 21st century. Be sure to include the cost for expanded storage and decreased performance for all of the applications.

That is the kind of analysis you need to use words like "never".

P.S. - here's a hint: Don't pretend to lecture if all you know is hard and fast rules. That kind of knowledge makes you a reference manual, not an engineer.

Re:Not news.

[Breakfast Pants]

.1 could be stored as 00011010. Look, it does have an (emphasis not added)binary representation. It happens to be one I just made up, but it's there. 0001 is the numerator, 1010 is the denominator.

Re:Not news.

[fm6]

I should have said that 0.1 does not have a binary floating point representation — though I think that was implicit in the context. We're talking about decimal values as they appear in common programming languages.

There are any number of data formats that represent common decimals without rounding. But they aren't intrinsic in lot of common programming languages. That's particularly painful in Java, which doesn't have operator overloading. So you have to say stuff like BigDecimal fraction = new BigDecimal(1).divide(new BigDecimal(10)).

Back in the 70s, IBM's great invention was PL/1 (Programming Language 1: the first real programming language!). This had an intrinsic data type for everything. There was even a data type for pounds, schilling, pence, so you could write code that added 5 schillings sixpence to 15 schillings tupence and get 1 pound 8 pence. (Ironically, this was about the time the UK decimalized its currency.) Alas, there were some serious design flaws in PL/1 (parsing a language with no keywords is hard), and it never caught on.

Tax

[nusuni]

Would certainly be a real kicker to find out that these tiny miscalculations caused everyone to pay more tax than they needed to. Where's my refund check?!

Re:Tax

[darkitecture]

Would certainly be a real kicker to find out that these tiny miscalculations caused everyone to pay more tax than they needed to. Where's my refund check?!

I'm sorry but you already spent it. The money that wasn't there from the budget surplus we didn't have was spent on providing tax relief that wasn't actually much of a relief in an attempt to stimulate the economy, which it didn't do.

science; business

[bcrowell]

He talks about scientific applications, but actually very few scientific calculations are sensitive to rounding error. Remember, they sent astronauts to the moon using slide rules. Generally for scientific applications, you just don't want to roll your own crappy subroutines for stuff like matrix inversion; use routines written by people who know what they're doing. (And know the limitations of the algorithm you're using. For example, there are certain goofy matrices that will make a lot of matrix inversion algorithms blow chunks.)

For business apps, the classic solution was to use BCD arithmetic. But today, is it more practical (and simple) just to use a language like Ruby, that has arbitrary-precision integers, so you can just store everything in units of cents? A lot of machines used to have special BCD instructions; do those exist on modern CPUs?

Re:science; business

[rubycodez]

you'll be delighted to know your 80386 or later x86 supports packed and unpacked binary coded decimal. incidently, matrix inversion is a crappy way to solve linear systems, there's much better ways that don't cause tiny approximation errors to magnify many-fold.

Re:science; business

[Jeremi]

But today, is it more practical (and simple) just to use a language like Ruby, that has arbitrary-precision integers, so you can just store everything in units of cents?

Hmm.... if you use integers of any given finite precision, aren't you still subjecting yourself to round-off error? (e.g. ((int)4)/((int)3) == 1!!) On the other hand, if you use a string-based infinite-precision datatype, what happens when you try to compute an non-terminating number (e.g. 1.0/3.0)? Perhaps your program crashes after trying to allocate an infinite amount of RAM to store the result? ;^)

Seems to me the only full solution to round-off error would be to store the results of certain math operations as strings indicating the underlying mathematical/algebraic expressions (e.g. 1.0/3.0 == "1/3"), a la Matlab... but then, I'm no expert, perhaps there is a better way.

Re:science; business

[bcrowell]

Seems to me the only full solution to round-off error would be to store the results of certain math operations as strings indicating the underlying mathematical/algebraic expressions (e.g. 1.0/3.0 == "1/3"), a la Matlab... but then, I'm no expert, perhaps there is a better way.
I'd love to have someone write me a check for $1/3. If I deposited it at an ATM for $0.33, would I get arrested? Would I read about it in the paper the next morning? BANK'S COMPUTER BLOWS UP, GOOFY CHECKED BLAMED.

Re:science; business

[Kuciwalker]

Seems to me the only full solution to round-off error would be to store the results of certain math operations as strings

Congratulations, you just invented the binary coded decimal.

Re:science; business

[dido]

AFAIK, Matlab deals mostly in ordinary floats, and does none of the esoteric things you mention to develop perfectly exact numbers. That's mainly the province of symbolic mathematics packages such as Mathematica, Maple, and (for something just as powerful that's actually Free Software) Maxima. These programs are actually capable of performing exact arithmetic even on irrational and transcendental numbers, by using rational numbers where this is possible, and by representing irrational/transcendental numbers as functions involving only rational numbers that can be used calculate the number to arbitrary precision, e.g. they might represent pi by using one of the many available power series expansions for it, and use their symbolic mathematics system to take care of the manipulations. Needless to say, this is very expensive, and massive overkill for almost everything but mathematics research and some specialized work in theoretical physics.

Re:science; business

[mwvdlee]

IBM's z/OS mainframes still use (packed) BCD primarily.
Pretty much every financial institution uses z/OS (formerly named OS/390) mainframes.

Re:science; business

[GregAllen]

underlying mathematical/algebraic expressions (e.g. 1.0/3.0 == "1/3"), a la Matlab

I think you mean Mathmatica.

Matlab uses double precision floats for everything. In later versions, you can explicitly request other data types, but many of the old functions will only work on the default data type. There is a Symbolic Math Toolbox that probably lets you do this, but it is certainly not Matlab's standard method.

Re:science; business

[Anonymous Coward]

"but actually very few scientific calculations are sensitive to rounding error"
Obviously you haven't written any digital simulations of analog processes. Roundoff and bruising is a significant source of error in the calculations. These equations are often implemented as difference equations with a multiplication coefficient for each of the terms in the equation. As the equation converges, the probabibility of subtracting .000000000031159 from .00000000003118 is real. What is worse the difference would be multipled by something like 45861859324 for the final result. In this type of programming, it is neccessary to have at least 16 bits more than twice the desired process resolution. Only by doing this can you insure the roundoff and bruising of the results can be minimized.
This approach may mean you will need to define a custom number format and custom math libs to maintain your accuracy.

Re:science; business

[Jeremi]

Congratulations, you just invented the binary coded decimal.

Really? Cool! As an example, can you tell me what the BCD representation of exactly 1/3 would be?

Should read...

[Anonymous Coward]

Should read, "write code that does arithmetic." Don't kid yourself and think you are doing anything remotely close to
real mathematics.

The business...

[kingkade]

This happens more often than you might think. I used to work for a large American software corp. One of their products which I had the pleasure of being on one of two teams who were working on it, had an accounting portion that used floating point columns in our DB schema and in code. I just was kind of disgusted and a little disturbed after finding this software's used by some pretty large organizations to track assets, etc.

This reminds me of something someone I knew said once: you don't really have to be intelligent to work in this industry or even get through school, just like everything else in life, it seems that brute force is enought to win most of the time.

This is not a "problem" per se

[Null Nihils]

float (and the big brother double) is inaccurate. Its no surprise. A 32-bit Float is but a single simple tool in a programming language. If anyone is surprised by how Floats behave then they are, most likely, inexperienced.

You don't start addressing a problem in software just by assuming Float or Double will magically fill every need. An experienced programmer needs to have a knowledge of how to use, and how not to use, the programming tools at hand. TFA about floating point numbers is very introductory (at the end it mentions that the next article will tell us how to "avoid the problem"... I assume it will go on to cover some basic idioms.) In a way it misses the point: Floating-point rounding is not a "problem". Floats and Doubles always do their job, but you have to know what that job is! The behaviour of floating point numbers should not be a big surprise to a seasoned coder.

For example: You can't use float or double to store the numerical result of a 160-bit SHA-1 hash... you have to use the full 160 bits. (Duh, right?) So, if you use a mere 32 bits (float) or 64 bits (double) to store that number, you are going to sacrifice a lot of accuracy!

Re:This is not a "problem" per se

[kingkade]

For example: You can't use float or double to store the numerical result of a 160-bit SHA-1 hash... you have to use the full 160 bits. (Duh, right?)

?

I don't get it...why would you even try, what's the point of mentioning something so obvious? It's like me saying: "Hey don't even try storing your new titanium, five-iron in your asshole: since your rectum is only a few inches wide and a five-iron is over a meter long!"

Re:This is not a "problem" per se

[Wonko the Sane]

A much better article is linked from this one near the bottom: what every computer scientist should know about floating-point arithmetic

Re:This is not a "problem" per se

[Anonymous Coward]

since your rectum is only a few inches wide and a five-iron is over a meter long!"

Well, obviously you don't try to stick it in sideways !

Re:This is not a "problem" per se

[mwvdlee]

I've never had any problem using floats working with 2 digits after decimal point. Likewise I've never had any problems using integers to count up to 100. The problems begin when people start using these datatypes for stuff they were never meant to do; nobody ever claimed floats work for near-infinite numbers or several hundred digits after decimal point.

You don't need to use floats to do math

[Anonymous Coward]

I did a model of universal expansion using only ints that proved conclusively that the universe is 6 years old.

Use Gnumeric and the Source.

[twitter]

1.125*59=66.375 in gnumeric. Yes, it rounds to 66.38. So it's not really a problem and you can beat the author to the punch by looking at the gnumeric source.

Numbers and bases

[Todd Knarr]

We have the same problem in everyday numbers. Try representing 1/3 in any finite number of digits. You can't. The big thing about floating-point numbers that trips people up is that we're used to thinking in base 10. Floating-point numbers in computers typically aren't in base 10, they're in base 2. The rounding problem he describes is simply us getting confused and wondering why a fraction with an exact representation in base 10 doesn't have an exact representation in base 2. The obvious solution is the one he alludes to at the end: don't use base 2. Computers have had base-10 arithmetic in them for decades, in fact the x86 family has base-10 arithmetic instructions built in (the packed-BCD instructions). COBOL has used packed-BCD since it's beginning, which is why you don't find this sort of calculation error in ancient COBOL financial packages running on mainframes.

Re:Numbers and bases

[kingkade]

You know, your low user ID would imply you've been around a while, but you totally missed the point. The base 2 is not the only problem and you don't need to switch and/or use BCD to avoid these problems. Read the article again (or for the first time) and if you still don't get it look up "decimal" or "fixed-point" types in your favorite strongly-type programming language.

Re:Numbers and bases

[tawhaki]

Try representing 1/3 in any finite number of digits.

0.3. All you need is base 9 :)

Re:Numbers and bases

[gweihir]

We have the same problem in everyday numbers. Try representing 1/3 in any finite number of digits. You can't.

That one is real easy: Don'r use a "real" format, i.e. floats. Use a "rational" format, i.e. two integers and the value is the one divided by the other. This is one of the standard formats in the Gnu multiprecision library.

Should be obvious really from standard shool mathematics, float approcimates R, but Q can be done exactly and is wherever needed and at least somebody has elementary mathematics skills.

Re:Numbers and bases

[flibbajobber]

Try representing 1/3 in any finite number of digits. You can't.

"1/3"

You can. I just did. So did you. In base-10, even. In fact, the answer is the same for base-4 or higher. Using only two digits, "1" and "3". Any rational number can be represented using a finite number of digits, using... (wait for it) a RATIO.

(Represent one-third in Base 2? why that would be "1/11". One-third in Base 3 would be "1/10".)

Re:Numbers and bases

[4D6963]

I think the GP poster has quite got the point tho. The problem isn't the IEEE-754 floating point, the problem is people not getting it right, in other words, people not understanding the binary precision of the mantissa when brought back to decimal. In school we were taught not to trust the IEEE-754 floats because it may represent 0.37 like 0.369999998, but the thing is that in real-life problems, well at least my real-life problems, that type of thing doesn't matter to me because my numbers wouldn't be particularly round in the decimal base. This being said, if you got a problem with getting 0.369999998 when you expect 0.37, then round off to the number of decimals you want, other than that, there is no problem once you trully understand how the thing works.

Re:Numbers and bases

[Todd Knarr]

Well, the other problem is the difference between decimal places vs. significant digits when it comes to precision. Most people are used to a fixed number of decimal places, and when you have to go to significant digits people get confused too. In practice, though, I run into decimal-vs-binary confusion far more often.

Re:Numbers and bases

[mopslik]

Try representing 1/3 in any finite number of digits...

...

The rounding problem he describes is simply us getting confused and wondering why a fraction with an exact representation in base 10 doesn't have an exact representation in base 2. The obvious solution is the one he alludes to at the end: don't use base 2. Computers have had base-10 arithmetic in them for decades...

Maybe I'm missing something, but I don't see how this is obvious at all. Something does not have an exact representation in base 2, so we should use base 10. This still does not solve problems like 1/3 above, which has no "finite" representation in base 10 (unless you move into using a ratio class)? Short of having a "has an exact representation in base N" lookup table, I don't see how choosing a specific base can help, except for some cleverly contrived examples.

As others have pointed out above, a better solution is to use decimial arithmetic. You'll pay a performance penalty, but you won't run into these same errors.

Re:Numbers and bases

[exp(pi*sqrt(163))]

Try representing 1/3 in any finite number of digits

OK

>ghci
...
Loading package base-1.0 ... linking ... done.
Prelude> :m Ratio
Prelude Ratio> 1%3
1%3
Prelude Ratio>

Am I missing something?

Re:Numbers and bases

[Todd Knarr]

The problem isn't really that some numbers can't be represented exactly, it's that base-2 has different numbers that can't be represented exactly than base-10. People aren't suprised when 3-for-a-dollar results in oddities (33 cents each, but 3x33 isn't 1 dollar), but get suprised when 10-for-a-dollar behaves the same way on a computer.

Re:Numbers and bases

[Anonymous Coward]

Try representing 1/3 in any finite number of digits. You can't.

1/3 = 0.1 (base 3) (exactly).

The big thing about floating-point numbers that trips people up is that we're used to thinking in base 10.

You are so right.

Re:Numbers and bases

[TekPolitik]

0.3. All you need is base 9 :)

Hence the use of base 60 by the Babylonians - easy representation of division by 2, 3, 4, 5, 6, 10, 12, 15, 20, 30 and 60.

It used to be much worse. Kahan fixed it.

[Animats]

Due to the efforts of Willam Kahan at U.C. Berkeley, IEEE 754 floating point, which is what we have today on almost everything, is far, far better than earlier implementations.

Just for starters, IEEE floating point guarantees that, for integer values that fit in the mantissa, addition, subtraction, and multiplication will give the correct integer result. Some earlier FPUs would give results like 2+2 = 3.99999. IEEE 754 also guarantees exact equality for integer results; you're guaranteed that 6*9 == 9*6. Fixing that made spreadsheets acceptable to people who haven't studied numerical analysis.

The "not a number" feature of IEEE floating point handles annoying cases, like division by zero. Underflow is handled well. Overflow works. 80-bit floating point is supported (except on PowerPC, which broke many engineering apps when Apple went to PowerPC.)

Those of us who do serious number crunching have to deal with this all the time. It's a big deal for game physics engines, many of which have to run on the somewhat lame FPUs of game consoles.

Re:It used to be much worse. Kahan fixed it.

[Anonymous Coward]

80bit was not part of IEEE. I don't know where you think it was.

Re:It used to be much worse. Kahan fixed it.

[mbakunin]

This takes me back.

I took honors Soph Math at Cal from Bill Kahan in 1988 as a freshman. Despite never changing clothes (I mean, they were always clean, but he always wore blue jeans and a blue shirt -- all semester long), BK was a very engaging lecturer, which the interview should convey. He was also something of a rat bastard as a teacher. If you didn't get it, you were to reapproach the textbook. I went to office hours. He was friendly, but not helpful.

He failed half the class.

Half.

The.

Class.

And these were kids at Cal (selection bias part one) taking a serious math class (two) and having chosen the honors course (three). Among other reasons, the utter lack of this sort of experience explains why I consider Ivy League schools lightweight for undergrads.

He gave us a four-year-old midterm. It happened to have been given in the doctoral version of the course. It was a well-written exam, I grant. I was nineteen, taking a midterm that had been designed for UC Berkeley math doctoral candidates. Sure, no problem.

He made both TAs take the final.

One of two TAs (not mine, she was great) failed it.

Let's just say that was the proudest B of my life.

To Kahan's credit, he convinced me to pony up for the HP 11C calculator and never, ever to take a Cal honors class again. I have a math degree, can you believe it?

Re:It used to be much worse. Kahan fixed it.

[SEAL]

Sounds like good ol' Rocket Reed's EE course at the U.S. Naval Academy...

During my time there, ~80% of his students went through that class with a D or F.

Gotta love tenured professors.

Rounding Floats

[ChengWah]

Floating point numbers are an approximation. So why would you use them for an exact answer? Duuuuhhhhhh

Floating Point Numbers are trouble...

[tlhIngan]

They're convenient while programming, but they can certainly be a PITA to use properly. First they don't compare properly (you can't test equality), and if you have to do multiplatform programming transferring floats, they had better be stored in standard format (which can have a nasty side-effect of slowing down your floating point arithmetic since after each operation the unit has to return it back to IEEE format from machine native).

I've seen programmers who never realized these facts and had them ask why their code didn't work (they stored statistics gathered from a monitoring unit on an ARM Linux embedded board, transferred them to a PC, and had nonsensical results). Altering the way they serialized their floats and doubles fixed that issue. And nevermind that processing a float on different architectures can have slightly different results (or big results, depending on how you write your code). I guess some people treat floating point numbers the same way as integers, when they're more approximation than anything.

Or you can write code like this guy - http://thedailywtf.com/forums/thread/71883.aspx

Re:Floating Point Numbers are trouble...

[Zan Lynx]

Oh yes, the equality thing. It can really surprise you.

For example, I was debugging an infinite loop in some SVG library. I run Gentoo and I compile with crazy options, because what is life without risk? Anyway, it turns out that if you do a thing like A = B, run a few functions and then test equality, A != B. This is because the storage in RAM and the storage in registers have different precision. It happened to work on the original developer's systems, but you've got to remember: Not all the world is a Intel i386/i686.

The summary is nonsense

[gweihir]

UIEEE754 specifies exact results. There is no room for interpretation. That means it is not the FPU we should be worried about but IEEE764. However I find that IEEE754 is quite well done.

On the other hand, people that programm with floats and do not know or understand IEEE754 are asking for trouble. But that is true with every type of library. Knowledge and insight can only be replaced by more knowledge and greater insight. El-Cheapo outsourcing to India or hiring people without solid CS skills as programmers is asking for trouble.

Re:The summary is nonsense

[gweihir]

P.S.: None of the described problems are in any way new or surprising. This is a very old discussion. Any decent CS or numerics course will explain what is going on and how to get around it. Also, there are good long-number libraries out there (e.g. GNU mp) that allow you to get past these problems as well, to any precision you like.

We ALL know??

[gwoodrow]

I got to about the 3rd sentence before the hamster running on the wheel in my head fell off and, in a daze, started pooping everywhere. That happens anytime I read something math related. Good thing math is just a fad.

Re:We ALL know??

[Anonymous Coward]

Dude, you are way ahead of the average clowns - they ain't got no detect-hamster-off circuitry. Seriously, I meant this as a compliment(sp?).

What are they teaching now?

[scuppy]

Did they stop teaching this stuff in first year university? As for the person who posted: "Try representing 1/3 in any finite number of digits" well, you and I just did using 2 integers.

Re:What are they teaching now?

[Shadyman]

I believe the poster meant "Try representing 1/3 in decimal form in any finite number of digits."

Again, that's easy, you use 0.3, with a 'repeating' bar over the 3, but that's beside the point.

Re:What are they teaching now?

[kfg]

So far as I can tell, remedial shoelace tying and staying inside the lines. 50% is a passing grade.

Of course these are only electives for humanities majors; who produce most of our published statistics.

KFG

Re:What are they teaching now?

[scuppy]

Easy and beside the point? You could sacrifice a bit in a floating point number to represent repeating, but I'd hardly suggest that mathematically processing it is easy. You really refer to visual representation, which is not the discussion. I would recommend representing 1/3 using a datatype composed of 2 integers as I said, or there are a few other alternatives suggested in other posts if obtaining the 2 integers is not easily done. Im sure there are many programming 101 type texts which discuss numerical representations of complex numbers.

Re:What are they teaching now?

[cathector]

i believe smalltalk amongst other languages has a somewhate native "rational" datatype, ie a pair of integers. sacraficing one bit won't work to indicate "repeating", btw. it works for 1/3, but it doesn't work for 2/7 : 0.285714285714285714...

Re:What are they teaching now?

[jZnat]

Sure it does; just use 0.\overline{285714}.

This is why you would choose...

[jd]

One of the many many solutions:

• Fixed-point numbers
  
• Berkeley MP or Gnu MP arbritary-length floating-point
  
• Co-processors with truly massive internal registers (I refuse to use less than 80-bit)
  
• Delayed calculation (ie: actually process a calculation at the end, storing the inputs and operators until you absolutely need the value - eliminates intermediate rounding errors and if the value is never needed, you don't waste the clock cycles)
  
• Don't use real numbers - apply a scaler or a transform such that ALL components of any scaled/transformed calculations must be integer, then only transform back for display purposes
  

The use of transforms for handling numerical calculations is an old trick. It is probably best-known in its use as a very quick way to multiply or divide using logarithms and a slide-rule, prior to the advent of widely-available scientific calculators and computers. Nonetheless, devices based on logarithmic calculations (such as the mechanical CURTA calculator) can wipe the floor with most floating-point maths units - this despite the fact that the CURTA dates back to the mid 1940s.

Re:This is why you would choose...

[philipgar]

logarithmic number systems (LNS) for computers were first proposed by Marasa and Matula in 1973, as a "better" approximation of numbers than floating point units. This paper compared the cumulative error from different floating point standards with LNS standards. LNS offers some advantages over floating point, however it's performance degrades significantly as you add more bits of precision.

LNS can be effective to around 24bits of precision, and then the hardware requirements for the LNS unit's adder/subtracter become too overwhelming. This is because multiplications and divisions are fast on LNS units (with minimal hardware) as just require an adder, however handling subtraction is much more difficult. The simplest (naive) methods of making an adder and subtractor involve using large ROM lookup tables. Fancier, more efficient units using smaller roms and small multipliers to help get better values (I don't remember all the details offhand). Sometimes they'll even trade precision for faster performance. This can result in chips with single cycle multiplies and divides, but multi-cycle additions and subtractions. For low precision calculations requiring many divides and multiplies LNS processors can often achieve the best performance. However for many applications an efficient LNS unit with sufficient precision just isn't practical.

Phil

Re:This is why you would choose...

[Anonymous Coward]

You forgot my favorite -- interval aritmetic. Keep track of the error bounds and allow testing to determine if the accumulated error exceeds acceptable limits. I believe at one point Sun was considering implementing this in hardware.

Quick Way to Check FPU

[reporter]

The article asks, "But do we ever stop to think what goes on inside that floating point unit and whether we can really trust it ?"

The second part of the question can be easily answered. Compile the computer program in two ways. First, set the compiler to not use the floating-point unit (FPU). Just generate the instructions for explicitly doing the floating-point computations in software. Run the compiled code and save the results.

Second, set the compiler to explicitly use the FPU. Generate FPU instructions to do the floating-point computations in hardware. Run the compiled code and save the results.

The results should be identical. If they are not identical, then either the compiler has a (software) bug or the FPU has a (hardware) bug. If you are using GCC without optimization, then the FPU probably has a hardware bug. GCC is quite reliable when it is used without any optimization.

Bah. Author doesn't understand arithmetic.

[swillden]

The author goes on and on about how floating point numbers are inaccurate, and unable to precisely represent represent real values, like this is something new, or even something different from the number approximations we normally use.

The reason the examples the author cites can't be represented precisely is that floating point numbers are ultimately represented as base-2 fractions, and there are a bunch of finite-length base-10 fractions that don't have a non-repeating base-2 representation. Guess what? We have *exactly* the same problem with the base-10 fractions that everyone uses all the time. Show me how you write 1/3 as a decimal!

The problem isn't that floating point numbers are inherently problematic, the problem is that we typically use them by converting base-10 numbers to them, doing a bunch of calculations and then converting them back to base 10. Floating point rounding isn't an unsolved problem -- floating point rounding works perfectly, and always has. It's just that the approximations you get when you round in base 2 don't match the approximations you get when you round in base 10.

Bottom line: If you care about getting the same results you'd get in base 10, do your work in base 10. This is why financial applications should not use floating point numbers.

Not really CS101...

[Brian_Ellenberger]

I wouldn't call it CS101. In CS101 you learn, of course, that computers are finite machines and can't hold infinite values exactly (ex PI). Going into the precision detail would require a course in Numerical Analysis. Since you know there will always be some error, one of the components of Numerical Analysis is figuring out what the error will be. From that you can determine what error threshhold is acceptable and perform the calculations.

Must read floating-point articles

[emarkp]

What every computer scientist should know about floating point numbers (HTML, PDF).

and

When bad things happen to good numbers (as well as Becker's other floating-point columns on that same page)

Re:Must read floating-point articles

[OnanTheBarbarian]

The first article ("What every computer scientist should know...") is completely a must-read. Mod the parent up. Read the article. It's the sort of thing that I wish every undergraduate CS major was forced to chow down on at some point in fourth year...

Re:Bah. Author doesn't understand arithmetic.

[aXis100]

Or more importantly, do you math in a system where the level of precision (number of significant digits) is far greater than the answers you require.

average joe

[john_uy]

pardon my ignorance but why does the problem exist today? can't it be fixed? what is the actual effect to us (since in the forum, the examples given in the article are false)? (links will be helpful.)

when i use my calculator, it doesn't give rounded off numbers. i suspect lots of programs will have problems with rounding off but i don't seem to notice it. is it that insignificant?

Re:average joe

[Anonymous Coward]

If you think your calculator doesn't give rounded off numbers, I hope you're not working in science or engineering.

Re:average joe

[Anonymous Coward]

pardon my ignorance but why does the problem exist today? can't it be fixed?

The problem exists today, and cannot be fixed, because it is a fundamental problem, not one that is a bug or anything like that. If you are going to store a number by any variation on the technique of writing down the digits, you won't be able to represent certain numbers precisely.

when i use my calculator, it doesn't give rounded off numbers.

Oh, but it does. When you ask your calculator what 1 / 3 is, it tells you it's .33333, for some particular, fixed, and finite number of threes. But the real answer is an infinite number of threes. So it is in fact rounding.

is it that insignificant?

Well, kinda, yeah. Can you think of any applications for which 10 digits of precision isn't enough? If you can measure something to ten digits of precision, and you want to make something a mile long, you have enough precision so that the variation won't be visible to the naked eye. An 80 bit double gives something like 18 digits of precision.

Re:average joe

[zCyl]

when i use my calculator, it doesn't give rounded off numbers.

What does your calculator give for 1 divided by 1.7?

Re:average joe

[cynical kane]

If he's using a good one, most likely 1/1.7 or 10/17.

Re:average joe

[dcollins]

"when i use my calculator, it doesn't give rounded off numbers."

Not true.

In the math class I teach, I do the following: have everyone take a calculator and do "2/3".
Half of the calculators say this: "0.666666666" (rounded down).
Half of the calculators say this: "0.666666667" (rounded up).

In truth, an exact answer requires an infinite sequence of "6"'s. The calculator (or any computer) must decide whether to round up or down to fit it into its display space (or memory). You always have some round-off error -- and the more calculations you do, the more the round-off error builds up and up and up....

Re:average joe

[john_uy]

but when you multiply the answer by 1.7, it goes back to 1. well from my understanding of the problem, if you do multiply it back to 1.7, then you will get a different answer because of the rounding off errors. isn't the rounding off suppose to happen when you are at the last digit of great decimal places compared to the one discussed in the article with error in the storage? i mean trying the 59 + 12.5% yields the correct answer. the calculator does not display the errors. is it a problem with how i understand the problem?

Re:average joe

[john_uy]

yes, i agree with that. sorry for the statement. but following rounding off rules, the last digit should be 7 (as we humans would have done it.) but my question now comes back to the example given in the article that when 0.37 is stored then retrieved, the calculator returns the same value. it doesn't give me 0.370000004 or any other value than 0.37. is there something wrong with my understanding of the problem?

Re:average joe

[vadim_t]

Your calculator could be internally using more precision than it can display. If you try that division several times, then multiply back eventually you'll get something quite different than what you started from. Only needs enough iterations.

Re:average joe

[TheThiefMaster]

My calculator always stored 12 digits of precision even though it could only display 10. So 10/3 = 3.333333333 on screen but 10/3 - 3.333333333 = 3.3 e-10, not 0. This is also why 2/3 would show on-screen as 0.666666667, because it was actually rounding 0.66666666666 (maybe an extra 6 on that, can't remember if it treated the 0 as a digit of precision). Any calculator which ends 2/3 with a 6 on-screen can't be very good in my opinion.

Re:average joe

[k8to]

The answer, which is explicitly given in the referenced article by the article (two clicks, not one), is that commercial calculators operate with three digits of precision greater than those that they display, so that for operations which are available on the calculator, the imprecision is hidden. Typically calculators will display ten digits, but calculate using 13.

Re:average joe

[azipsun]

It is possible that your calculator uses decimal numbers internally and so isn't subject to the same rounding problems. (There are still rounding problems, just different ones.) My old HP calculator did this. If I recall correctly it stored 14 decimal digits internally (plus a 2 digit exponent) but only displayed 12 digits. I had a lot of fun playing around with it to figure out what it was doing internally.

Re:average joe

[Just Some Guy]

yes, i agree with that. sorry for the statement. but following rounding off rules, the last digit should be 7 (as we humans would have done it.)

By "we humans", you mean "people who use naive methods" (but excluding statisticians, bankers, engineers, etc.). Both "6" and "7" are perfectly correct, depending on which (of several) rounding algorithms in use.

but my question now comes back to the example given in the article that when 0.37 is stored then retrieved, the calculator returns the same value. it doesn't give me 0.370000004 or any other value than 0.37. is there something wrong with my understanding of the problem?

Yep. 0.370000004 is really close to 0.37, and your calculator can detect this. Therefore, it assumes that you really want to see 0.37. The problem is that the "fix" only affects the display and not the internal representation.

Re:average joe

[zCyl]

but when you multiply the answer by 1.7, it goes back to 1. well from my understanding of the problem, if you do multiply it back to 1.7, then you will get a different answer because of the rounding off errors.

When you divide by 1.7, most calculators will round the answer and store it to a certain precision. When you multiply that answer by 1.7 again, it rounds a second time, but it just so happens to get 1 as the result of that rounding. Try this instead:

1/1.7
+ 1000000
- 1000000
* 1.7

Most calculators will give you an answer less than 1, yet you can clearly see by hand that the answer should be exactly 1.

Why I only use decimal values

[eliot1785]

This is why I use DECIMAL and not FLOAT in MySQL. Problem solved. I'm not a big fan of floats, the extreme precision that they seem to have is mostly an illusion.

Re:Why I only use decimal values

[Fordiman]

Dunno why that was modded funny. It's somewhat true.

The potential error in any float is 1/(2^N) where N is the number of bits used to store the significant digits (called the mantissa)... just like the potential error in a written decimal number is 1/(10^N).

So? Well, for stuff where you need standard (N=3) float-error, use N=10 for binary. You won't find this, mind you.

Just for reference:
IEEE 754 (standard floating point numbers) in 32-bit uses 23 bits for its mantissa, and 8 bits as its exponent. Maximum static error in storage: 1/8388608
in 64-bit, it uses 52 bits for the mantissa and 11 for the exponent. Maximum storage error: 1/4.5 Quadrillion
Note that 754 uses a 'hidden' bit, being the unnecessary 1 at the start of the mantissa (in binary, since the number needs to be aligned to the first nonzero, and the only nonzeron in binary is 1, you don't need to store the first bit of the mantissa. Still, motorola 80 bit numbers do bother to store it)

Re:Why I only use decimal values

[eliot1785]

Yeah - my post wasn't intended as a joke. Thanks for the explanation too.

The comment about the illusion was basically in reference to the fact that FLOAT and DOUBLE values are often stored and displayed with more decimal numbers than are actually accurate. It would be better if they could somehow self-check for precision and only store the remaining decimals that are accurate. We can dream, can't we?

Re:Why I only use decimal values

[flupps]

Up until MySQL 5.0 calculations with DECIMALs were still done as DOUBLEs, so you could get unexpected results.

Slight clarification

[The Cisco Kid]

'Floating point numbers'
as opposed to
'Computer implementation of the storage and manipulation of floating point numbers'

Only the latter might be suspect, depending on the implementation.

Whatever happened to what used to be known as 'scientific notation' for what are also called 'real numbers'? Eg, you store the mantissa (eg "37") and the exponent (eg -2) and there is no approximation involved, although the mantissa might have a set maximum length, so you might have trouble storing, for example 1.000000000000000000000001 if the mantissa had a maximum length of ten.

Re:Slight clarification

[TheThiefMaster]

Um, that IS how computer floats are stored, just with a power-2 (binary) exponent instead of decimal. With a limit of 23 bits on the matissa iirc for a 32-bit float. Maybe an 8-bit exponent and 1 "sign bit", if memory serves.

Re:Slight clarification

[The Cisco Kid]

Ah ok, so the problem is 'the use of binary floating point numbers to represent decimal floating point numbers'. But still doesnt explain why .37 isnt .37 - "37" is fairly easily accurately repesented in binary. As is "-2".

Re:Slight clarification

[Anonymous Coward]

That doesn't work because the exponent is also done in binary. So it isn't -2 you would have to represent, it's -4 (1/16). And you'd have to contort 37 to fit this new exponentiation, and therein lies the problem - 0bx1. * 2^-4 != 0.37 decimal.

Re:Slight clarification

[TheThiefMaster]

Basicly, the problem is that it doesn't store the equivalent of 37x10^-2 for .37 (integer and power), more like 0.37x10^0 (fraction and power). And while 37 is easily representable in binary, the fraction 0.37 comes out as approximately: 0b.01011110101110000101000101 (to 26 binary places), or 0.36999996006488800048828125 in decimal. I think they do it this way so that they lose the smallest-value bits when the number is too large for the mantissa, instead of the largest-value ones.

A good example of the evils of math.

[bigmaddog]

If we think back to the good old days of the first Gulf War and all that, we might remember the Patriot missile and what a dismal failure that was. Part of the problem there was that the missile's clock values were such that they would not convert to base 2 (and hence to float) accurately and so the tracking was off and lots of expensive misses happened. If you recall, lots of US soldiers died when a Scud that theoretically ought to have been shot down hit their barracks.

As usual, it's not just one thing that screws everything up, not even in the narrow confines of the Patriot's software problem. Here's a short write-up on that math/software part of it. There were other issues with the Patriot but that'd be blatant off-topic flamebait. ;)

Re:A good example of the evils of math.

[codegen]

Part of the problem there was that the missile's clock values were such that they would not convert to base 2 (and hence to float) accurately and so the tracking was off

Actually the problem was that they used a float to store the system time (time since power on) in the ground radar unit. It allowed the clock to be used in calculations without a conversion. A float will store an integer just fine (and accurately) until the number gets too large and then the units part drops off the bottom of the precision and the increment operator no longer makes any sense. This was a design decision that made sense for the role for which the missle platform was originally designed. The patriot was originally designed to be used in the European Theater (if the cold war ever turned hot) and as such would never remain in one location for more than a very few days.The clock is reset everytime they move the battery (they power off the ground tracking radar when they move). The use in the gulf war was in a strategic role (not tactical) which kept them continuously operating in a single location for long periods of time, and the shortcut they used came back to haunt them (as usual). If they had reset the system every few days, the problem would not have occured.

Re:A good example of the evils of math.

[Fulcrum of Evil]

Part of the problem there was that the missile's clock values were such that they would not convert to base 2 (and hence to float) accurately and so the tracking was off and lots of expensive misses happened.

That wasn't the problem. The Patriot missle thing was rated for 48 hours between reboots, but they ran it for week at a time. If they had run it within specs, it'd be fine (or at least less bad).

Floating error

[Coppit]

I remember an old question from grad school: Why might you add a bunch of floating point numbers starting with the smallest? The answer is because floating point decimal accuracy goes down the larger the characteristic (non-decimal) is, so add the small numbers to get a larger characteristic before you add the larger numbers in. If you add the big numbers first, adding the small numbers might not change the intermediate sum. Of course, real-world floating point error in numerical algorithms is much more subtle. On the other hand, software engineering errors are often not subtle at all, so maybe things balance out. :)

Re:Floating error

[gnasher719]

'' I remember an old question from grad school: Why might you add a bunch of floating point numbers starting with the smallest? ''

There are to ways to get higher precision:

1. Instead of adding the numbers starting with the smallest, you continuously add the two smallest numbers, then put the result back into the list of numbers to be added. For example if you add 2^20 numbers, all around 1, you'll have 2^19 sums around 2, 2^18 sums around 4, 2^17 sums around 8 etc. The average result is only 20, therefore the average rounding error is quite small. By adding all numbers sequentially, you would on the average get a result of 2^19, so much higher rounding error.

2. Implement double precision addition: If x >= y >= 0, and you calculate s = x + y, then you get the exact error by calculating (s - x) - y if all operations are performed with the same precision. So all you need to do is add up the values and add up the rounding errors separately. For best results, combine both methods.

Gnu Multiple Precision

[kybred]

Is GMP similar to that? I used it to approximate the Poisson function for BER calculations. Pretty easy to use.

Comp Sci 101

[syousef]

Welcome to a very poor article on what's been taught in early Comp Sci for many many years.

Any serious developer of business software knows all about this and avoids floating point at all cost for financial calculations. Scientists however do use them carefully since the math they do is usually much more performance (speed) sensitive and the calculations are a little more complex than what tends to be done on the business side (ie _most_ business calcs are relatively simple).

Re:Comp Sci 101

[Todd Knarr]

I think it's simpler: financial calculations require a certain number of decimal places of precision, while scientific calculations tend to require a certain number of significant digits of precision. Floating-point numbers provide a known number of significant digits of precision, but depending on the exponent that may not provide the 2 decimal places of precision needed to represent a financial amount (in US currency at least, other countries may have different requirements).

Re:Comp Sci 101

[Anonymous Coward]

I'll make it even simpler:

Financial calculations are about counting units of currency. Anything that involves counting should be done with integers (or some other exact precision number system, but these pretty much all boil down to integers in theoretical terms), whether you're working with dollars and cents at a bank, or boxes of books at Amazon.com.

Scientific calculations are about measurements. Measurements are never precise, because we don't have infinitely precise measuring equipment. Therefore, exact arithmetic is pointless, because we need to quantify the error anyway.

That's not to say that you can just use floating point numbers in scientific calculations and all the issues magically go away. (Although IEEE 754 was a big step towards making things a lot easier.) For example, you still have problems adding very small numbers to very large numbers, and the like, so scientific programmers still have plenty of headaches to deal with. And there are probably certain applications that can't make do with hardware-supported types. But scientific programmers don't need to abandon floating point, like financial programmers do. Floating point was basically designed with scientific computing in mind, not business computing.

Sun was doing some interesting work on supercomputers that natively supported interval-based arithmetic (not sure what the status of that is), where the hardware kept track of the error in its calculations as it performs them. That would be even more ideal for scientific computing, because it alleviates the work of keeping track of how much error has accumulated in your own code.

Re:Comp Sci 101

[Todd Knarr]

Except that financial calculations don't count units of currency. Think about interest calculations, for example, that do care about fractions of a cent (at least in the ledger, although the numbers may be rounded to the nearest cent for display/printing purposes).

Re:Comp Sci 101

[Anonymous Coward]

when can .02 of a cent + .02 of a cent != .04 of a cent? when you represent them as floating point numbers. there are defined types already for decimal numbers (ie. XXXXXX.YYYYYY with practically unlimited prescision on either side of the decimal place) but there seems to be a large number of programmers who fail to make use of them or even know they exist. yeah they use a little extra memory, but this is financial calculations were talking about, they need to be exact.

Re:Comp Sci 101

[Anonymous Coward]

Ah, but that raises the subtle question of what you're counting, exactly. I was thinking about discussing interest calculations, but I figured it'd be a distracting aside to the basic point, which is that financial calculations are basically an accounting operation.

Anyway, you obviously can't have unlimited precision for money, neither in practical nor theoretical terms (making the reasonable assumption that all computers have finite memory). Thus there'll always be a cut-off point, and once you've got essentially a fixed-point representation, you're back to integers again, and counting units of currency. (I never stated that those units had to be the physical dollar and cent ones, although that's the easiest casual mental model; 1/10000 of a dollar or whatever would probably be a good choice for USD.)

Interest calculations may use multiplication to derive the amount, but ultimately however much interest you earn has to involve rounding rules, which are usually carefully specified in financial regulations, and then tossing the appropriate number of virtual coins into the account. Otherwise, you just end up with the same problem you had with floating point again, with money possibly becoming an uncountable real value. And you never want money to not be countable (in the mathematical sense), at least if you want to stay in business and out of jail.

Hmm

[Anonymous Coward]

I found this out years ago, and took it so far as to try to find a solution to the problem. I took it on as part of my senior thesis in college and worked to develop a way to, essentially, create a class that stored numbers using a numerator and denominator which could be of invariable size (think BigInteger numerator, BigInteger denominator, but using C++).

The drawbacks include that it is somewhat complex, most especially with the division (and somewhat, though to a lesser degree, multiplication), as well that it is not as efficient as there is not as much hardware support (you don't have the floating-point hardware support, since you're operating on multiple integers instead).

The true fallback is that only a fixed quantity of numbers can be finitely represented; those that cannot are forced to a fixed memory-width (say, 32, 64, or 80-bits, for example). Due to this, there is guaranteed an inaccuracy in the storage (forced rounding/truncation) when the number is not finitely represented.

Lightweight article, but some heavy consequences

[whit3]

I was taken with the comment "scientists can be fussy"; we need a
nap, I guess?

          Seriously, guard bits and high-precision accumulators and addition
algorithms that add the small numbers first (so the roundoff error in the
big numbers doesn't unduly affect the result) are all good ways to treat
roundoff errors. The old VAX/VMS math function libraries were available
with single, double, H_floating, and G_floating just in case you needed
many-digit exponents and really LONG mantissas.

          What this article seems to suggest, though, is DECIMAL arithmetic (shades of
COBOL!) as a solution. It is to laugh. Decimal arithmetic manipulation is
familiar from childhood, but has no other virtue. Arrays of 'values' are
containers of variable-length records, you gotta traverse a tree to
find an element (or index tables, or worse, do a linear search); Time
to complete an operation is dependent on the data values. There are
about 70 functions on numbers in the FORTRAN math library; does anyone
want to rewrite them for decimal arithmetic? What kind of precision
'improvement' do you expect in the case of functions like SIN? How
would you even specify a precision goal for such things?

        And few if any scientists need more precision than double (there were
those guys in Hans Dehmelt's group, at U. of WA, that did a fourteen-digit
measurement... but they would have got it right even if they had to
use abacuses...)

          A more interesting point is on the Fourier transform; there's a theorem
(Parseval's theorem, if you must know) that says a bit of error (noise) added
to a data set will become, after Fourier transforming that data set, the exact
SAME amplitude of noise in the output data. That means that the Fourier
transform doesn't reduce the signal/noise ratio of the input data. I often
have wished that other mathematical and program procedures had the
same property. They don't (and this has been known since Lagrange found
the problem in orbit calculations). And it doesn't matter whether the roundoff
is perfect, because ALL data starts with some noise. And it can never
get better.

At least Intel is trying...and it's not CISC!

[Riding Spinners]

Quite simply, Intel no longer uses CISC. Sure, the instruction set is CISC, but it's all microcode reduced to RISC instructions underneath the hood (which was done way back with the Pentium II and may have partially been implemented on the original Pentium). MMX has been dead for a while, replaced by SIMD and SIMD2, which can actually run in parallel to the floating point unit and no longer requires a context switch. Seriously though, outside of the math world, you probably don't need either unless you're doing software rendering of graphics -- the original reason for MMX was to speed up processing of games and video effects in software and this work is now pretty much entirely handled by the GPU.

C'mon, at least Intel is trying. We can't divide 1 by 3 with our base-10 system and our society has yet to crumble. If you want more precision, just use more bits. I'm sure you can figure it out -- after all, you're better than Intel!

Old news, but an unsolved problem

[Opportunist]

And I'm not sure if it can be solved altogether. When you spend a little time meditating over the IEEE 754, you notice a few flaws. The first and most obvious is, of course, that, no matter how precise you want to make it, somewhere there's a cutoff. And, especially when you multiply with floats, that error grows as well. But there's another problem. Two actually.

The first one is the one mentioned in the article, and something everyone who didn't sleep through his IT classes should know: Computers calculate binary, and converting floats from binary to decimal isn't possible without error. There is no way to represent 0.37 in binary, in IEEE754. No matter how many bits you spend on the mantissa. Now, you can argue that, if you make it "big enough", it doesn't matter anymore since it's well within the error margin and when you round it to, say, 5 after decimal, the error vanishes. True. But when you start calculating, when you multiply or, worse, exponentiate, the error grows in big leaps.

Another, less obvious, problem is hidden underneath the way the IEEE754 works: Your error grows as your numbers grow. This might seem obvious, but it is interesting how many people overlook this flaw and problem in everyday life. Since according to the IEEE754 standard, real numbers are stored as exponent and mantissa, if you're dealing with BIG numbers, a fair deal of your mantissa is spent on the "pre-comma" part of your number, so you're losing precision. You can't reliably say that "a double is good for 5 behind dot, no matter what", you have to take into account how many of those precious mantissa bits are spent before you even get to ponder what's left for your precision.

This isn't so much a problem of processors. It's a problem of people understanding how their processors work.

Re:Old news, but an unsolved problem

[ponos]

Another, less obvious, problem is hidden underneath the way the IEEE754 works: Your error grows as your numbers grow. This might seem obvious, but it is interesting how many people overlook this flaw and problem in everyday life. Since according to the IEEE754 standard, real numbers are stored as exponent and mantissa, if you're dealing with BIG numbers, a fair deal of your mantissa is spent on the "pre-comma" part of your number, so you're losing precision.

This is not entirely accurate. The length of the mantissa (and the exponent) is constant for both doubles and floats. Furthermore, the point of using an exponent is so that there is no difference whether you calculate 2x10^9 * 2x10^9 or 2*2 or 0.0002*0.0002. In all these cases the mantissa is the same (the example is in decimal, but you get the point). You always get N bits of mantissa whether your number is small or big.

In my opinion, the IEEE754 float types are really good provided that (a) you use algorithms that are numerically stable and (b) you treat them as floats and not as integers. A useful addition to C99 has been the inclusion of isless(), isunordered() isgreater() etc macros for this purpose. With sufficient care a bignum library is rarely needed.

P.

Re:Old news, but an unsolved problem

[Opportunist]

The mantissa is the same length (of course). But with large numbers (read: large exponents) you get very few reliable positions after the decimal point. I've had my share of headaches in statistics with that problem...

Re:Old news, but an unsolved problem

[flyboyfred]

Perhaps the problem is expecting more significant figures than your floating point representation can deliver. You can't really expect to get more significant figures out than you put in anyway.

Fred
8v)

The problem is using floating point improperly

[Myria]

GIMPS looks for Mersenne primes. This is clearly an exact integer operation. However, for speed, they use Fast Fourier Transforms to do the big squaring operation with floating point. Obviously, they need an exact result.

The trick is to carefully calculate exactly how much error each operation can generate. It is possible to know exactly how many bits of your result contain valid information. If you need more accuracy, you can split it into multiple operations. As long as the final accumulated error in their result is less than .5, you have the integer answer they need. Note that it's basically impossible to do this without using assembly language, because the order of operations and subexpression elimination definitely matter.

Another interesting problem occurs with floating point results. You cannot expect the complete answer to be exactly identical on all machines. Even on the same machine, compiler settings affect the answer: x87 differs significantly from SSE. If you are doing something that needs bitwise identical results on all machines, you need to either implement it with integer math, or do what GIMPS does and do error tracking.

Melissa

Re:The problem is using floating point improperly

[ponos]

This is clearly an exact integer operation. However, for speed, they use Fast Fourier Transforms to do the big squaring operation with floating point. Obviously, they need an exact result.

All serious bignum libraries use (or should use!) the FFT to multiply very big numbers. This has been studied extensively (see Knuth The Art of Programming vol 2, for example) and is the fastest way to multiply. The general idea is that after the transform you can multiply in O(N), which is much faster than the naive O(N*N) one would expect from a simplistic digit-by-digit approach.

P.

Goldberg on Floating Point

[haemish]

The classic paper is David Goldberg's "Everything a Computer Scientist needs to know about Floating Point", online at http://docs.sun.com/source/806-3568/ncg_goldberg.h tml

Well, *I* didn't know ...

[Anonymous Coward]

Show of hands: Who did not already understand that floats are approximations?

One hand raised as requested ...

Just use integers.

[Anonymous Coward]

I just use integers.

Amusing Float Story

[Bob9113]

True Story:

Business: We need to be able to store thirds, eighths, and hundredths of a unit in the same field. Then we need to add them up, and it has to be exact.
Developer: OK, one second... cool. We'll store the number of 600ths.
Business: 600ths? What is a 600th? Just use 100ths.
Developer: You said you need thirds, right?
Business: Yeah, use .33.
Developer: You said it needs to be exact, right?
Business: Yes.
Developer: 3 * .33 is .99.
Business: Oh, yeah. Just round that.
Developer: But that's not exact, and the error can be cumulative.
Business: It's close enough.
Developer: You know, we could store 600ths for accuracy, and display 100ths for user-friendliness. Would that help?
Business: Just use 100ths.
Developer: Right. Thanks. <bangs head on desk>

The field is stored as hundredths.

I know that the problem the article is talking about is the 1.0+1.0=2.000001 problem - but this story is still funny.

Re:Amusing Float Story

[Anonymous Coward]

So... those guys are losing one percent of their money in their financial calculations whenever they try to use thirds? Is the software already in production use? Have they noticed anything weird about that yet?

Re:Amusing Float Story

[Bob9113]

So... those guys are losing one percent of their money in their financial calculations whenever they try to use thirds?

It's actually not something closely tied to the finances.

Re:Amusing Float Story

[Just Some Guy]

No offense, but it's your fault for telling them what you were going to do. There are times - and this was one of them - when your job is to abstract the messy details away from the powers that be. All they need to know is that the end result is correct.

I for one...

[Traegorn]

I for one welcome our floating point overlords.

rounding algorithms

[trb]

If you're interested in rounding (and who isn't?) you might want to read An introduction to different rounding algorithms.

Re:Bah. Author doesn't understand arithmetic.

[slamb]

The problem isn't that floating point numbers are inherently problematic, the problem is that we typically use them by converting base-10 numbers to them, doing a bunch of calculations and then converting them back to base 10. [...] Bottom line: If you care about getting the same results you'd get in base 10, do your work in base 10. This is why financial applications should not use floating point numbers.

Base-10 is one problem; floating-point is another. If you are certain that base-10 floating point is what you want for financial calculations, use IEE 754r floating-point numbers when it's finalized. But floating point numbers, by design, only maintain a certain number of significant figures. In many financial calculations (say, current bank balances; possibly not long-term stock market estimates), you always want precision down to the nearest cent or tenth of a cent, regardless of how big the number is. That's a job for fixed-point, base-10 arithmetic. (Luckily, libraries for this exist, and IEE 754r also introduces standardized fixed-point base-10 numbers.)

You might be able to get away with floating-point if the mantissa's wide enough for your largest number[*], but why mess around? Fixed-precision arithmetic is easier to understand, so it's the right tool for the job. Save floating-point numbers for the people who need them, who put in the effort to tweak formulas to minimize errors like catastrophic cancellation, and who use them appropriately:

• knowingly accept an unknown precision and accuracy (might be okay for an OpenGL-based game)
• use interval arithmetic to flag problems (say, scientific calculations that can be tweaked and rerun if a problem is revealed)
• actually prove that they're within defined error bounds (the only way for real-time critical applications, like life-sustaining systems or ones that affect a lot of money)

[*] - Maybe; I don't remember all the properties of IEE 754 floating-point numbers off the top of my head, which is exactly my point.

Huhu, what?

[stonecypher]

struct fraction { public: long long int numerator; long long int denominator; }; // covers anything in that article

There's a reason some people shouldn't be in industrial computing. Problems like this are trivially easy to solve, and have in fact long since been solved by infinite precision math libraries like GMP. There is a common datatype called BCD (binary coded decimal) which handles these problems by just counting 0..9 in each hex digit and then ignoring the other six values, which solves this at arbitrary precision; the first time I saw that was in Paradox in 1988, but I have references to it in books from the late 1960s.

This is a non-story, documenting one author's infamiliarity with basic practices. Nothing to see here. Move along please.

Re:Bah. Author doesn't understand arithmetic.

[swillden]

Or more importantly, do you math in a system where the level of precision (number of significant digits) is far greater than the answers you require.

That is necessary but not sufficient to prevent the appearance of "weird" results.

Applications that handle money at the retail level, for example, only require three or four decimal places of precision (in the US, at least), so you might think floats are perfectly adequate, but in fact they can produce results that appear incorrect.

Early in my career I worked on a point-of-sale app that had this problem. The previous developer had tried to fix the problem by switching from floats to doubles, but of course that didn't work. Precision wasn't the problem, differing expectations for rounding were. Since changing to a fixed-point representation wasn't possible, I just had to be very careful about making sure that I never rounded early, keeping all possible precision to the end, and then had to write a rounding routine that papered over the discrepancies --not all that hard to do, actually, as long as you have enough precision to start with, and as long as you understand what's going on.

DECMIAL BASED COMPUTERS NOW~! ; )

[plasmacutter]

That's right.. I want to see decimal based computers!

not because it's more efficient but because then I don't have to do stupid binary and hex conversion anymore!

the world should bow to me and my lazy american ideal~!

Re:DECMIAL BASED COMPUTERS NOW~! ; )

[TheFamousEccles]

Decimal based computers are obsolete. I used one, an IBM 650, in the early 1960s. It was installed in 1958.

Changing Readership

[TiggertheMad]

Show of hands: Who did not already understand that floats are approximations?

Sorry to say it, but /.'s readership has really slipped in educational level since the early days. There are a lot of non-coders reading it these days, so yeah, I bet there were a lot who didn't know that...

Re:Changing Readership

[Capt'n Hector]

What a snob you are. There are many people who are more educated than you but who cannot tell you what a float is. Not everyone is a computer programmer. Not even on slashdot.

Re:Bah. Author doesn't understand arithmetic.

[swillden]

But floating point numbers, by design, only maintain a certain number of significant figures. In many financial calculations (say, current bank balances; possibly not long-term stock market estimates), you always want precision down to the nearest cent or tenth of a cent, regardless of how big the number is.

In the financial apps I worked on, the mantissa size was never an issue. You have to deal with some very large balances before you start losing stuff off the end of even a 32-bit float's mantissa. I don't think there are any balances in US dollars that would run into trouble with 64-bit doubles. The problems that do arise in financial apps with typical base-2 floating point implementations are caused by the impossibility of precisely representing many base-10 fractions in base 2.

That said, you're right that fixed-point arithmetic is the right thing to use. You still have to worry about overflows, but that's a much less complex problem to manage and avoid.

another example

[Anonymous Coward]

the patriot missles in the gulf war woulnt hit there targt in some cases because thier code told them to count time in 1/10 second intervals, which is undefined in base 2 (its a repeting series, 1001001001001...). this lead to them being less acurate after being on for a while

decimal exponent floating point

[Joseph_Daniel_Zukige]

The numerical value in a long and the power of ten in another?

That's just floating point revisited, with 64 bits of significance (less if you mean to interpret the long as binary coded decimal).

Some floating point packages give 64 bits of significance in a long double, although it's not required by the C standard IIRC. But 64 bits only give about 18 or 19 decimal digits of significance, I forget which (but exactly 16 digits if BCD).

Changing the exponent to decimal only makes the range a bit wider. (Waters down the coverage available by not-a-numbers, too, but you probably don't mind that?)

What if the significand (your numerical value) is binary coded decimal? Then you have the advantage that all values map directly to the way we write numbers down by hand. It's a big advantage, because we no longer get surprised by things like 0.2 decimal being stored inexact. But we still have rounding errors when dividing by numbers that are multiples of any primes other than 2 and 5. (And there are lots of those.)

A way to represent repeating fraction strings (such as when you write 0.9 with a bar over the nine to show that it is the result of something like a third times 3) would help for rational numbers. But taking advantage of such a representation is not as easy as one might hope, invoking rounding issues of another sort. (What's the difference between zero point repeating nine and 1.0? How does the computer know when to resolve and how to resolve the cases that aren't as visible?) And you still leave rounding unresolved for irrational numbers such as pi and e and and multiples and fractions thereof.

(Marking the repeating end of a fraction is equivalent to keeping track of numbers as fractions, keeping both the numerator and denominator and only dividing when the result does not lose significance.)

Decimal strings have a very nice advantage, in that the visible surprises are fewer, and if you know you need 16 columns of accuracy, you can calculate the intermediates out to 32 digits of significance. But there are certain nasty surprises that tend to get swept under the rug in decimal arithmetic that binary helps resolve, so it's a kind of pick-your-poison problem, assuming you can choose between decimal strings and binary strings.

And that is really the best we can offer:

Fixed width integers for problems where we know the range doesn't exist the width of the integer.

Fixed point as a variation of fixed-width.

Fixed significance floating point for "easy" fractional problems where rounding is okay.

Arbitrary length numeric (decimal or binary) strings for the rest of the problems, remembering that we still have to deal with rounding.

Maybe sometime we'll figure out how to deal with repeating end elements, and be able to at least keep rational numbers truly accurate.

Some of the irrational numbers might be resolvable by a numbering system based on polynomial series, but I haven't seen much work on generally available libraries for those.

Just use BigDecimal in java

[Serveert]

It does what you expect. .1 = .1 with BD. (as opposed to .1000000000000000055511151231257827021181583404541 015625)

did you just call pi an infinite value?!?

[kevlarman]

...somewhere, a calculus teacher just had a heart attack from reading your comment. Pi may have an infinite number of digits in its decimal representation, but that does not make it infinite (rather, since it does not repeat, it is called a transendental(sp?) number).

Re:did you just call pi an infinite value?!?

[spiffyman]

It's Transcendental number.

Not trolling, just helping since you asked.

Re:did you just call pi an infinite value?!?

[sickofthisshit]

Pi's not repeating in its expansion is due to it being an irrational.

Transcendental means that it cannot be a root of any polynomial with rational coefficients. The square root of 2 does not repeat, but is the root of the polynomial x^2 - 2.

Re:did you just call pi an infinite value?!?

[fishbowl]

> since it does not repeat, it is called a transendental(sp?) number

Pi is transcendental, but that is not exactly the reason. It is transcendental because it cannot
be represented in any finite serious of algebraic or arithmetic operations. Many irrational numbers
are not transcendental.

floats are not "inaccurate"

[idlake]

Many people seem to think of floats as a kind of number that gives fuzzy results; that's b.s. Floating point numbers operate according to precise models. Those models may not fit your calcuations or needs, and one can argue that IEEE has standardized a Rube Goldberg-style floating point model, but none of that makes them inaccurate.

In particular, you can perform bit-accurate integer arithmetic with floating point numbers if you like.

Re:floats are not "inaccurate"

[TheFamousEccles]

> In particular, you can perform bit-accurate integer arithmetic with floating point numbers if you like.

No you can't. Integers stored in floats are usually normalized, i.e. stored as a mantissa between 0 & 1, and exponent.

Re:floats are not "inaccurate"

[idlake]

Integers stored in floats are usually normalized, i.e. stored as a mantissa between 0 & 1, and exponent.

Indeed they are. What does that have to do with anything? When you compute .11(2) * .1101(2) with a floating point unit, you get an exact result.

No you can't.

Yes, you can. Floating point numbers don't magically go fuzzy by themselves.

Yes he did.

[raehl]

Apparently the author of the article didn't read the stories in RISKS that he cited.

He just stored the causes of the bugs in floats, and they were unfortunately rounded to slightly different causes when he displayed them for the article.

Oooh! No wonder..

[robpoe]

Well, that explains everything.

Microsoft has a floating point bug in the software that tells us what year their new products will be released...

Now I understand.

Game on!

not really

[YesIAmAScript]

The number of people who really understand floats is less than 1% of the people who think they do.

Do you understand that

(A < B)

is not the same as

!(A >= B)

and that

((A + 1) == (A))

Can be true?

Every day, many people make the mistake of using floats when wat they really wanted was the ability just to represent large numbers. For example, in Mac OS X, the system uses doubles as representations of time. This is the worst idea I can think of. First of all, floats are imprecise and time is the thing that man can subdivide the most precisely. Secondly, if a Mac OS X machine is on long enough, time will cease to progress becuase of the 2nd statement above!

Plenty of people who thought they knew what they were doing have used floats in places where they are a bad idea. And it continues to today.

So I say no, Computer Science 101 doesn't seem to cover all you need to know about floats.

Re:not really

[morie]

No, I do not understand that, but I would like to learn why. Where can I find information?

Re:not really

[jrumney]

Secondly, if a Mac OS X machine is on long enough, time will cease to progress becuase of the 2nd statement above!

Oh shit! You mean in 58 million years my Mac will stop functioning?!!! Damn those stupid programmers, why didn't they think of that?

Re:not really

[abdulla]

I would like proof of that, it seems to me they use the standard unix time values, ie a signed 32bit integer for seconds and gettimeofday is the same as on other systems. TimeValue is also a signed 32bit integer, hmmm, do you have any proof that Mac OS X uses doubles for time?

Re:not really

[mike2R]

This Wikipedia page has good background information.

Re:not really

[Anonymous Brave Guy]

The first paper recommended for learning more about floating point arithmetic is usually Goldberg's famous What Every Computer Scientist Should Know About Floating-Point Arithmetic .

I can't remember whether the paper specifically discusses the failure of floating point arithmetic to obey the mathematical laws of arithmetic, but even if not, the background it provides is probably enough for you to understand the reasoning yourself.

Re:not really

[gnasher719]

You can use mach_absolute_time which returns time since the machine was started in 64 bit integer nanoseconds (derived from rdtsc or mftb/mftbu depending on the machine), that gives you time information for about 100 years (the 64 bit would be enough for 600 or 700 years, but rdtsc will overflow after about 100 years). The filesystem uses 64 bit integers with 48 bit for seconds, and 16 bit for fractions. That should last for about 2000 years.

Re:not really

[StrongAxe]

First of all, floats are imprecise

Actually, this is not totally true. A more accurate statement would be that floats can inaccurately respresent values that would otherwise not be representable.

I am not familiar with the floating point hardware used on Power PCs, but on intel processors, double-precision floating point numbers have 53 bits of precision. This means that they can totally accurately represent integers up to 53 bits. This should be enough to exactly compute values of 8 trillion dollars to the penny.

How about building a real number object?

[PostComment()]

Since we all know that computers work in discreet values and thus create approximations of select real numbers, why not take advantage of this and create a real number class? Yes, there would be a lot of overloads on the operators and perhaps we have to update the math.h library, but still, this seems to be the most accurate way. Only at display time, or printing does it need to perform some kind of binary conversion so it can be used with some given api, but at least the errors don't get drastically worse with many subsequent computations going against a float. This could be particularly useful in a financial institution where your inputs are gauranteed to be only fractions of 100th (at worse I am assuming). For example, we can implement a class that has two ints such as int numerator, int denominator... and from there we have to overload the operators and maybe create some kind of conversive function as well input/output functions. Well, what do you think? Here is an example... suppose that you have to deposit 33 cents... you would convert and store this into to the realnum obj as 33 num 100 denom. From there I think you can have pretty darn accurate calculations. Oh btw, make sure the user input was loaded as a string and have that parsed into the real num object. Just a thought. I might be wrong though

Re:How about building a real number object?

[ytm]

You propose rational not real numbers. It's been done before.

However creating a real number object is interesting thought excercise, considering how reals are constructed from rational numbers, like Cauchy sequences: http://en.wikipedia.org/wiki/Construction_of_real_ numbers#Explicit_constructions_of_models

Probably not practical.

Re:How about building a real number object?

[HeroreV]

OMG u iz so smort u blo mai mind u sexie jeanyus u. im sure nobudie evar thowt of such a smort idea b4. nun of the othur bilyuns of peepul R az kewl az u kawz thay kunt maek such smort ideaz

Solutions

[Mark_MF-WN]

There are lots of solutions out there. One good compromise in many situations is to store a range rather than a single value; either a min-max pair, or a median value with a precision. Every floating point operation that a computer can do has a predictable limit on the amount of error that it introduces; tracking this amount explicitly alongside your floats and doubles makes an awful lot of sense, and has a relatively small performance cost compared to solutions like decimal arithmetic and symbolic computation.

Approximation error undefined?

[Spazmania]

The article suggests that the approximation error is undefined: for any particular number if could be plus or minus the least precision binary digit. Is that correct? Doesn't the approximation error follow the same rounding rules as everything else, so if the next digit would be a 0 it rounds down but if it would be a 1 it rounds up?

Anyway, this problem is not unique to computers. You can see rounding error in plain decimal math:

1/18 * 18 = 18/18 = 1/1 = 1

1/18 repeats infinitely in decimal, so we choose an arbitary point at which to round, say 4 decimal places.

0.05555(etc) rounds to 0.0556.

0.0556 * 18 = 1.0008, not 1.0000

That seems obvious, so lets try it another way:

(1/18 * 9) + (1/90 * 45) = 9/18 + 45/90 = 45/90 + 45/90 = 90/90 = 1/1 = 1
1/18 = 0.05555(etc) which rounds to 0.0556
1/90 = 0.01111(etc) which rounds to 0.0111
(0.0556 * 9) + (0.0111 * 45) = 0.5004 + 0.4995 = 0.9999 (neither 1.0008 nor 1.0000)

As long as division is the most complex operation, the solution is not to convert the numbers to decimal in the first place. Maintain the number as a fraction until the very end.

Computation

[Mark_MF-WN]

Symbolic calculation would be impractical for highly iterated calculations, as you find in many financial and matrix formulae. The symbolic representations would simply become impractically long, and resolving them into actual numbers for presentation to Humans would have exactly the same issues as before.

Another true story

[Flyboy Connor]

I once wrote interest-calculation software for a bank. This was new software to replace their old stuff. Naturally, I stored the values in cents, not guilders/dollars/euros, to avoid rounding errors (which really have a big effect in interest calculations).

When I delivered my software, they compared my output to the output their old software produced. There were small differences. They asked me where these came from, and I traced them back to rounding errors in their old software. I showed them this by example, thinking that they would be happy that their new software did not have this problem.

Their response? "The new software should produce exactly the same numbers as the old software." "But the old numbers are WRONG!" "That does not matter, the new software should produce exactly the same numbers as the old software."

It is really hell to make good new software error-compatible with faulty old garbage.

Re:Another true story

[Bob9113]

Their response? "The new software should produce exactly the same numbers as the old software." "But the old numbers are WRONG!" "That does not matter, the new software should produce exactly the same numbers as the old software."

Laugh, cry. Had the exact same thing (though with advertising conversion rates, not interest) on a different project from the one I noted above. Spent a month on the analysis and statistics. Learned all about lognormal distributions. The answers were beautiful. <shrug>

Discrete vs Continuious

[Anonymous Coward]

Exactly. The same's true in MS Sql Server, Oracle, or in fact, *any* SQL database. .Net languages actually have a native Decimal type that is guarenteed to have full decimal fideality to six d.p. or something.

Floats are approprate when the value is a truely continuious one that cannot ever be precisely represented in a digital computer system. A classic example would be wave high computation simulations - the "true hight" of a wave being represented could be measured down increasingly better levels -- all the way to the subatomic level, there's no actual 'precisely right' definition. Thus, a float (or a double) is the correct data type. (Or an audio wave file - the actual 'real world' sound pressure is a continious value. CD players just approxmate it with 16 bit integers - and yes, there is a certain quantatisation error with that.)

But in finance, there is a "true" value - my bank account has, for example, two hundred dollars and fifty six cents - it is a completely discrete value. No matter how many times I measure it, it will be exactly the same.

Re:Discrete vs Continuious

[Anonymous Coward]

"...my bank account has, for example, two hundred dollars and fifty six cents - it is a completely discrete value. No matter how many times I measure it, it will be exactly the same."

Buddy, you oughta get your stash into an interest-paying account!

Just trying to help here...

Re:Discrete vs Continuious

[NewWorldDan]

But in finance, there is a "true" value - my bank account has, for example, two hundred dollars and fifty six cents - it is a completely discrete value. No matter how many times I measure it, it will be exactly the same.

All float numbers are discrete values as well. The "problem" is that they're in base 2 when most people are used to looking at numbers in base 10. Left of the decimal point, base2 and base10 convert on a 1 to 1 relationship. Right of the decimal point is where you have problems. You can convert a base2 decimal space is completely coverd by the base10 decimal space, but not the other way around. Thus the example of the linked article - .37 can not be represented in base2 (without a repeating decimal), but only aproximated. However, 1.0101b does convert to 1.3125 without loss.

Use Fractions

[RKBA]

"No, there's nothing you can do about it."

Sure there is, use fractions. For example, 1/3 is exact, whereas 0.3333... is not.
The Maplesoft "Maple" program symbolic math program does this, and only evaluates fractions if an explicit evaluation is called for (eg; by the "evalf()" function).

Re:Use Fractions

[betterunixthanunix]

Except that will still cause you to run into problems, unless you only need to deal with rational numbers. It will work for financial stuff, sure, but for video games and scientific computing, this is not an acceptable solution to the problem. Even Mathematica, which is also a symbolic program, can be tricked into erroneous output (try plotting the function F[x] = Sin[1/x]), because at some point the division will have to actually be performed.

Of course, if you are guaranteed that you will only be dealing with integers and rationals, you can get away with using remainders when you perform the actual division. In fact, this will also work for nth-root computations, although it won't be particularly useful except as a technique for expressing the degree of error.

Floating

[otherone]

Doesn't the word "float" kind of imply that it isn't as accurate as say a regular number? Last time I checked boats didn't have parking brakes.

Rounding errors...

[jozmala]

If you go for fraction of integer you will either have to round them or potentially spend infinite amount of ram.

Think about this, if you multiply a number with a n fractional bits, with a number with n fractional bits.
The end result has 2n fractional bits, or is rounded. Only escape is that if there multiplier gives zero:s in end result. But with lots of calculations you start either rounding things or there will be huge number of bits required to represent the value.

Re:Decimal Arithmetic - £sd

[cruachan]

More interesting than cents, when I first started in a commercial DP department, back in the mid-80s, we had a couple of old guys (well, in their 50's) who could remember writing code that had to use the old UK pre-decimal money system (the UK went decimal in 1971). Under that there was 12 pence to the shilling, and 20 shillings to the pound. They similarly converted all values to pence before starting calculations, then converted back to £sd when complete. All on a computer (a Honeywell I think) with less power than my mobile phone.

Holy cow!

[Kynde]

Floating point arithmetic on computers is not absolutely accurate? Not suitable for
financial solutions?

What next? Sloppy usage of pointers in C may lead to uncanny features?
And I though I knew a thing or two about programming.

Inappropriate expectations

[Archtech]

"But do we ever stop to think what goes on inside that floating point unit and whether we can really trust it?"

That's an ill-conditioned question. Of course we can trust the FPU - to do what it's designed and specified to do. If the programmer doesn't understand how the FPU works, that spells trouble, just like using any other complex machine without proper training.

The question reflects a serious social - not technical - problem that we are facing more and more. Namely, there are so many people who rely on computers but have no idea how they work, many of whom think of a computer as some kind of "brain" or even "god" rather than a complex machine with well-defined capabilities and limitations.

Stories like this recall the old DEC war story about the customer who complained that his VAX was giving wrong answers. It got escalated to galactic support before the customer revealed that his criterion for judging the answers "wrong" was that they differed from those given by his HP pocket calculator! (Never occurred to him that his own calculator could be "wrong", and the whole concept of differing levels of precision seemed to have eluded him).

but what shall we use instead?

[schweini]

i also only use the DECIMAL datatype in my databases, so i can safely ignore all of this, yet, if i remember correctly, this whole float-thing exists because it is more efficient and machine-friendly. Does anybody have any performance comparisons on large datasets comparing the various number-types, not only in the context of databases? aren't floats supposed to be very FPU-friendly? how are e.g. DECIMALs calculated? would it be better to store dinacial numbers as INT[decimalpoint]INT?

How about this?

[mlow82]

BigDecimal

Error diffusion is another way.

[DrYak]

On solution as you put, is to priority sort your operations.

Another solution, is the Kahan summation algorithm.
Wich, grosso-modo, keeps track of the error at each step, and injects it back at the next.
In your example, in each iteration, the algorithme notice that tha 1.0e1 is missing from the sum and carries it to the next addition. A few iterations later, the carry is big enough to be added to the result.

The advantages are : you don't need to first load all components in a tree, then itteratively sort them and process them all until you're done. In fact you can even use this algorithme in a streaming fashion, were you don't enven need to know how much value will come.

The disadvantages are : some compilers are able to guess that the carry "should mathematically be 0" (actually true in a perfect world with infinite precision numbers) and could "optimise" the code back to a plain normal sum function bypassing the algorithm (and won't subsequently use any other sum-correction algorithm).

Re:Error diffusion is another way.

[Eivind]

Sure. There's many ways of solving the problem, none of them very hard to grasp once you've done the fundamental task: which is to be aware of and understand the problem.

Lots of programmers though, are unaware of the finer details of floating-point numbers.

As evidenced by MS-Excel failing to give the correct answer, even when as we've now demonstrated, there's multiple, simple, correct algorithms for doing so.

It *is* surprising to do the equivalent of 1000 + (1+1+1 ...[10000 times] +1) and get 1000 as the answer. The answer *should* be on the order of 11000. Anything else is a bug.

Thus we can conclude that MS-Excel does not even manage to get its SUM() function correct. One of the simplest functions there can be on a set of floats.

(long) example

[caveman]

I wrote this article for our in-house programmers some time ago to illustrate just this problem...

Quantum mechanics on the floating-point stack

This article describes a potential pitfall for visual C 6.0 programmers when using floating point arithmetic. This does not occur with GCC, even on the same platform, because the (int) typecast is sufficiently different.

Why 'Quantum'? The third principle of quantum mechanics is "The act of observing something happening causes a change in the thing being observed." This holds true in the examples given in this article.

The problem stems from the way floating point numbers are handled by the hardware in the Intel-compatible floating point units.
Externally to the floating point unit, floating point values are stored in 32-bit (single) or 64-bit (double) values. However, internally, they are stored in an 80-bit format, as below:


single float: Sign <--8-bit-exponent--> <--23-bit-mantissa-->
double float: Sign <-11-bit-exponent--> <--52-bit-mantissa-->
x87 register: Sign <-15-bit-exponent--> <--64-bit-mantissa-->

Both the single and double precision floats also have an implied leading-1 on the mantissa which is not stored in the actual data, whereas the internal float does not.

The value -4.0 is stored in a double as (hex) 00 00 00 00 00 00 10 C0, when this is written in binary, in the byte order of the diagram above, this works out as
1 10000000001 00000000000000000000000000000000000000000000000000 000000
The exponent is biased, which means that it has a value added to it to provide for negative exponents. In double precision, that bias value is 1023. Expressed in binary, that is 01111111111, so the exponent's real value is 10000000001 - 01111111111 = 00000000010.
The mantissa has an implied leading 1, and the decimal point appears between that leading 1 and the rest of the mantissa, so the value above is negative (the sign bit is set) 1.0000000000... x 200000000010 = -1.0 x 2^2 = -4.0

So far, so good. However the problem lies in functions such as log10(), pow() and so forth that generate floating point results which suffer from accuracy problems. On the intel architecture, these accuracy problems only manifest themselves at the extreme end of the 80-bit floating point format, so for example log10(0.0001) returns -3.99999999999999997e+0000 in the 80-bit format. When this value is stored in a double, via a FST(P) (floating store (and pop)) instruction, the value is rounded to 64-bit accuracy, and results in the bit patten above.

If you copy this value to an integer, you will get the correct result, which is -4.

The error creeps in when you copy the value to an integer directly from the floating point stack, because the value on the floating point stack is still -3.99999999999999997e+0000, and the '=(int)' typecast always chops the decimal places off. The processor converts floating point to integer via a FIST(P) (floating integer store (and pop)) instruction, and the function which the compiler uses to do the cast sets the floating point control word to chop, rather than round, the result. This function, called __ftol is automatically called by the Visual C compiler to do the conversion. It is slow and cumbersome, but it does the job to the specification required. However, you can get different results, depending on when the function is called, because the compiler generates different code depending on how you use floating point results. In all of the following examples, the stack management code has been removed for clarity.

In the instance:
d = log10(0.0001);
i = (int)d;
the microsoft compiler generates the following code:
push 3F1A36E2h ; Push high 32-bits of 0.0001 (double) onto stack
push 0EB1C432Dh ; Push low 32-

Re:(long) example

[caveman]

Bugger! Missed 'preview' and pressed 'submit'.
A lot of the tabs got messed up.

I was going to add:

d = log10(0.0001);
i = (int)d;
printf("%d\n",i);
i = (int)d;
printf("%d\n",i);
...will generate different results at each printf call, confusing the novice programmer to the point of despair ;-)

Re:(long) example

[caveman]

Also due to the lack of proofreading/previewing, the 200000000010 should have had a ^ inserted, as in 1.0000000000... x 2^00000000010
Pity slash's allowed HTML does not include <SUP> tags..

Re:(long) example

[gnasher719]

'' In the instance:
d = log10(0.0001);
                i = (int)d;
the microsoft compiler generates the following code: ''

Doesn't really matter what code which compiler produced; the programmer should be shot on sight.

The floating-point number 0.0001 cannot possibly be equal to the real number 0.0001, it will necessarily be either a little bit smaller or a little bit larger.

d = log10 (0.0001) will set d to a value which may be coincidence be equal to 4.0, or may be slightly larger, or slightly smaller. Which one depends on the exact details of how the log10 function is implemented and the floating point format used, and it is in no way defined by the C language.

i = (int) d will therefore set i to -3 or -4, and which one is completely unspecified by the C language. An implementation that sets i to -3 is not wrong, it just exposes the stupidity of the programmer.

Re:(long) example

[caveman]

> it just exposes the stupidity of the programmer.

Indeed; The programmer may have printf("%d\n",(int)log10(0.0001)); and been suitably suprised.

The oddity here is that with the hardware using 80-bit, and the software 64-bit, the particular value generated is inconsistent if the apparently same operation is carried out on it twice. FIST generates -4; FST generates -4.000, FISTP generates -3 or -4 depending on the round/chop bit in the FPCW. The (microsoft) inconsistency is that the int = (int)double cast does not behave consistently, which will further confuse the hapless programmer.

My programming background is in bits, registers, and I/O, not doubles, hence I had to debug this particular instance for the programmer concerned. I'd have done it in ASM, and kept the whole thing in 80-bit, but that is why I don't do the mathematical stuff in the software, just the bit bashing.. ;-)

Not exactly...

[DrYak]

There's a system called Binary-coded decimal, which help a binary based system to handle base 10 numbers.

You store each digit of a base 10 number using a 4bit representation. So, in each nibble of a hex reprentation of a number, you get the actual base 10 number.
decimal 1234 = BCD 0x1234.
The advantages are that it is more easy to convert them back from BCD format to decimal to print them. The disadvantage are the increased complexity of circuitry needed to process them in a CPU (and the waste of storage space).

Re:Not exactly...

[Viol8]

Not all CPUs support BCD. Besides which even BCD uses binary as a storage method even
though it doesn't do base 2 calculations.

use doubles instead of floats

[steincastle]

The newest CPUs/FPUs like Athlon64 work in 64bit precisition (double) already not to mention 128bit registers. And did u guys noticed that on Athlon64 even in 32bit mode the double math is faster then the float math ?

A piggyback article

[meburke]

The problem of arbitrary precision for floating point arithmetic has been around for years. A USENIX conference in the early 90's ('90 or '92 I think) had a paper presented that showed a method for testing the precision of your floating point unit, and interestingly enough, only the Motorola worked with acceptable precision. It's been about 15 years since this issue was really addressed (although there was a small reminder in 1998) and I think it's good for us to be reminded periodically that not all hardware is reliable. Or rather, a reminder that hardware is reliable only under specific circumstances. (The original paper made mention of the the fact that the Intel FPU became more unreliable under high heat.) If anyone can point me to the original paper I'd be grateful. I can't seem to find it in my files.

The Answer

[BSonline]

Actually, the answer is 42.

Making a mountain out of a mole hill

[Anonymous Coward]

The author is a cook. He's making a mountain out of a mole hill, as in anyone who expects write mathematical floating point algorithms using a CPU's FPU should already know of the rounding problems with internal floating point representation. If this matters, and cannot be easily worked around another set of mathematical representations and algorithms should be implemented in software or via use of a pre-existing library.

In any event, here's the 2nd example results on a ppc G3:
66.37500000000000000000 59.00000000000000000000 0.12500000000000000000
result = 59.00000000000000000000

yep, thats rounding error, alright...(I'm bored...) also using 12.5 and dividing by 100, also results in the above #...

From example 1: .37 = 0.37000000476837158203

BTW: your calculators (TI & HP) will also exhibit this "problem". While I've never used TI calculators extensively, I have used various HP calculators for years, and quickly discovered the rounding on my own before knowing a damned thing about machine representation of floating point numbers and FPUs in general. In any event from extensive use of such machines, I tend to find that the round "errors" tend to cancel each other out in most cases, or that the "error" is of such a small value (billionths or less) of the total that it is negligible in most cases, especially if you limit results to thousandths of a value.

All of this crap being said, there are still some cases where the rounding "error" is evident in results of calculations, and most people are able to spot them and figure out the "more correct" result. If this is not sufficient(and not possible in machine algortithms yet) then the developer as mentioned above SHOULD be writing their own mathematical library or use any one of the 100s of open source or commercial math function libraries that either do not exhibit this "problem" or have worked around them for a particular application.

This entire "article" sounds like someone with half of a clue who got burned...

Why is this on Slashdot?

[Anonymous Coward]

I hate to troll, but c'mon Slashdot editors -- this is not news. (Shall I, too, write up pages from my first year engineering courses?)

Well, Yeah, but ....

[vtcodger]

***Well, kinda, yeah. Can you think of any applications for which 10 digits of precision isn't enough? ***

Basically, I agree with you, but as Hamming pointed out in the 1950s you can get yourself into trouble with some thing like:

A = small number, e.g. size of smallest feature in a Celeron-M CPU in microns

B = big number, e.g. distance to Andromeda galaxy in microns

C = (A+B) ... (some set of clever operations) ... - B

The math is fine, but the implementation won't yield the correct answer. because the value of interest got scaled off. That isn't rocket science, but it is suprisingly hard to catch.

That said, Floating Point works suprisingly well for most things. Back in the 1960s, things like 2+2=3.99999 were a fairly common phenomena. Hardly ever happens today. I spent about three decades in the defense industry writing and testing systems that got things from point X to point Y. I think I saw a reasonable selection of the possible errors that folks can make. Other than subtracting big numbers from other big numbers and expecting the result to be precise, I can't recall a single problem with floating point.

If we're looking for something that is basically broken to write an article about, forget floating point. Try event driven software architectures. Or the notion that it is possible to write unambiguous specifications that are also comprehensible.

Re:Decimal Arithmetic - irony

[mlwmohawk]

In your first pararaph you recommend that "education" is a good way to avoid gaps in knowledge. I'm sorry, "education" as in "university" education is probably the most efficient way to get gaps in "education."

I've been developing software since the 70s and I have no degree. More than that, I am typically disgusted with those who do. Especially the youn ones who graduate and say things like "why do I need to know that?" A school, inevitably, teaches to a test or some curriculum, where as an inherently curious person will explore more deeply.

I remember reading about floating point math and how it works many years ago, and recall thinking that it was just not suited for many applictions. When writing banking algoiriths, you need to use a precision math package. Double precision, however, is good enough for a lot of calculations as long as you understand that it is not precise.

As for software engineering, I agree with you. We need to engineer more than we do. I have long since been satisfied with the auto mechanic/engineer analogy for software developers. You don't need to be a good mechanic to replace an alternator. You need to be a fairly good mechanic to rebuild an engine. But you want someone who thinks like an engineer to design your engine. Some software jobs are analogus to replacing an alternator, some software jobs, like finance and spacecraft landing probably require engineering skills.

An engineer isn't an education, it is a way of thinking. If you already think like an engineer, a common library or the internet will provide the education you need, probably better than any university.

P.S.
While I do not have a degree, in my 20s I used to help my former high school friends with their course work for their EE and CS degrees. I even disagreed with their professors regularly. I was right, of course, as the professors were teaching from "their books" (often the ones written themselves) and not a plurality of books. One professor yelled at my friend for "not following his teaching." Often times when you "understand" the topic, a more specific and easier solution is obvious. You'd be surprised at how many professors don't actually like students being creative. A creative student is hard to grade because the professors, typically, do not understand the creative appraches and are left with simply looking at correct answers, and the process by which they were arived, is unclear to them. Thus injuring the professors eqo.

Yup, Universities suck because the professors, not all, obviously, but typically anyway, have a self promotional agenda which is not education.

This is why we don't use Java

[Anonymous Coward]

First of all, the best adivce is not to use a non-IEEE compliant floating point language such as Java.

Second, for most finincial transactions, monetary units are generally represented as integers, yes INTs;

long int dollars;
int cents;

this covers the full range of +/- 0-65535 for cents WITHOUT those nasty rounding problems. Most languages have built in currency datatypes, Yes even JAVA. And since it's based on INTEGERS, the poor floating point performance and non-conformance don't come into play.

Re:Decimal Arithmetic - irony

[Anonymous Coward]

It sounds like you have spent an inordinate amount of time justifying to yourself why you didn't get your degree. Relax!

Re:floats are not "inaccurate," approximately :-)

[mlwmohawk]

Many people seem to think of floats as a kind of number that gives fuzzy results; that's b.s. Floating point numbers operate according to precise models. Those models may not fit your calcuations or needs, and one can argue that IEEE has standardized a Rube Goldberg-style floating point model, but none of that makes them inaccurate.

You see, this is the problem with computer science today. I am reminded of a story told by CBS' Andy Rooney, he is in some breakfast joint and orders the "fresh squeezed orange juice." When it arrives, Andy tastes it and says to the waiter, "This is not fresh squeezed orange juice." To which the waiter replies: "Yes, it is, let me get the bottle and show you."

Yes, IEEE floating point is a very well documented standard. Absolutely, it is a very well documented precise model for approximating numbers.

Anyone who whishes to argue otherwise must understand that the static representation of a number must have sufficient data with which to represent it. 64 bits is not enough data to accuratly represent the range of data it is supposed to. Now, double precision has enough precision for calculations where there is a measurable percent of inaccuracy in the numbers, i.e. like electrical circuits and near range rocket trajectory, but when it comes to money, no.

You can improve the situation as some FPU systems have 80 bits internally, and some compiler switches to preserve the precision in the FPU, but if you are doing banking, you have to use a package like BCD math.

Good thing I use double instead of float....

[gatkinso]

...THAT should keep me safe from thems nasty float errors!

Re:Decimal Arithmetic - irony

[mlwmohawk]

It sounds like you have spent an inordinate amount of time justifying to yourself why you didn't get your degree.

It isn't a justification so much as it is a disgust with computer science trends. I don't know a single person in my age/experience range that thinks CS grads are qualified or up to the task of doing anything more than "business logic" crap. The CS grads today do not understand computers or computing. They do not understand how the machines really work. Thus, if you want to hire someone to write a device driver, graphics routines, high speed math, or any non-trivial application, you can't look for a young guy. What's even worse, is that the CS guys are told that the actual computer is unimportant and are poisoned by the nonsensical Djykstra quote they are fond of spouting.

There are "real" issues with "real" computers, and this math article is just one example. "real" computers can't do anything but simple arithmatic (add/sub[mul,[div]]). FPU's implement more but as numeric approximations that are generally "close enough," but are too often confused for accurate math. Implementing real word concepts on computers efficiently is a real science. Implementing real world concepts on a theoretical computer is nonsense.

basic computer science...

[smash]

... one of the first things we got taught with regards to data types is that you DO NOT USE FLOATS on data that needs to be accurate.

e.g., money values...

How they ended up in financial software is a worry... then again there's a lot of SHIT software out there...

Re:Decimal Arithmetic - irony

[Canthros]

You're half right. An engineer isn't a degree. A degree's not a worthless piece of paper, though, and, although you might not get much value from a college education (good grief. Were your friends students at a community college?) from one, they're still very useful. At the very least, there are better schools out there.

BCD isn't the answer

[Ayanami Rei]

Fixed point isn't really necessary either.
If you do calculations using 32-bit integers representing (cents/tenths/hundreths of cents) it works out quite well.
I mean, do you need a cash register than can tally sums > $1000000?

Re:BCD isn't the answer

[Nutria]

I mean, do you need a cash register than can tally sums > $1000000?

You do realize that there's more to business than cash registers, right?

A 32-bit fixed point number maxes out at 21,474,836.47 which is severely limiting for all but small-sized businesses and tiny governments.

64-bit fixed point number (max 92,233,720,368,547,758.07) are obviously better, but are only efficient on 64-bit machines, which are still a minority of installed machines.

Re:BCD isn't the answer

[/ASCII]

64-bit computing is reasonably efficient on most 32-bit machines. And $92,233,720,368,547,758.07 is more than the summed total earnings of every single person alive on the planet today.

Re:BCD isn't the answer

[mrchaotica]

According to other posts, a cash register using floats could also screw up on really small sums, added a large number of times.

Re:BCD isn't the answer

[Nutria]

64-bit computing is reasonably efficient on most 32-bit machines.

Are you sure? Such a needs 4 or 6 32-bit registers (depending on whether you overwrite one of the operands with the answer), and x86 has so few registers that you use them all in a single calculation, meaning that you must push the existing contents of the registers. Unless of course you leave one of the operands in RAM, which really sucks.

And $92,233,720,368,547,758.07 is more than

If I implied that 92 quadrillion isn't enough, sorry. Not my intent.

Still, most (all?) fixed point implementations use a scale of 2, which is adequate most of the time, but not all of the time.

And there's still the problem that Fixed Point is not integrated into any "modern" programming languages (except SQL).

Re:BCD isn't the answer

[91degrees]

And there's still the problem that Fixed Point is not integrated into any "modern" programming languages (except SQL).

But it doesn't need to be. It's trivial to implement in any language with operator overloading. Doing so for BCD isn't exactly rocket science either.

Re:BCD isn't the answer

[Nutria]

But it doesn't need to be. It's trivial to implement in any language with operator overloading. Doing so for BCD isn't exactly rocket science either.

Never said it was hard... Hell, COBOL did it 45 years ago.

Unfortunately, no "modern" languages have done it. While it's understandable that academic- and reasearch-designed languages have deigned to do it, I'm surprised that, for example, IBM hasn't tried to get it into Java.

Re:BCD isn't the answer

[91degrees]

Modern languages are designed for flexibility. They don't implement complex numbers, or vectors either. A lot of them don't even bother with strings. OO programming has made direct language suppport for higher level structures redundant.

Irrational Numbers

[Anonymous Coward]

"Can you explain this charge of arctan(gamma(1/cube-root(17)) on my account?"

floating point values are not approximations

[Anonymous Coward]

Floating point numbers are not approximations. Putting aside NaN and inifinity, every bit pattern represents a specific rational number. The relevant standards define the basic operators (addition, subtraction, multiplication, division and square root) as returning the floating point number closest in value to the ideal result. It turns out that this guarantee is quite cheap to implement in hardware.

The next thing to understand is that the representation represents fractions in base-2 instead of base-10. For us 0.3079 means 3/10 + 0/100 + 7/1000 + 9/10000. For the computer 0.1010 means
1/2 + 0/4 + 1/8 + 0/16. In our notation rationals with a denominator that is a multiple only of 2 and 5 eventually reduce ...0000000000 but with a binary notiation only rationals where the denominator is a power of 2 can reduce in this way.

Originally computers were made using base 2, base 10 and base 16. Eventually someone proved that base-2 always gives more significant digits per bit than any other representation and the other floating point formats basically disappeared.

Now, at first glance this may seem terrible -- but it almost never really matters. In a base 10 scientific system you'll almost never be able to operate solely inside the rationals that are represented exactly in decimal fractions. Even common financial calculations (such as amortizing a mortgage) use irrationals and applying percentages to arbitrary amounts of money obviously results in fractional pennies :) It's not like these problems magically disappear if you use a better math library or the financial industry can avoid using e from time to time.

To sum up, read up on floating point. It's a very elegant, well thought-out systems designed for scientific computing but with general utility. If you understand it you can use it. And if the text you are reading describes the numbers as approximations stop reading and look for a better text.

Vancouver Stock Exchange

[florescent_beige]

A quick Google, oops I mean a quick search using the web site www.google.com, on the Vancouver Stock Exchange turned up this.

I still remember the time the prof in our numies class talked about rounding down if the trailing digit was 1-4, rounding up if it was 6-9, and randomly choosing up or down if it was 5. We were all thinking...Wha? None of the packages I have used since then (eg NASTRAN) employ such a strategy as far as I know, although it may be buried deep inside the guts somewhere.

But it's always been in the back of my mind, doesn't rounding up on 5 introduce a bias?

Floats are dirty!

[redelm]

"Working in FP math is a lot like moving sandpiles. Everytime to try to move one, you lose some sand, and pick up some dirt."[Kernigan&Plauger]

Floats have their uses, but generally they trade exactness for range. And huge pifalls for the uninitiated, like comparing floats for equality.

AFAIK, accounting systems are still done in COBOL-heretige BCD fixed point math, usually as integer mils (one thousandth of a cent). Spreadsheets run into trouble because they are usually double floats.

My thoughts w.r.t. BCDs

[Ayanami Rei]

They are useful for storing decimal quantites unambigously in databases and flat files.
However they are not as useful for code that manipulates them heavily:

* MP libraries that use full-on binary representation are always faster and more memory efficient unless we're talking about an IBM mainframe
* It's a pain to up and downconvert from "normal" datatypes

In-memory representations are probably better served by 64-bit quantites of fractions of a currency unit or a fixed point type. (Using an MP library to simulate BCD is overkill since a 64-bit integer has a greater mantissa than any financial system will ever need, even if calculating the National Debt to the penny)

On 32-bit systems that lack instructions like MMX/SSE/Altivec to handle 64-bit quantites, one might instead use a packed struct of two 32-bit quantites at appropriate currency divisions (US: dollars and ten thousandths of cents, JP: thousands and hundreths of Yen) can also work. The second method is more cumbersome but there are some nice tricks: like when summing you can get away with resolving the carry until outside of the loop as long as N < 1000 or so.

In any case packed structs are probably unnecessary on 32-bit architectures anymore because most compilers and scripting languages have a decent 64-bit emulation mode that is as good as any library implementation.

BC Math or other representations

[PhYrE2k2]

We all know that the answer to this problem is to represent numbers as non-approximate values.

If you have a fixed number of decimals, just including a point in an integer will save storage space: 12345 = 123.45
Alternately, store as strings (though accept 8 bits per character, including decimal) and use string math, such as bcmath. This of course at the expense of speed.

You will maintain perfect precision in these cases.

The FPU uses exponents and anyone with the basics of programming knows this. Now we all know why you "don't let your 12 year old niece" make your crucial purchasing software or online store as is all too common- they ignore these facts and feel that double and single are good types... until you fail to balance at the end of the year.

-M

It converts O(N^2) into O(N log N)

[Ayanami Rei]

Multiplication is equivalent to a convolution of two discrete arrays.
It's a O(N^2) operation if done using the multiply, shift, add method.
An FFT (of which there are integer variations) is a O(N*log(N)) manipulation of the data.
When you transform both arrays, you do a straight component multiply, then you untransform the result.

3 * O(N log N) + O(N) O(N ^ 2) for very large multiplicands.

We're talking about way outside of the range of most scientific or financial applications. It's an important speedup for mathematical research and certain kinds of statistical analysis.

Numerical Stability

[Anonymous Coward]

It's a classic problem. Back in the first Gulf war, the ground based defense missiles (I think it was the Patriot line) had to keep being rebooted every couple of hours because their guidance systems had a cumulative numerical instability in them. It was the first time they had run the missiles on continuous hot standby for periods of days at a time, so it was the first time that the problem cropped up. Talk about learning the hard way. Being able to analyse an algorithm for its numerical stability should be part of every programmer's arsenal of tricks.

LOADS of people don't understand

[fdrebin]

Okay, Show of hands: Who did not already understand that floats are approximations? Anyone? I didn't think so. I've gotta wonder why this story ever made it into Slashdot. This is more worthy of Time magazine where it can be spun as a startling new revelation into the dirtier corners of computer science and foisting a lie on the public.

LOADS of people don't understand it. And I MEAN people with CS degrees.
Mostly I've worked in scientific areas. I've given the "here's what's really going on inside floats" dozens of times. Most of the techically oriented types said things like "Oh yeah, I remember, floats aren't exact".

I've worked for a while in a billing company. Most of the programmer types didn't have a clue about floats. But then, most of the meat-code in that area was setup by someone who did, and was not touchable.

/F

Obligatory Lisp Experience

[caymanbum]

A while ago I was going through a text on Astronomical Algorithms.

The beginning part of the book had a "be careful about computer calculations" section for those not already familiar with the concept.

One of the samples showed a simple program (in BASIC, of course!) which determined the number of significant digits used on your particular environment.

I forget the exact procedure the book used, but it involved doubling a number within a loop and then terminating the loop when the expression "x == x + 1" was true. (i.e. when adding one to a number did not affect the significant digits.)

New to Lisp, I decided to produce a Lisp version.

... To my surprise, the program ran for several minutes on my sooper dooper pentium 4 machine without terminating.

It turns out that in my naive, straight forward implementation, I was implicitly using Lisps 'bignum' support. It seems that you "automatically" get "bignums" within Lisp unless you specifically ask for something else.

A second snippet of code within this section of the same book showed how repeated rounding errors can accumulate to throw off an answer. For this, they repeatedly summed the following calculation "x = x + (((x+1)/3)*3)-1" IIRC. (The answer should always be "x".)

They showed example results from various machines for several iterations. The results dramatically illustrated the accumulated error after even a few iterations.

... Except for my naive Lisp version. It also seems that Lisp gives you a fractional datatype by default! The default implementation produced the exact answer.

Minor things really, but this was my first experience with a computer language that fit what I had learned in math class and I found it some what refreshing.

CS Education

[jefu]

As a CS professor, I agree with much of what you say.

There are certainly lots of CS professors out there who don't know much about CS and who teach (essentially) from ideology.

But the problems go deep. Part is the expectations of students who believe that they are purchasing an education and are therefore entitled to get good grades. Part is the way many modern universities work where "retention" is king and therefore we must keep students in the program or the program dies. Even if that means that students stay in programs that they should not be in. Part is the trend toward codifying "outcomes and assessments" in courses, which usually means not just "objective tests", but objective tests that cannot vary much, even over the course of years. As an example, in one program I know of, the person teaching the "CS 1" type courses has no real world experience and does not teach any kind of problem solving, but the professors who do have the background are not allowed to teach the CS 1 courses, because they'd scare off the students - and we're back to retention.

Got any suggestions?

Re:CS Education

[mlwmohawk]

I have actually read about a lot of the problems you are talking about. The problem is that universities, like hospitals, media news, and so many other organizations, are serving two masters, what they wish to accomplish and profits. All too often the short sighted focus on profits erode the value of the objective (which has a slow growth inherent value).

Thus we see, in universities, news agencies, hospitals, etc. a steady degradation in the mission of the organization in return for quick profits for the directors and shareholders. Like locusts, when the last drop of value of the organization is gone, and it is effectively dead, they will move on to the next organization. Often selling it to a much larger organization that wants to turn it into a pointless equivilent of a McDonalds.

Harvard is almost useless as a university because of "grade inflation" (for the above reasons), MIT and its grads have seen better days. So many institutions of great reputation are little more than shells of their former selves.

OK, I have to stop ranting and get back to work.

Rounding is no big deal

[etresoft]

Everyone knows about rounding problems with floats. What people don't seem to realize (and this goes for many real "Rocket Scientists" I've known) is that a float only gives you a fixed amount of digits - that's all. You can have a highly precise small number or a really big number. You cannot ever have a precise, big number. It just so happens that these same "Rocket Scientists" like to represent time as a floating point based on some 1970 epoch. Guess how accurate that is going to be in a couple of years. How do they solve this problem? The "double double" type of course!

Clasic testbokk issue

[ChrisA90278]

I still have this textbook I got in 1971. It's called "Computer Science, A first course". It talks about this same exact problem or representation. If compared integer, floating and decimal representations.

Why would this count as "news". Everyone who has to deal with this would already know about it.

Re:Decimal Arithmetic - irony

[mlwmohawk]

You're half right. An engineer isn't a degree. A degree's not a worthless piece of paper, though, and, although you might not get much value from a college education (good grief. Were your friends students at a community college?) from one, they're still very useful. At the very least, there are better schools out there.

OK, I can't contain myself. OK, take the cost of the education, specifically CS or programming, and the cost of the loan, and the time spent in the university vs working getting real experience, and you'll see that going to the university is less cost effective. So, you're right, it isn't worthless, it is less than worthless. My advice to *anyone* wishing to get into computer software development is to teach yourself how to program and focus on MBA studies, because business skills are now vital in the industry.

Oh, by the way, the school's were Northeastern University, UMass Amherst, and Bridewater state. The school that had the worst professors was Northeastern.

Interval Arithmetic tries to address this

[johnny6vasquez]

If you can represent a number by an inner and outer bound, and then every time you perform a calculation using that number, you expand the bounds to represent the margin of error, you get a nice way of always knowing your precision.

So take the real value, 1/3, and represent it as say, [0.33333329, 0.33333334].

After a few operations, you could end up with [4.2134243, 4.2136963] as an answer. This tells you that your answer definitely lies in the range above, and that you have lost some certainty of the location of that "real value answer".

There's some more info here on a project website http://shrinc.ca/?n=237&h=1&r=286&wc=1

Re:Interval Arithmetic tries to address this

[An dochasac]

Recent versions of Sun Microsystem's developer suite have interval math libraries: http://docs.sun.com/app/docs/doc/806-7998 And since Sun execs are beginning to pull their heads out of their ... and finally making their development suite available for developers (free as in beer), you can play with it: http://developers.sun.com/prodtech/cc/index.jsp

Re:Decimal Arithmetic - irony

[Anonymous Coward]

Business skills could also help you, buddy. If something is worth $10 and you pay $20 for it, that does not mean it's net worth is -$10. That seems to be what you are saying, with your pithy "less than worthless" comment. Ironic, when we're branching off a topic about accuracy in financial programs. You have the float thing down, but either you are a dolt when it comes to other financial matters, or, more likely, you are shrewdly equivocating and bending the truth to serve your purposes.

The question of whether education is worth more than the opportunity cost of money in the bank + potential practical experience is stickier. Which is precisely why my hackles are rising from your posts, which clearly posit that there is an absolute answer to that question, and the answer is no degree.

actually, it is totally true...

[YesIAmAScript]

People use floats because they can hold "really big numbers". But they don't really hold the really big numbers, they just approximate them.

Floats are imprecise. They appear precise in ranges of represented values and for sizes of errors that people commonly use. But in actuality, they will silently use an approximation of the number you tried to put in instead of the real number if the number cannot be precisely represented.

That's why they are imprecise, and that's one of the big dangers.

Re:actually, it is totally true...

[StrongAxe]

Floats are imprecise.

This statement is not accurate. Floats can imprecisely represent numbers not otherwise representable is more accurate. In some cases, floating point values are precise. For example, double-precision reals can exactly represent all integers up to 2^53, and all even integers up to 2^54, and all integers divisible by four up to 2^55, etc.

They can accurately represent cash values in pennies up to 8 trillion dollars (or 8 billion, if you want to count thousandths of a cent).

Naturally, floating is for scientific computing

[porky_pig_jr]

dealing with some data that can't be measured correctly anyway, like weight, hight, etc. "Continuous values", that is (vs descrete).

You guys actualy program?

[kemo_by_the_kilo]

You guys actualy program? i though this was /.
whats happened to cpan, cut and paste and modules?

Reach for them each time? I don't think so...

[Anonymous Coward]

"We all know of floating point numbers, so much so that we reach for them each time we write code that does math."

No, "we" don't, and if you do, I hope your programming is confined to video games where such elementary mistakes couldn't cause serious consequences. What on earth are computer science classes teaching these days?

Re:Decimal Arithmetic - irony

[mlwmohawk]

You start with an insult, ad hominem, you lose one point.

Yes the pithy comment was somewhat simplistic, but it wasn't any sort of logical cop out either. The number speak for themselves. There is a conventional wisdom that it is valuable, but "conventional wisdom" is often counter to facts.

It is like the argument of buying a house vs a renting an apartment. It is not a given that one is better than the other. If you can find an apartment in which you are happy living at a substantally lower rent than you would pay for a mortgage, if you had financial self control, you could easily save more than you would be building in equity minus what you pay in interest.

If a university education is not required for your career, and in software it is not, then you have to measure the cost/benefit of the education. A CS degree fails the cost benefit test, especially since it does not actually prepare you properly for your field. You STILL need experiece. Since the knowledge one obtains from the school is readily available freely at the library or internet, and is more up to date, then the school add no value for a dedicated person. The time you spend at the school actually takes experience time away from your career.

Like I said in another thread, get an MBA with some basic programming. Learn the rest yourself. You will do far better than a McCS grad.

I love floating point representational errors...

[gremlinuk]

because I got my doctorate by writing algorithms that chose analytic and numeric method based upon the representational accuracy of floating point arithmetic when doing differences between very similar large number.

me.

No, 80 bit *is* part of IEEE.

[td]

80bit was not part of IEEE. I don't know where you think it was.

IEEE 754 includes a "double-extended" format, whose size must be at least 79 bits -- it's allowed to be longer -- and which is, in almost every implementation, 80 bits. Who knows what the parent AC is thinking.

Funny you should say that

[theantix]

I have an open task right now that requires me to prepend a zero when parsing vendor data that has only four digits.

Fixed point for financial arithmetic

[CustomDesigned]

In many financial calculations (say, current bank balances; possibly not long-term stock market estimates), you always want precision down to the nearest cent or tenth of a cent, regardless of how big the number is. That's a job for fixed-point, base-10 arithmetic.

Actually, the base doesn't matter for fixed point arithmetic. We used to use 48 bit integers: struct money { long hi; unsigned short lo; } This is particularly efficient at add,sub,mul,div even when translated from C by a relatively dumb compiler. and 48 bits is enough for the national budget of the US tracked in Lira. Important for a 16Mhz 68010. But nowadays, we just use the 64-bit integer type built in to all C compilers and Java. Plenty fast enough on a modern 32-bit processor.

The tricky programming issue is keeping track of which variable has what implicit fixed point and make sure they don't overflow. In C++, we have a template FNUM type where the int parameter is digits after the decimal point. But if you are careful, this isn't really necessary - and in fact doesn't help all that much. A comment giving precision by each struct money variable or database field is just as good.

Here Here!!

[unjedai]

Finally, someone said it! It bugs me to no end how programmers call themselves "Software Engineers" when every other kind of engineer (except maybe the guys that drive the trains) had to take a test and work under a licensed engineer for a certain period of time before assuming the title.

Re:Here Here!!

[jkauzlar]

That may be a horrible idea, depending on how you look at it.. do you want to take the field of software development, which has traditionally been open to a wide range of education-levels and people from other fields (grassroots geeks) and introduce a 'class' system? (*all* of the most brilliant programmers/software engineers I know are not CS/CE grads) IMO, the software industry has thrived on the talents and creativity of those programers who really love doing what they do and would be bored silly in the structured classroom environment.

OTOH, software mistakes can sometimes cause millions or billions of dollars worth of damage.. so some kind of accountability in the form of a certification might help?

(PS, I do have a BS degree in CS, but do not work in the software industry.)

Re:Here Here!!

[Breakfast Pants]

Recording Engineers?

GDC 2005: "EPSILON is NOT 0.00001"

[AHumbleOpinion]

See Numerical Robustness for Geometric Calculations (aka EPSILON is NOT 0.00001!) from GDC 2005 http://realtimecollisiondetection.net/pubs/

Patriot a failure?

[Inominate]

The patriot is a mobile surface to air missile system. It was designed to shoot down aircraft over europe during ww3.

It was discovered that the missile was accurate enough to potentially be able to hit a ballistic missile, upgrades to the system were put into place to give it the capability.

The gulf war came around, and the patriots got their trial by fire. It was the first time a hostile ballistic missile was shot down. Really quite a feat to pull off outside of a planned test.

It also proved serious flaws. However such flaws are to be expected with you put any new piece of equipment into a war. A major one besides the one you mention(and a much more dangerous one) is the patriot's warhead. Being that it's a SAM, it's warhead is designed to remove the target from the air, not to obliterate it. When you're shooting at an aircraft, that's the entire goal. When you're shooting at a scud which is barely being aimed as it is, all you're doing much of the time is changing the course of the warhead.

Still, Non-perfection is a long way from dismal failure, especially when you're combat testing something that's never been tried before.

Re:floats are not "inaccurate," approximately :-)

[idlake]

Yes, IEEE floating point is a very well documented standard. Absolutely, it is a very well documented precise model for approximating numbers.

Floating point numbers are no more and no less "approximations" than integers or BCD numbers: for some operations and pairs of arguments, they give you exact results, for some, they give you rounded or truncated results, and for some, they give you overflow/underflow.

The rules are a bit more complicated for floating point numbers than for integers (e.g., for integers, only division truncates), but there is nothing intrinsically "approximate" about them. You can choose to view floating point numbers as approximations in your application but many people also use them for exact computations.

Re:floats are not "inaccurate," approximately :-)

[mlwmohawk]

You can choose to view floating point numbers as approximations in your application but many people also use them for exact computations.

Sorry, but you clearly have no idea of what you are talking about. A floating point number can not 100% accurately represent every number within its range. Given any specific number, one can predict the exact representation, sure. When a series of calculation are performed one can not be sure of th outcome, exactly. For instance, if you have an array of numbers with a wide range of values, you will want to add in the order of smaller to larger. If you do it larger to smaller, you may get a different result. That is *NOT* exact by any definition.

Floating point is an inexact math system, it is design for speed, not accuracy.

Given the right size, floating-point is best

[Savantissimo]

Well, you're more right than most who have posted here. Several "real programmers" here seem to think that BCD eliminates cumulative errors. Fixed-point is not completely moronic, but you still need extra decimal places sufficient to handle iterated computations such as: interest calculations with rates to five significant digits compounded over decades, subtractions of nearly equal quantities, multiplications by one+/-epsilon or near-inverses, and so forth. But you misspoke about fixed-point numbers having fixed precision - rather, they have fixed accuracy. The former depends on the number of distinct values that can be represented, the latter depends on the absolute size of the smallest representable unit. Any given fixed-point representation has a different effective precision for every different numerical value it can hold, while floating-point numbers have a different minimum distinguishable increment (accuracy) for each value of exponent. As others have pointed out, IEEE-754 floating-point numbers have known accuracy and proper mathematical behavior, but they occasionally require some skill to use. So do the fixed-point systems, but they have less robust error behavior than the IEEE numbers with their curious special cases and ranges. Given sufficient bits in the floating-point number, the accuracy is as good or better than needed for any type of financial math (better really- finance often isn't as precise as most people here seem to think, and almost never so accurate). If you think that accuracy is important in this kind of application, though, why object to a couple of extra bytes per number? But really it's the fixed-point that wastes bits on the seldom-used but always-allocated headroom needed to store large values.

The Intel 80-bit double-extended precision floating-point number format has 64 bits of mantissa, and can exactly represent any integer between -2^64 and 2^64. Using only the positive range, that is over 19 decimal places, more than the 10 digits before and 8 after the decimal point which another poster has said is the numerical accuracy required of banks in order to be allowed connection to the London markets. In most cases, the 80-bit floating-point number is far more accurate: for account balances between +/- 16.7E6 currency units, the accuracy will be accurate to within about +/- 2^-40 units (12 decimal places), and for balances within +/- 8.6E9 currency units the accuracy will be within about +/- 2^-31 units (9 decimal places + 1 bit). Between about 137 - 274 billion-unit accounts one would have to make do with only 7.8 decimal places of accuracy instead of 8, but there would still be over 6 decimal places of accuracy even for single accounts of up to 17.6E12. So floating-point numbers can indeed guarantee high accuracy; for ordinary currency numbers, floating point has higher accuracy than almost all fixed point implementations. (And even if you do crowd the limits, the underflow is gradual due to the "subnormal" and "denormal" numbers which are smaller than the normal range.)

Examples:
If you were to add fractional-cent amounts calculated to have the maximum possible error of representation in 80-bit format (7.45E-7 cents ) to a billion-dollar account once per minute for fifteen months, the accumulated error would still be less than half a cent. In more normal acccounts of 1 million dollars, the 2.27E-13 cent maximum error would have to be added once per millisecond for nearly 70 years to reach half a cent accumulated error. Any error from adding approximated binary fractions (1/odd number, etc.) would of course usually be less than the maximum error.

Floats are usually much more convenient than fixed representations for practical higher financial calculations. However, if one needs to do something less useful - say, calculate the interest on the US national debt compounded and recalulated each microsecond in units of quadrillionths of Weimar-era hyperinflated Marks, (and you are too 1337 to use a 128-bit format), then use arbitrary-precision arithme

Integers are all you need.

[Anonymous Coward]

You could just discard decimal numbers altogether and only use integers. After all, it's the enterprise-y thing to do.

Unless the article was written by Richard Pryor...

[Tim Browse]

...I'm not interested.

Moo

[Chacham]

Old news.

Timely remark.

[hicksw]

The Daily Telegraph (London UK) reports that the US Bureau of Labor Statistics has a rounding problem.

http://www.telegraph.co.uk/money/main.jhtml?xml=/m oney/2006/08/15/cnus15.xml

It seems that doubtful rounding practices have distorted US consumer price index figures.

float like a butterfly sting like a bee

[ncmathsadist]

This floating point problem is an old chestnut. Now that you are among the floating-point sapent, I'd recommend this book

Acton, Forman, Real Computing Made Real, Princton Univeristy Press.

This humorous, informative book will chasten and remind the casual user of floating point numbers! The losss of significant digits can be truly tragic....

Associative

[Anonymous Coward]

Numerics course I,

exercise sheet 1,

1 a) Proove that floating point addition is not assoiative

no, it's completely accurate

[YesIAmAScript]

Floats are imprecise.

You can do this statement:

x = (float) 16777215

And it sill compile, run and happen. The number will appear to fit.

Except x doesn't hold precisely 16777215. It holds approximately 16777215. Yes, everyone should know that things like this can occur and program so they don't run into such problems. But the whole point of the article is people don't know this, and they don't program around such problems.

For example, double-precision reals can exactly represent all integers up to 2^53, and all even integers up to 2^54, and all integers divisible by four up to 2^55, etc.
They can accurately represent cash values in pennies up to 8 trillion dollars (or 8 billion, if you want to count thousandths of a cent).


These statements are completely true. They also lose close to non-obvious problems like that even though it can exactly represent all integers up to 2^53, if the proper result for the formula you are computing is an integer up to 2^53, it doesn't mean the double that represents that result will equal that integer. Often it will be close to that integer within some error bars. You really should compute these error bars so you can then compare against the proper result or do a round to decimal place (in this case integer, the 0th decimal place) within these error bars against that value. But instead people do

if (81 == x)

and it doesn't match.

The IEEE standard does a great job with guard bits to attempt to prevent this, but in the end, it is up to the programmer to understand that precision will be lost (because floats are imprecise) and how to work around this.

Ask a programmer if they know floats are imprecise and they'll say they are and they are familiar with the issues. Then ask them if 0.1 can be accurately represented in a float and they'll look at you quizicaly as if the question were to trivial that it doesn't even need to be asked. When you point out it cannot, they'll maybe say something like "not my problem, I use doubles instead of floats anyway, they are more accurate".

It's a big problem. Floats are imprecise, they approximate values in situations people people don't expect. And because of that, at the end of a sequence of operations, they often end up with a messy 0.000000001 sticking on their "precise" integer less than 2^53 and they rarely investigate the proper way to handle it.

Re:no, it's completely accurate

[StrongAxe]

Except x doesn't hold precisely 16777215. It holds approximately 16777215.

This is a matter of interpretation. x holds a floating-point value that is exactly 16777215.00000000000.... Now, within the confines of inexact calculations, such a value could be the result of any expression that yields any real number within the range 16777215+/-2^29. This is because one usually cannot predict the values that ought to be stored in the guard digits, so it is usually best to just treat them as random statistical noise.

However, if you know that the values being computed are exactly integers, you also know that the values lost in the guard digits are exactly equal to zero, in much the same way that if you buy something for $83 dollars and hand the cashier a $100 bill, you know that you won't be receiving any pennies in change.

But instead people do if (81 == x) and it doesn't match.

In most floating-point applications where you have non-zero values for the guard digits, yes, this is true. However, in the narrow set of applications where you can guarantee that the guard digits and fractional digits are zero, such a comparison is valid.

In C, you can safely say for (f=0.0; f!=10.0; f+=1.0) because the values are exact integers.
You can even safely say for (f=0.0; f!=2.5; f+=0.25) because the values are exact binary fractions (on a binary machine).
You cannot safely say for (f=0.0; f!=1.0; f+=0.1) because there is a non-zero error in 0.1 so the comparison fails.

The IEEE standard does a great job with guard bits to attempt to prevent this, but in the end, it is up to the programmer to understand that precision will be lost (because floats are imprecise) and how to work around this.

Precision can be lost if the operands produce results that cannot be accurately represented in the floating-point format. If this happens, a Significance Exception is raised. However, not all operations do this. Operations in which the result of the calculations can be performed with zero error leave the exception unraised, and produce results that are exactly accurate. This happens to be the case when working with floating-point numbers that are integers (or exact multiples of 2^-n) and the mantissa of the result can be stored within the significant number of bits (24, 53, or 64, depending on precision).

Ask a programmer if they know floats are imprecise and they'll say they are and they are familiar with the issues.

I am a programmer, and I am quite familiar with the issues on both sides of this discussion. I will agree with you that in the vast majority of cases, one cannot rely on the accuracy of floating point, because in the vast majority of the cases, one does not know the source of the values, nor how accurately they represent the real-world quantities you are modeling. However, in certain situations where you can accurately model the errors (as in this case, where the errors are always zero), one can make such assumptions.

It's a big problem. Floats are imprecise, they approximate values in situations people people don't expect. And because of that, at the end of a sequence of operations, they often end up with a messy 0.000000001 sticking on their "precise" integer less than 2^53 and they rarely investigate the proper way to handle it.

I will agree that most programmers are not aware of the pitfalls of using floating point, and they should definitely avoid using it where accuracy is required unless they know exactly what they are doing. In my example, if all values used are exact integers
Using floating point is a bit like navigating a minefield. For most, the safest advice is "just stay away". However, it can be safe to do if you know where the mines are.

Why not ...

[hummassa]

A dual system? You know, where you do single-cycle mul/div in one "LNS half" of the register and then, in another number of cycles, on background, you update the other "float half". OR you do single-cycle add/sub in the "float half" and update the "LNS half" on the background.

Re:floats are not "inaccurate," approximately :-)

[Anonymous Coward]

A floating point number can not 100% accurately represent every number within its range.

Neither can an integer variable; integer variables only represent integers within their range. Floating point numbers can do that, too, and a lot more.

When a series of calculation are performed one can not be sure of th outcome, exactly.

Of course, one can, just like with integers.

For instance, if you have an array of numbers with a wide range of values, you will want to add in the order of smaller to larger. If you do it larger to smaller, you may get a different result. That is *NOT* exact by any definition.

Neither integers nor floating point numbers obey associativity.

Floating point is an inexact math system, it is design for speed, not accuracy.

Bullshit.

A place for a factorial base representation?

[Anonymous Coward]

I read an article in (I think) Dr Dobbs about this sort of stuff, describing a scheme using factorial base arithmetic, which was able to represent any rational number in finite space, with a reasonable constant. The gist of it was that instead of each successive place representing some quantity divided by a higher power of the base, it represents a quantity divided by a larger factorial.

The upshot of it was that as long as you restrict yourself to rational numbers at the start, and perform only +, -, * and / operations (steering clear of roots and powers with non-integral exponents, for example) you will be able to get an exact result. Depending on how many calculations you go through and what numbers you generate, the representations might grow quite large, but they'll always be exact.

One might observe that the first terms are necessarily small and there is wasted space and time, but a refinement of the technique could lump terms together to conserve space and speed up processing.

That's the idea anyhow, and it appealed to me but I've seen little or nothing of the technique since that article was published.

Regards.