7 ms·

I've worked with large datasets, aggregating millions of numbers, summing, dividing, averaging, etc... and I have tested the orders of operations, trying to for

I've worked with large datasets, aggregating millions of numbers, summing, dividing, averaging, etc... and I have tested the orders of operations, trying to force some accumulated error, and I've actually never been able to show any difference in the realm of 6-8 significant digits I looked at.

tomxor 7y ago
> in the realm of 6-8 significant digits I looked at That is far inside the range of 64bit double precision. For error to propagate up to that range of significance depends on the math, but i doubt the aggregation you are describing would cause it... provided nothing silly happens to subtotals like intermediate rounding to precision (you'd be surprised). Something like compounding as the parent was describing are far more prone to significant error propagation.
karmakaze 7y ago
I've seen rounding errors on something as simple as adding the taxes calculated per line item vs calculating a tax on a subtotal. This was flagged as incorrect downstream where taxes were calculated the other way. In a real-life transaction where pennies are not exchanged this could mean a difference of a nickel on a $20 purchase which isn't a meaningful difference but certainly not insignificant.
- Demiurge 7y ago
  How much was the difference? Was there any rounding involved at any step? When dealing with money, I see rounding and integer math all the time. As another comment has mentioned, within 53 bits of mantissa, the number range is so big, we are talking 16 digits. I''d be curious to see a real-world example where the float math is the source of error, as opposed to some other bug.
  - karmakaze 7y ago
    It doesn't take much imagination to construct an example. Knowing 0.1 isn't exactly represented make a formula with it that should be exactly a half cent. Depending on fp I precision it will be slightly above or below a half cent and rounding will not work as expected. We found this in prod at a rate of hundreds to thousands of times per day it only takes volume to surface unlikely errors.
    - Demiurge 7y ago
      It is the rounding that seems to be an issue here.
    - karmakaze 7y ago
      I thought I was clear that the result was rounded. The fp imprecision affects the correctness of rounding e.g. half to nearest even.
vbezhenar 7y ago
JavaScript is precise for 2^53 range. It's unlikely that you're operating with numbers outside of that range if you're dealing with real life things, so for most practical purposes doubles are enough.
- karmakaze 7y ago
  Actually this is a source of many issues where a 64bit int say a DB autoinc id can't be exactly represented in a js number. Not a inreallife value but still a practical concern.
- civility 7y ago
  > JavaScript is precise for 2^53 range What does this mean to you? It's very easy to get horrible rounding error with real-life sized things. For instance document.writeln(1.0 % 0.2); The right answer is 0.0, and the most it can be wrong is 0.2. It's nearly as wrong as possible. These are real-life sized numbers. btw: I think IEEE-754 is really great, but it's also important to understand your tools.
  - vbezhenar 7y ago
    I'm talking about integer numbers. 2^53 = 9007199254740992. You can do any arithmetic operations with any integer number from -9007199254740992 to 9007199254740992 and results will be correct. E.g. 9007199254740991 + 1 = 9007199254740992. But outside of that range there will be errors, e.g. 9007199254740992 + 1 = 9007199254740992
    - civility 7y ago
      I didn't see anything in your message above indicating you were restricting yourself to integers.
    - tomxor 7y ago
      You are are describing only one of the types of numerical error that can occur, and it is not commonly a problem: this is only an edge case that occurs at the significand limit where the exponent alone must be used to approximate larger magnitudes at which point integers become non-contiguous. The types of errors being discussed by others are all in the realm of non-integer rationals where limitations in either precision or representation introduce error and then compound in operations no matter the order of magnitude... and btw _real_ life tends to contain _real_ numbers, that commonly includes rationals in use of IEEE 754.
civility 7y ago
x = 1e-20 + 1e20 - 1e20 y = 1e20 - 1e20 + 1e-20 assert x == y
- firethief 7y ago
  That's like the first rule of floating point numbers though: don't do that
  - civility 7y ago
    The person I replied to claims to have looked at large* data sets and never seen a discrepancy in 6-8 significant digits. I thought I'd show them a small data set with 3 samples that retains no significant digits. * Never mind that "millions" isn't large by current standards...
    - firethief 7y ago
      But you are observing all the digits, not just 6-8. It's implicit in the semantics of the operation, and that's something everyone who works with floating point should know.
      - civility 7y ago
        I think I see where you're hung up. If I change it to: x = 1e20 + 1 - 1e20 y = 1e20 - 1e20 + 1 assert x == y There is only 1 digit, and it's wrong. You don't even need 6-8. I probably should've used this as my example in the first place.
        firethief 7y ago
        You're making the same mistake but now it's less obvious because the change of scale. When you compare floating point numbers, simple == is not usually what you want; you need to compare them with a tolerance. Choosing the tolerance can be difficult, but in general when working with small numbers you need a small value and with large numbers you need a large value. This dataset involves datapoint(s) at 1e20; at that magnitude, whatever you're measuring, the error in your measurements is going to be way more than 1, so a choice of tolerance ≤ 1 is a mistake.
ryani 7y ago
Here's a common problem that shows up in implementations of games: class Time { uint32 m_CycleCount; float m_CyclesPerSec; float m_Time; public: Time() { m_CyclesPerSec = CPU_GetCyclesPerSec(); m_CycleCount = CPU_GetCurCycleCount(); m_Time = 0.0f; } float GetTime() { return m_Time; } void Update() { // note that this is expected to wrap // during the lifetime of the game -- // modular math works correctly in that case // as long as Update() is called at least once // every 2^32-1 cycles. uint32 curCycleCount = CPU_GetCurCycleCount(); float dt = (m_CycleCount - curCycleCount) / m_CyclesPerSec; m_CycleCount = curCycleCount; m_Time += dt; } }; void GAME_MainLoop() { Timer t; while( !GAME_HasQuit() ) { t.Update(); GAME_step( t.GetTime() ); } } The problem is that m_Time will become large relative to dt, the longer the game is running. Worse, as your CPU/GPU gets faster and the game's framerate rises, dt becomes smaller. So something that looks completely fine during development (where m_Time stays small and dt is large due to debug builds) turns into a literal time bomb as users play and upgrade their hardware. At 300fps, time will literally stop advancing after the game has been running for around 8 hours, and in-game things that depend on framerate can become noticably jittery well before then.
- Dylan16807 7y ago
  Though inside game logic you should probably default to double, which would easily avoid this problem.
  - ryani 7y ago
    If I'm going to use a 64 bit type for time I'd probably just use int64 microseconds, have over 250,000 years of uptime before overflowing, and not have to worry about the precision changing the longer the game is active.
    - Dylan16807 7y ago
      So using fixed point. You could do that, but you can't make every single time-using variable fixed point without a lot of unnecessary work. Without sufficient care you end up with less precision than floating point. If you don't want to spend a ton of upfront time on carefully optimizing every variable just to avoid wasting 10 exponent bits, default to double.

tomxor 7y ago

> in the realm of 6-8 significant digits I looked at That is far inside the range of 64bit double precision. For error to propagate up to that range of significance depends on the math, but i doubt the aggregation you are describing would cause it... provided nothing silly happens to subtotals like intermediate rounding to precision (you'd be surprised). Something like compounding as the parent was describing are far more prone to significant error propagation.

karmakaze 7y ago

I've seen rounding errors on something as simple as adding the taxes calculated per line item vs calculating a tax on a subtotal. This was flagged as incorrect downstream where taxes were calculated the other way. In a real-life transaction where pennies are not exchanged this could mean a difference of a nickel on a $20 purchase which isn't a meaningful difference but certainly not insignificant.

Demiurge 7y ago
How much was the difference? Was there any rounding involved at any step? When dealing with money, I see rounding and integer math all the time. As another comment has mentioned, within 53 bits of mantissa, the number range is so big, we are talking 16 digits. I''d be curious to see a real-world example where the float math is the source of error, as opposed to some other bug.
- karmakaze 7y ago
  It doesn't take much imagination to construct an example. Knowing 0.1 isn't exactly represented make a formula with it that should be exactly a half cent. Depending on fp I precision it will be slightly above or below a half cent and rounding will not work as expected. We found this in prod at a rate of hundreds to thousands of times per day it only takes volume to surface unlikely errors.
  - Demiurge 7y ago
    It is the rounding that seems to be an issue here.
  - karmakaze 7y ago
    I thought I was clear that the result was rounded. The fp imprecision affects the correctness of rounding e.g. half to nearest even.

vbezhenar 7y ago

JavaScript is precise for 2^53 range. It's unlikely that you're operating with numbers outside of that range if you're dealing with real life things, so for most practical purposes doubles are enough.

karmakaze 7y ago
Actually this is a source of many issues where a 64bit int say a DB autoinc id can't be exactly represented in a js number. Not a inreallife value but still a practical concern.
civility 7y ago
> JavaScript is precise for 2^53 range What does this mean to you? It's very easy to get horrible rounding error with real-life sized things. For instance document.writeln(1.0 % 0.2); The right answer is 0.0, and the most it can be wrong is 0.2. It's nearly as wrong as possible. These are real-life sized numbers. btw: I think IEEE-754 is really great, but it's also important to understand your tools.
- vbezhenar 7y ago
  I'm talking about integer numbers. 2^53 = 9007199254740992. You can do any arithmetic operations with any integer number from -9007199254740992 to 9007199254740992 and results will be correct. E.g. 9007199254740991 + 1 = 9007199254740992. But outside of that range there will be errors, e.g. 9007199254740992 + 1 = 9007199254740992
  - civility 7y ago
    I didn't see anything in your message above indicating you were restricting yourself to integers.
  - tomxor 7y ago
    You are are describing only one of the types of numerical error that can occur, and it is not commonly a problem: this is only an edge case that occurs at the significand limit where the exponent alone must be used to approximate larger magnitudes at which point integers become non-contiguous. The types of errors being discussed by others are all in the realm of non-integer rationals where limitations in either precision or representation introduce error and then compound in operations no matter the order of magnitude... and btw _real_ life tends to contain _real_ numbers, that commonly includes rationals in use of IEEE 754.

civility 7y ago

x = 1e-20 + 1e20 - 1e20 y = 1e20 - 1e20 + 1e-20 assert x == y

firethief 7y ago
That's like the first rule of floating point numbers though: don't do that
- civility 7y ago
  The person I replied to claims to have looked at large* data sets and never seen a discrepancy in 6-8 significant digits. I thought I'd show them a small data set with 3 samples that retains no significant digits. * Never mind that "millions" isn't large by current standards...
  - firethief 7y ago
    But you are observing all the digits, not just 6-8. It's implicit in the semantics of the operation, and that's something everyone who works with floating point should know.
    - civility 7y ago
      I think I see where you're hung up. If I change it to: x = 1e20 + 1 - 1e20 y = 1e20 - 1e20 + 1 assert x == y There is only 1 digit, and it's wrong. You don't even need 6-8. I probably should've used this as my example in the first place.
      - firethief 7y ago
        You're making the same mistake but now it's less obvious because the change of scale. When you compare floating point numbers, simple == is not usually what you want; you need to compare them with a tolerance. Choosing the tolerance can be difficult, but in general when working with small numbers you need a small value and with large numbers you need a large value. This dataset involves datapoint(s) at 1e20; at that magnitude, whatever you're measuring, the error in your measurements is going to be way more than 1, so a choice of tolerance ≤ 1 is a mistake.

ryani 7y ago

Here's a common problem that shows up in implementations of games: class Time { uint32 m_CycleCount; float m_CyclesPerSec; float m_Time; public: Time() { m_CyclesPerSec = CPU_GetCyclesPerSec(); m_CycleCount = CPU_GetCurCycleCount(); m_Time = 0.0f; } float GetTime() { return m_Time; } void Update() { // note that this is expected to wrap // during the lifetime of the game -- // modular math works correctly in that case // as long as Update() is called at least once // every 2^32-1 cycles. uint32 curCycleCount = CPU_GetCurCycleCount(); float dt = (m_CycleCount - curCycleCount) / m_CyclesPerSec; m_CycleCount = curCycleCount; m_Time += dt; } }; void GAME_MainLoop() { Timer t; while( !GAME_HasQuit() ) { t.Update(); GAME_step( t.GetTime() ); } } The problem is that m_Time will become large relative to dt, the longer the game is running. Worse, as your CPU/GPU gets faster and the game's framerate rises, dt becomes smaller. So something that looks completely fine during development (where m_Time stays small and dt is large due to debug builds) turns into a literal time bomb as users play and upgrade their hardware. At 300fps, time will literally stop advancing after the game has been running for around 8 hours, and in-game things that depend on framerate can become noticably jittery well before then.

Dylan16807 7y ago
Though inside game logic you should probably default to double, which would easily avoid this problem.
- ryani 7y ago
  If I'm going to use a 64 bit type for time I'd probably just use int64 microseconds, have over 250,000 years of uptime before overflowing, and not have to worry about the precision changing the longer the game is active.
  - Dylan16807 7y ago
    So using fixed point. You could do that, but you can't make every single time-using variable fixed point without a lot of unnecessary work. Without sufficient care you end up with less precision than floating point. If you don't want to spend a ton of upfront time on carefully optimizing every variable just to avoid wasting 10 exponent bits, default to double.