Potential loss of precision due to floating-point numbers

[dexX7]

It is given that certain rational numbers can not be represented as floating point with any finite precision, and it's representation would have an endlessly repeating sequence, resulting in an approximation of the actual value. While this likely only affects the fractional part of numbers, there are other pitfalls, and depending on the level of precision, there are gaps between numbers (for example 9007199254740993 doesn't exist, when using double).

At this point it is unclear, if the meta DEx might be affected by similar issues, which currently uses boost::multiprecision::cpp_dec_float_100 to represent numbers, which are further transformed into strings and cut after a certain number of digits. This primarily affects the calculation of unit prices, and related values, such as the updated amount desired by a seller, the updated amount desired by a buyer, the number of units a buyer receives, and the order matching, which is based on the unit price.

To avoid potential pitfalls related to floating-point numbers, suggestions so far were to use boost::rational to represent rational numbers, or to use boost::multiprecision::int128_t with plain integer math for the core calculations.

It should be discussed, whether this is an actual issue, and how it should be addressed.

[dexX7]

I started to create very simple, almost trivial tests, but stopped quickly, as I noticed this issue became very relevant.

The tests follow the scheme:

Trade 2.00000000 MSC for 6.00000000 SPX
------------------------------------------

A offers 6.00000000 MSC for 2.00000000 SPX
B offers 2.00000000 SPX for 6.00000000 MSC

Order match and exchange of tokens expected.

Trade details and RPC output available in "standard output":

• http://bitwatch.co/uploads/omnicore-cpp_float/

---

Some more via Boost tests with plain boost::multiprecision::cpp_dec_float_100:

typedef boost::multiprecision::cpp_dec_float_100 XDOUBLE;

check XDOUBLE(1) / XDOUBLE(2) == XDOUBLE(3) / XDOUBLE(6) failed [0.5 != 0.5]
check XDOUBLE(100) / XDOUBLE(200) == XDOUBLE(120) / XDOUBLE(240) failed [0.5 != 0.5]
check XDOUBLE(6) / XDOUBLE(2) == XDOUBLE(9) / XDOUBLE(3) failed [3 != 3]
check XDOUBLE(6) / XDOUBLE(9) == XDOUBLE(2) / XDOUBLE(3) failed [0.666667 != 0.666667]

For the comparison operators using std::string was an interesting idea, but unfortunally:

check std::string("2.0") < std::string("10.0") failed [result = false]

I'm probably going to give boost::rational or boost::multiprecision::int128_t a try tomorrow..

Similar behavior was actually observed some time ago: mastercoin-MSC#198

[zathras-crypto]

This is really good data - I'm surprised at the XDOUBLE stuff, really surprised.

XDOUBLE(6) / XDOUBLE(2) != XDOUBLE(9) / XDOUBLE(3) ?!?!?!?

There was some discussion about the fit of float here (given all the rest of our math is integer based) but I honestly thought you had to get really precise before float math became an issue - to see 6/2 != 9/3 was quite an eye opener.

[dexX7]

I think the underlying issue is that the float point representation of 6/2 and 9/3 differs slightly, and this underlines why I'd prefer to use no float at all.

As it looks like, the initial plan was to convert the results into strings, but this comes at a huge price: it must be done right, e.g.:

• std::string("2") < std::string("10") => false, but
• std::string("02") < std::string("10") => true

... and it introduces a significant performance hit.

As mentioned, I'll give boost::rational a try, or use integer math directly, see:

• issues/9#issuecomment-94943784
• issues/9#issuecomment-94974809

[zathras-crypto]

Just dumping some comments from the Skype chat in here:

Patrick
I think one structural revision to Dex nuts and bolts that merits consideration is avoiding Floats entirely
whole integers where 1 = .00000001 of the currency
wasn't there an exchange that got hacked because the withdrawal field got a stack overflow? Or some other craziness due to float slippage.
Thomas
yeesh, still using floats? why? because javascript? or something fundamental to omni protocol?
yes, floats for tokens is… insane.
it was (recently) bitgo, and not a hack, but a mistake that caused 85 btc to go to a transaction fee because of vagaries of floating point arithmetic.
Patrick
I think the hack I had in mind was at BTC-e back in 2013 - hard to keep all the hacks straight.
Thomas
bitgo was this week
the point being.. yeah. use intgers (emo)
Me
Hi guys, just for clarification, all math in OmniCore is integer based, with the exception of the "unit price" for a MetaDEx trade - an entirely temporary value used for trade matching that is not stored anywhere. We are also using a special float with 100 digits of precision. However even this we are currently looking at whether is suitable - long story short nothing is set in stone for MetaDEx as yet. Hope that helps :)

FYI the bitgo stuff they're talking about got sorted because the mining pool was kind enough to return the 85 BTC processed as tx fee, but I think the moral of the story they're trying to get across is "floats are bad m'kay". As I mentioned I'm not particularly knowledgable in this area, but if a particular float calculation cannot be guaranteed to return the same result given the same input values in all systems, I also agree we can't use them.

[dexX7]

Looks like I found a sequence:

A offers 1.00000000 MDiv for 2.00000000 MSC
B offers 1.66666666 MSC  for 0.83333333 MDiv

These offers should match, but currently don't, and the comparison fails here:

// Is the desired price check satisfied? The buyer's inverse price must be larger than that of the seller.
if (pnew->inversePrice() < sellers_price) {
    file_log("SKIP: %s < %s\n", xToString(pnew->inversePrice()), xToString(sellers_price));
    continue;
}

x_Trade(mzGqKZixwgGjNhoyfYnS6vctLS6k8WseES: prop=1, desprop=3, desprice= 2.00000000000000000000000000000000000000000000000000);newo: 0.50000000000000000000000000000000000000000000000000:mzGqKZixwgGjNhoyfYnS6vctLS6k8WseES in 205/001, txid: a6877cf97c , trade #1 1.66666666 for #3 0.83333333
SKIP: 2.00000000000000000000000000000000000000000000000000 < 2.00000000000000000000000000000000000000000000000000
x_Trade()=0:NOTHING

[zathras-crypto]

These offers should match, but currently don't, and the comparison fails here:

Isn't that because
if (pnew->inversePrice() < sellers_price) {
instead of
if (pnew->inversePrice() <= sellers_price) {
?

[dexX7]

Isn't that because ...

Hehe, this is what I assumed too, but in this case it's:

inversePrice >= seller_price -> match
inversePrice <  seller_price -> no match

The issue above is indeed based on the floating numbers, and probably like 1/2 == 3/6, which should be equal, but isn't.

[zathras-crypto]

The issue above is indeed based on the floating numbers, and probably like 1/2 == 3/6, which should be equal, but isn't.

OK cool - FYI I found that if I upped DISPLAY_PRECISION_LENGTH to around 120, I started to see the actual differences in the floats.