search

typelevel / algebra

Experimental project to lay out basic algebra type classes
https://typelevel.org/algebra/
Other
378 stars 69 forks source link

Add instances for BigDecimal and BitSet. #166

Closed non closed 8 years ago

non commented 8 years ago

This commit also adds a static method for computing GCDs of BigDecimal values (ported from Spire), and standardizes the methods used in the set instances.

tixxit commented 8 years ago

One thing about this is that the actual way we calculate GCD for floating point number is by treating them like rational numbers. I gave a justification in my original PR to Spire:

This makes GCD for rationals match up with Mathematica. The GCD of 2 rational numbers p/q and r/s is gcd(ps, rq) / (q * s). This PR implements this for Rational, Float, Double, and BigDecimal, though being careful to be more efficient.

I wonder if it's worth adding to the docs somewhere, so we can sort of explain the behaviour, since the GCD can basically be anything otherwise for these numbers.

johnynek commented 8 years ago

:+1: but we should add an issue to track code coverage and specifically to add tests here. Since this comes from Spire rather than de novo, I'm not as worried.

johnynek commented 8 years ago

I can't find any trait with Gcd (I'm on my phone). Am I missing it? Is there no law we have for the expectation of gcd? Or is any law too weak to be a full specification?

non commented 8 years ago

@johnynek We have laws for GCD/LCM in spire -- I'll add relevant tests/laws to this PR before we merge it.

There is even a TODO in the laws for EuclideanRing, so I can also add those while I'm at it.

non commented 8 years ago

Oh! It seems like we removed gcd and lcm from the type classes at some point, but just hadn't removed all those methods. I'll amend this to remove them (and add tests for quot and mod too).

non commented 8 years ago

OK -- I think this addresses @johnynek's concerns (we've removed everything GCD-related, added other tests, and removed some unsafe instances we caught with the new tests). It's a bit more of a compatibility break than before but I think it's worth it!

non commented 8 years ago

Wait -- I need to do a few more things.

johnynek commented 8 years ago

👍 just a minor request for a comment.

tixxit commented 8 years ago

👍

non commented 8 years ago

Alright, I added the comment for @johnynek and I also made sure to mix the new implicit instances into the AllIntances trait. Finally, I enabled the law-checking tests for these two new types (in the case of BigDecimal it's slightly fake, as you'll see, but that's normal in this space).

johnynek commented 8 years ago 
[info] - [BigDecimal].euclidean ring.distributive *** FAILED ***
[info]   GeneratorDrivenPropertyCheckFailedException was thrown during property evaluation.
[info]    (algebra-laws-test-fastopt.js:35722)
[info]     Falsified after 87 successful property evaluations.
[info]     Location: (algebra-laws-test-fastopt.js:35722)
[info]     Occurred when passed generated values (
[info]       arg0 = -2147483648,
[info]       arg1 = -2147483648,
[info]       arg2 = -2147483648
[info]     )
[info]     Label of failing property:
[info]       (-9223372036854775808 ?== 9223372036854775808) failed
johnynek commented 8 years ago

that's weird. Is this a bug with BigDecimal on scala-js?

non commented 8 years ago

@johnynek It sort of looks that way to me. I went ahead and downgraded the test to _.ring for now, since that is a known-flaky test anyway.

non commented 8 years ago

OK, well after finding (and reporting) a Scala.js bug [1] it looks like we're finally green again.

[1] https://github.com/scala-js/scala-js/issues/2587