These are chat archives for non/algebra

5th
Oct 2016
Denis Rosset
@denisrosset
Oct 05 2016 06:52
@tixxit @non, I'm quite motivated to get the ring structure correct; it is needed for the correctedness of the various GCD algorithms (I have a PR in progress for multivariate polynomials)
The current PR I have for algebra is quite big, but it's a good playground (option 1); I can as well make a smaller PR just to make the current implementations correct, and outline the impacts on Spire (option 2). Do you have time to dig deep in option 1, or should I go option 2?
Sorry to be a bit pushy; @non did a great job at rebasing Spire on top of algebra, the more we wait the more painful the merge is going to be
Oh, before I forget: the SAGE categories are a very good point of comparison, see http://doc.sagemath.org/html/en/reference/categories/index.html . They did an excellent job at encoding the mathematical structures in a programming language --- they use Python + a custom category/type system on top
P. Oscar Boykin
@johnynek
Oct 05 2016 06:59
I'm somewhat negative on the PR.
I am really nervous about euclideanFunction.
It feels like we are bolting on a lot of machinery to deal with actually two or three cases.
Denis Rosset
@denisrosset
Oct 05 2016 07:00
Great, some feedback. What do you think?
OK, agree with you. In the PR, the euclideanFunction is to support the tests. I don't feel it belong in algebra.
What I think however is that an EuclideanRing instance should be correct for some euclideanFunction, even if we don't test it with a law.
What do you think?
P. Oscar Boykin
@johnynek
Oct 05 2016 07:02
Let me look again. Not sure exactly what you mean.
Denis Rosset
@denisrosset
Oct 05 2016 07:03
The PR is quite big. I can provide a short summary here before you dig inside.
There are two definitions in "modulo" used in programming languages, with two different sets of laws.
Currently, algebra implement a quotmod operation in EuclideanRing, the current laws are correct.
On fields however, the remainder of a division is always zero, because every nonzero element has an inverse. Thus, we should force the behavior of quotmod in Field. This is required by the algebraic structure of EuclideanRings, and the correctness of e.g. polynomial algorithms depend on it.
P. Oscar Boykin
@johnynek
Oct 05 2016 07:05
We should think what algebra is about vs spire vs algebird.
Denis Rosset
@denisrosset
Oct 05 2016 07:06
Indeed. What is the equivalent of EuclideanRing in algebird?
P. Oscar Boykin
@johnynek
Oct 05 2016 07:06
To me, the pr is more about spire's domain: numerics and classical algebra
Algebird really is not focused on this. It is generally about aggregation techniques on big data.
Denis Rosset
@denisrosset
Oct 05 2016 07:07
Currently: the "quotmod" implementation for integer (Long, BigInt, ...) instances in algebra are correct. The test "Rat" instance is correct.
P. Oscar Boykin
@johnynek
Oct 05 2016 07:07
Very often using approximate/probabilistic algorithms that have monoid/group structure.
Denis Rosset
@denisrosset
Oct 05 2016 07:07
However, the BigDecimal, Float and Double instances are incorrect: as these are fields, "mod" should always return 0.
OK. Maybe the correct solution is to move EuclideanRing in Spire, and to build there a separate hierarchy including the GCD stuff.
P. Oscar Boykin
@johnynek
Oct 05 2016 07:08
Yeah, I totally agree that should be fixed. We should clarify the laws and fix the implementations
Yeah, maybe EuclideanRing should not be in algebra.
Denis Rosset
@denisrosset
Oct 05 2016 07:09
OK, I will do the following: do a minimal PR that makes the current stuff, including EuclideanRing, consistent.
P. Oscar Boykin
@johnynek
Oct 05 2016 07:09
I personally like Fields so I'd keep them.
Okay. Sounds good.
Denis Rosset
@denisrosset
Oct 05 2016 07:09
Yeah, Fields should be there.
P. Oscar Boykin
@johnynek
Oct 05 2016 07:10
By the way. I think spire is very interested in this problem of getting GCD right.
Denis Rosset
@denisrosset
Oct 05 2016 07:10
Indeed. This is the next thing on my plate.
P. Oscar Boykin
@johnynek
Oct 05 2016 07:10
Sorry for being quiet on the PR.
Denis Rosset
@denisrosset
Oct 05 2016 07:11
The only catch is that Spire cannot insert classes in the middle of the Field < ... < Ring hierarchy.
... and GCD are other beasts. While EuclideanRing seem quite unopinionated, SAGE is doing crazy things with their GCD definition on fields (as you can basically return whatever on a field)
I need to investigate the impact on polynomial algorithms
P. Oscar Boykin
@johnynek
Oct 05 2016 07:12
You could have an implicit instance given a Field.
Denis Rosset
@denisrosset
Oct 05 2016 07:12
BTW, this is hairy stuff, but to my knowledge very few libraries get this precisely done
P. Oscar Boykin
@johnynek
Oct 05 2016 07:12
Subclassing is not the only way to go.
Denis Rosset
@denisrosset
Oct 05 2016 07:12
Sure!
Thinking of it, I think EuclideanRing should be out of algebra. If we include EuclideanRing, we should implement as well the other typeclasses in the commutative ring hierarchy (principal ideal domains, unique factorization domains, GCD domains and so on). And there is a bit of wiggle room: for the factorization domains, you maybe want some freedom on the factorization algorithms (deterministic or not, exact or with a small probability of failure, and so on)
This hints at moving stuff to Spire
Waiting for @non to chime in. In the meantime, will submit a second, smaller PR --- let's keep the first one for discussion, I think it does a good job at highlighting the differences between the 2-3 species of modulo operations
P. Oscar Boykin
@johnynek
Oct 05 2016 07:17
Sounds pretty good. Gotta go now.
Denis Rosset
@denisrosset
Oct 05 2016 07:18
see you
Denis Rosset
@denisrosset
Oct 05 2016 08:05
@johnynek see #174
Erik Osheim
@non
Oct 05 2016 13:56
@denisrosset so did you and @johnynek sort of decide that removing euclidean ring from algebra makes sense? i think the changes from #174 make it work ok, but maybe it's not useful enough at this point to keep there?
Denis Rosset
@denisrosset
Oct 05 2016 14:03
@non, I'm not a maintainer of algebra, so I cannot make that decision. But I would vote in favor. If anything, truncated division should be in algebra, as it is a common operation implemented on many integer types, and also on floating point primitives.
While EuclideanRing is part of the commutative ring tower, including unique factorization domains, GCD domains... and having one piece of that tower of algebra and the rest in spire is not extremely consistent
Erik Osheim
@non
Oct 05 2016 14:14
ok, right.
Denis Rosset
@denisrosset
Oct 05 2016 14:48
Thanks for having a look while in a crazy schedule! I'm quite excited about finishing the multivariate polynomial PR after that