Error: 0.1 + 0.1 == 2

[chexxor]

> import Data.HugeNum
> let x = fromNumber 0.1
> let y = fromNumber 0.1
> x + y
HugeNum 2.0

Looks like the addPlusPlus function is the source of the error, but I haven't figured out which part of it is the problem. At first glance, it seems the digits name should be (Digit 0 : Digit 2 : Nil), so the decimal value of 1 will put the decimal point after the first 0. Or perhaps the decimal name should be 0 instead of 1?

  r = L.zip (L.reverse r1.digits) (L.reverse r2.digits)
  -- r = ((Tuple Digit 1 Digit 1) : (Tuple Digit 0 Digit 0) : Nil)
  digits'' = foldl digitwiseAdd (Tuple mempty _zero) r
  -- digits'' = (Tuple (Digit 0 : Digit 2 : Nil) Digit 0)                                         
  spill = snd digits''
  -- spill = Digit 0
  digits' = fst digits''
  -- digits' = (Digit 0 : Digit 2 : Nil)
  digits = unsafeRemoveFrontZeroes $ spill : digits'
  -- digits = (Digit 2 : Nil)
  decimal = adjustDecimalForFrontZeroes (spill : digits') (r1.decimal + 1)
  -- decimal = 1
  z = { digits: digits, decimal: decimal, sign: Plus }

I wonder why the tests didn't catch this, as it seems like a pretty basic problem. I imagine the checkRing test would catch this, no?

[garyb]

I wonder why the tests didn't catch this, as it seems like a pretty basic problem.

Looks like the Arbitrary instance is only generating integers: https://github.com/purescript-contrib/purescript-precise/blob/a938279b28ad0de6deefc98380d7a61b452ddab8/src/Data/HugeNum.purs#L58-L59

[garyb]

Ah, that's because it's really slow at running the tests if you don't.

[garyb]

Truncating the random decimal digits to 2(ish)

instance arbHugeNum :: Arbitrary HugeNum where
  arbitrary = do
    i <- Int.toNumber <$> chooseInt 0 1000
    d <- Int.toNumber <$> chooseInt 0 10
    pure $ fromNumber (i + d / 10.0)

Means they run acceptably, and do fail now.

[garyb]

Actually the law tests aren't failing due to addition, it's multiplication that's making them fail. It might well be that it is law abiding in addition even if it's not the expected value.

But anyway, this works for 0.1 + 0.1 = 0.2:

  z = { digits: adjustDigitsForDecimal decimal digits, decimal: decimal, sign: Plus }

adjustDigitsForDecimal :: Int -> List Digit -> List Digit
adjustDigitsForDecimal decimal digits = go (decimal - L.length digits + 1) digits
  where
  go n ds
    | n <= 0 = ds
    | otherwise = go (n - 1) (_zero : ds)

It seems like unsafeRemoveFrontZeroes is overzealous and needs to know about decimal so as not to remove too many, or something.

But multiplication is broken.

[chexxor]

Nice!

To do:

• Verify the addition fix you created works for more edge-cases. (Gary said in chat that we should probably add some test cases that convert to and from numbers - will have to use an epsilon for comparing with numbers, but should be possible to give us a better idea as to whether it actually works as intended or not.

• Discover example inputs which cause the multiplication laws to fail. The law that multiplication is failing on means that (a * b) * c /= a * (b * c) fails in about 10% of the test cases it's running. We can fix it after we discover the problem and test cases.

[chexxor]

I wrote a short function which gave me values of a, b, and c which cause the associativity law to fail. Here's a short set of combinations of these values:

a=HugeNum 224.5 b=HugeNum 895.8 c=HugeNum 130.1
a=HugeNum 989.5 b=HugeNum 961.6 c=HugeNum 543.2
a=HugeNum 866.5 b=HugeNum 872.2 c=HugeNum 561.7
a=HugeNum 996.8 b=HugeNum 416.5 c=HugeNum 581.1
a=HugeNum 695.1 b=HugeNum 253.5 c=HugeNum 802.2
a=HugeNum 922.0 b=HugeNum 799.5 c=HugeNum 523.6
a=HugeNum 464.5 b=HugeNum 782.6 c=HugeNum 654.1
a=HugeNum 911.4 b=HugeNum 888.4 c=HugeNum 966.5
a=HugeNum 551.8 b=HugeNum 238.5 c=HugeNum 413.7

It seems the problem isn't associativity, it is the state of the HugeNum value created by the multiplication operation. My initial guess it is caused by producing a value having decimal places ending in zero. Note that the correct value for this expression is 26,164,033.71.

> (fromNumber 224.5 * fromNumber 895.8) * fromNumber 130.1 -- == HugeNum 261,640,337.10
-- Evaluates to
 HugeNum 201107.10 * HugeNum 130.1 -- == HugeNum 261,640,337.10 (wrong)
-- Interestingly
> (fromNumber 201107.10) * (fromNumber 130.1) -- == HugeNum 26164033.71 (right)

Here's what happens when we follow the first set of values through the times function.

• Enter the second guard
• adjustDecimalForTriviality r1 r2 $ times (makeHugeInteger r1) (makeHugeInteger r2).
• adjustDecimalForTriviality r1 r2 $ fromNumber 20110710.0 -- further evaluated
• Enter the adjustDecimalForTriviality function.

  digitsLength = L.length r3.digits - 1
  --digitsLength == 8
  digits' = L.take digitsLength r3.digits -- r3 is always an integer-like representation of h1 * h2
  --digits == (Digit 2 : Digit 0 : Digit 1 : Digit 1 : Digit 0 : Digit 7 : Digit 1 : Digit 0 : Nil)
  decimalMod = meatyDecimals h1 + meatyDecimals h2
  --decimalMod == 2
  digits = replicate (decimalMod - digitsLength + 1) _zero <> digits'
  --digits == (Digit 2 : Digit 0 : Digit 1 : Digit 1 : Digit 0 : Digit 7 : Digit 1 : Digit 0 : Nil)
  decimal = L.length $ L.drop decimalMod $ L.reverse digits
  --decimal == 6
  sign = Plus
  r = { digits, decimal, sign }

The extra zero on the end is the mistake, I believe. It seems like HugeNum's digit field can't have a trailing zero. In fact, I found a doc at the top which supports this belief:

-- | ##Type definitions
-- | Well-formed HugeNums are such that the decimal is a positive number less
-- | than the length of the list of digits. For example, to denote the integer
-- | 2, we would set `sign = Plus, digits = 2 : 0 : Nil, decimal = 1`.
-- | Any extraneous 0's on either end of the list of digits should be trimmed.

I managed to fix the multiplication associativity errors by making this patch:

- digits = replicate (decimalMod - digitsLength + 1) _zero <> digits'
+ digits = takeMeatyParts $ replicate (decimalMod - digitsLength + 1) _zero <> digits'

Now we've hit a new test error, this time the error lies in the "'Left Distribution' law of Semiring", which is a * (b + c) == (a * b) + (a * c). It's very possible this leading-or-trailing zeros issue is the source of this new problem, as well.

[garyb]

Nice work! I suspect you're right that the next problem might be another case of too many or too few zeros, since that's been the culprit so far and seems like the easiest bit to get slightly wrong in the algorithms involved here.

[chexxor]

I believe I fixed the issues, because pulp test is successful with this patch: https://github.com/purescript-contrib/purescript-precise/pull/5

In my previous comment, I introduced the wrong solution, which caused the "left distribution" law to fail. The correct solution was to adjust the zeroes after the HugeNum had been created, not during. times (fromNumber 987.5) (fromNumber 237.6) is an example which caused my first attempted solution to fail, as it produced "HugeNum 234630.00"