kalmarek commented 5 years ago

I'm moving some of my old code to AbstractAlgebra ring interface: @wbhart (or whoever did this) thanks so much for taking time to define and describe it.

It would be great if we could provide testsuite for each defined interface. Something like:

test_ring_interace_conformance(x,y) # for non-parametrized rings (x,y are two distinct elements)
test_ring_interface_conformance([x_T, y_T], [x_S, y_S]) # for parametrized rings: pairs of ring elements parametrized by T or S

wbhart commented 5 years ago

That's a great idea. I like it!

kalmarek commented 5 years ago

@wbhart have a look at first try here: https://gist.github.com/kalmarek/76b674c63b62c0d02605e7d0c1068f17

I don't really know how to test rand as it depends on the actual implementation; maybe we should ask for rand(R) that will make some standardised choices?

also:

R, x = PolynomialRing(AbstractAlgebra.JuliaZZ, "x")

test_ringinterface(x^2, x-1) # fails: promote rules return `Union{}`
test_ringinterface(big(2), big(3)) # passes
test_ringinterface(big(2.0), big(3.0)) # fails: `divexact(f, R(0))` does not throw

kalmarek commented 5 years ago

ok, the second iteration is ready; I have a few questions:

is canonical_unit(f) an element of parent(f) or base_ring(parent(f))?? e.g. canonical_unit(::Poly{BigInt}) returns a BigInt;

I'm somehow struggling with divexact[_left, _right] and AbstractAlgebra.promote_rules:

`divexact`

it is not clear from the documentation what kind of error should be thrown
moreover for Rings the documentations states

If no exact quotient exists or an impossible inverse is unavoidably encountered, an error should be thrown.

however

julia> R, x = PolynomialRing(AbstractAlgebra.JuliaZZ, "x");

julia> divexact(x^2, x-1)
x+1

looking at example implementations of divexact_left it is clear that they call divexact_left on the coefficients, which may or may not implement it:
divexact_left(f::Poly{BigInt}, parent(f)(1)) leads to StackOverflowError
divexact_left(::BigInt, ::BigInt) is aMethodError`
f = big(2.0); divexact(f, parent(f)(0)) does not throw: Inf is returned.
divexact_left, _right throw MethodError for BigFloats as well

`promote_rules`

AbstractAlgebra.promote_rule(BigInt, Int16) = Union{}
AbstractAlgebra.promote_rule(BigFloat, Int16) = Union{}

thofma commented 5 years ago

See https://github.com/Nemocas/Nemo.jl/issues/300 for the canonical_unit part. I am all in favor of returning something in the ring that we are working in. But it is quite a rabbit hole to change it.

The promote_rule business also needs some love.

wbhart commented 5 years ago

The promote_rule is explained by the following:

julia> R, x = PolynomialRing(AbstractAlgebra.JuliaZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> promote_rule(typeof(x^2), typeof(x - 1))
Union{}

julia> AbstractAlgebra.promote_rule(typeof(x^2), typeof(x - 1))
AbstractAlgebra.Generic.Poly{BigInt}

Note, we define our own promote_rule, as we cannot overload the Julia promote_rule function for a variety of reasons.

I'm not really sure that divexact should throw for bigfloats, as this wouldn't be very useful behaviour. Perhaps we just change the documentation to say that it is an exact division if the ring is exact, if not divexact(a, b) returns c such that a = bc in the given ring assuming a and b have the same precision and assuming such a value exists. (I'm not even sure that is correct, so perhaps we just change the docs to talk about exact rings, i.e. types for which isexact_type returns true).

wbhart commented 5 years ago

This is a bug:

julia> R, x = PolynomialRing(AbstractAlgebra.JuliaZZ, "x");

julia> divexact(x^2, x-1)
x+1

You can open a ticket for that.

wbhart commented 5 years ago

Regarding what kind of error should be thrown: we would use the InexactError that Julia prints, but it says something about integers could not be divided, which is useless as a general error when not working over the integers. We'll have to create our own exception for this or pressure the Julia people to change their error message. But very few errors in AbstractAlgebra are throwing specialised exceptions. Many of them just call error("Some message here").

wbhart commented 5 years ago

The divexact_left things are bugs. You can open a ticket for these,

wbhart commented 5 years ago

We don't consistently implement stuff for Int16, Int32, Int8, UInt16, etc. I'm not sure if it is really a bug. It's a waste of time to fix. The minimum Integer we should recognise is Int in my opinion. Admittedly the docs do indicate in one place that you can define an integer ring for any size integer. We probably should just change that. It's too much work to support all these cases no one will ever use, at least until someone does.

wbhart commented 5 years ago

I should point out that inexact rings are not mathematically rings. Typically associativity fails or equality is not an equivalence relation or something like that. Another case we don't always cover is non-integral domains. Mathematically it is very hard to support everything. In some cases it is theoretically possible, but no one has the energy to make it work in practice or theory.

kalmarek commented 5 years ago

@wbhart, @thofma thanks for your replies;

yes, I already use AbstractAlgebra.promote_rule in the second iteration tests (those errors for Poly{BigInt} are gone). My suggestion is to indicate in docs where does the extended method come from: e.g. zero! is from AbstractAlgebra, but mul! is not; I'd be nice if a warning banner would appear in docs just before promote_rule with the same message as is in src/AbstractTypes.jl (most people would assume it's extending Base.promote_rule).
divexact encountering an impossible inversion sounds to me more like a DomainError (and we can customize the message)
whenever docs state that a method should work for T<:Integer I test it for two opposite types on the spectrum: Int16 and (when it makes sense) for BigInt; I'm just reading docs and producing code that should work according to API ;)
i'm perfectly aware that inexact rings are not mathematical; still a test suite for (inexact) rings could be produced since I don't have to @test iszero(f-f) or @test isapprox(g+f - g, f): to check conformance it's enought to @test isequal(f, g) isa Bool.

If You can find time please have a look at the linked proposed @testset (You have much more experience implementing rings). I made some (mathematical) assumptions which might be too tight for inexact rings in general, but still PolynomialRing( ... , "x") over AbstractAlgebra.RDF fails exactly those four tests which AbstractAlgebra.ZZ does.

And its good to collect concrete topics fo discussions before June ;-)

wbhart commented 4 years ago

You mentioned that there were some failures in the tests you did write. Perhaps you could mention what these are.

I doubt that we will have time to implement interface-conformance tests before the release. But at least we should close known issues that you found (assuming they are not special cases that have to violate the interface for the time being).

wbhart commented 4 years ago

Oh, I should mention, we have plans to make the Ring interface a little lighter so it is easier to satisfy. Perhaps writing conformance tests after that time would make more sense anyway.

kalmarek commented 4 years ago

mostly undefined functions (for some reasons some people don't like to implement hash ;); divexact_left going into StackOverflow; wrong errors thrown on impossible divisions and so on; It's been a while since I touched this code (June?) as there was no will to make it usable, and I had more urging stuff to do.

wbhart commented 4 years ago

I'll do a check on Monday to see what hash functions are still not defined.

But the divexact_left I will need some more information about. What ring?

Same for impossible divisions.

kalmarek commented 4 years ago

316 #315

out of the top of my head: neither arb nor acb provide hash;

kalmarek commented 4 years ago

but to be honest: I think that AbstractAlgebra.promote_rule needs to be fixed before we release...

also https://gist.github.com/kalmarek/76b674c63b62c0d02605e7d0c1068f17 was written with the old testing framework in mind, but I don't have an idea how to make it more @testset-ish. The idea was to run the same tests for two "generic" elements of a ring to test that what we promise in the docs holds true. And this should probably be run for all rings that we construct in our tests.

@rfourquet could you have a look and suggest something?

rfourquet commented 4 years ago

@rfourquet could you have a look and suggest something?

I don't really see a problem with defining functions containing testsets, test_ringinterface(f, g) can just be called where needed at the toplevel of test files. (Or did I misunderstand your question?)

wbhart commented 4 years ago

@kalmarek Can you remind me what's wrong with AbstractAlgebra.promote_rule?

kalmarek commented 4 years ago

@rfourquet no, that was the question; those functions will need to be compiled for all types, unless we @nospecialize

@wbhart as defined now (or was in June, I don't know if there have been any changes since) it is asymmetric and will produce non-equal results depending on the order, unless special binary ops methods are defined

rfourquet commented 4 years ago

no, that was the question; those functions will need to be compiled for all types, unless we @nospecialize

@nospecialize is a good idea indeed. I guess you could also get away without defining functions, provided you don't need to call sub-functions which test only part of the interface. Then all testsets could be nested, and have a toplevel @testset "..." for (f, g) in list_of_fg ..., provided that all (f, g) pairs can be reached from a single place in the tests.

wbhart commented 4 years ago

@kalmarek That is the idea. Note that we are not overloading Julia's promote_rule here.

If you can give me an example of code that won't work because of this, we can change it. But I don't currently know that it is really broken. It was designed to be like this.

kalmarek commented 4 years ago

all points as written here https://github.com/Nemocas/AbstractAlgebra.jl/issues/324#issuecomment-499724639 stand;

including the case where generic == is not symmetric;

it works only because a) there are hand-written very specific cases of == and/or it is not thoroughly tested. Try constructing a ring parametrized by other ring where == dispatches through generic, or commenting-out the specific method.

wbhart commented 4 years ago

Ah, that discussion.

I feel that I answered it well enough and it is really too much to read through it all again.

I am not interested in making our interface design work well for Int as a parameter. If there are examples that just involve BigInt as a parameter, I'll work on fixing that. Otherwise I disagree that we need to fix things (other than possibly changing the name of our promote_rule to something_else).

If someone can come up with a different promotion system that works for all our systems better than the current one, I'll merge it. But I have no plans to work on that myself.

I still support writing interface conformance testsets, but only for actual rings. Poly{Int} is not a ring, in my humble opinion.

fieker commented 4 years ago

On Wed, Oct 02, 2019 at 05:25:09AM -0700, wbhart wrote:

Ah, that discussion.

I feel that I answered it well enough and it is really too much to read through it all again.

I am not interested in making our interface design work well for Int as a parameter. If there are examples that just involve BigInt as a parameter, I'll work on fixing that. Otherwise I disagree that we need to fix things (other than possibly changing the name of our promote_rule to something_else).

If someone can come up with a different promotion system that works for all our systems better than the current one, I'll merge it. But I have no plans to work on that myself.

I still support writing interface conformance testsets, but only for actual rings. Poly{Int} is not a ring, in my humble opinion.

It would be - if we accept that this is Z/2^64Z, in the symmetric residue system... however, while mathematically correct, it would violate the embedding into C

I'd actually also say its not a ring, cannot be a "full" ring, thus is out.

-- You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub: https://github.com/Nemocas/AbstractAlgebra.jl/issues/312#issuecomment-537468349

kalmarek commented 4 years ago

@wbhart wait, didn't you say in Saarbrucken that it is a good idea to support different type of Ints, like SafeIntegers suggested by @jmichel7 ?!

A promotion system which causes == to be asymmetric is broken by design. Currently it works only because there are ad-hoc methods defined for our rings. Yes, there is lots of text in that issue, but none of it addresses the points raised. Way too much text I'd say.

@fieker if you know (for theoretical reasons) that your polynomials/matrices etc. will fit into Int16 you can use this to your advantage as this easily may lead to 4×speed-up (or much more if counted for cache locality). And julia is one of the few languages that allows you to change that on the fly without much hassle.

So You may either be more pragmatic and benefit from smaller types, or say "it's not mathematically a ring" (but are arbs a field?) and leave performance on the table, but of course it's your choice.

wbhart commented 4 years ago

Yes, but that can be done safely.

The rest of it I'm not going to go over again.

fieker commented 4 years ago

On Wed, Oct 02, 2019 at 10:38:36PM -0700, kalmarek wrote:

@wbhart wait, didn't you say in Saarbrucken that it is a good idea to support different type of Ints, like SafeIntegers suggested by @jmichel7 ?!

A promotion system which causes == to be asymmetric is broken by design. Currently it works only because there are ad-hoc methods defined for our rings. Yes, there is lots of text in that issue, but none of it addresses the points raised. Way too much text I'd say. ... do we need to meet face to face at some point?

@fieker if you know (for theoretical reasons) that your polynomials/matrices etc. will fit into Int16 you can use this to your advantage as this easily may lead to 4×speed-up (or much more if counted for cache locality). And julia is one of the few languages Yep, I know that that allows you to change that on the fly without much hassle. That I am not too sure about

So You may either be more pragmatic and benefit from smaller types, or say "it's not mathematically a ring" (but are arbs a field?) and leave performance on the table, but of course it's your choice. Yep, and it depends on

how much work do we put in to support that/ vs work to prevent this? work to maintain this?

what should be possible/ supported?

how do we protect users/ inform users? e.g. take linear equations, for your example, over small ints. I can easily set up an example where input and output are small ints, but, depending on the algorithm, the intermediate results will overflow amd return garbage. Is this the users risk to understand? Do we need to use (maybe slow) algorithms to minimize this risk? What about det(2*I_n)? your risk? 0? BigInt(2^n)? Float(2^n)?

I fully understand the need for cache/ menory optimized data. That is why we support the dreaded nmod/ fmpz_mod things.

So how far do you want to push this support? Should this be: all risk to the user? What will be the specification?

-- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: https://github.com/Nemocas/AbstractAlgebra.jl/issues/312#issuecomment-537795477

jmichel7 commented 4 years ago

On Fri, Oct 04, 2019 at 12:51:30AM -0700, Claus Fieker wrote:

e.g. take linear equations, for your example, over small ints. I can easily set up an example where input and output are small ints, but, depending on the algorithm, the intermediate results will overflow amd return garbage. Is this the users risk to understand? Do

This is exactly the situation where SafeInt are useful...

Jean MICHEL, Groupes et representations, IMJ-PRG UMR7586 tel.(33)157279144 Bureau 639 Bat. Sophie Germain Case 7012 - 75205 PARIS Cedex 13

fieker commented 4 years ago

On Fri, Oct 04, 2019 at 01:12:51AM -0700, Jean Michel wrote:

On Fri, Oct 04, 2019 at 12:51:30AM -0700, Claus Fieker wrote:

e.g. take linear equations, for your example, over small ints. I can easily set up an example where input and output are small ints, but, depending on the algorithm, the intermediate results will overflow amd return garbage. Is this the users risk to understand? Do

This is exactly the situation where SafeInt are useful... But, while faster than fmpz/BigInt, they are slower than Int16....

Jean MICHEL, Groupes et representations, IMJ-PRG UMR7586 tel.(33)157279144 Bureau 639 Bat. Sophie Germain Case 7012 - 75205 PARIS Cedex 13

-- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: https://github.com/Nemocas/AbstractAlgebra.jl/issues/312#issuecomment-538294603

jmichel7 commented 4 years ago

On Fri, Oct 04, 2019 at 01:14:19AM -0700, Claus Fieker wrote:

This is exactly the situation where SafeInt are useful... But, while faster than fmpz/BigInt, they are slower than Int16....

The point is that they are in my experience 10 to 20% slower than Int16, which is still 50 times faster than fmpz/BigInt.

Jean MICHEL, Groupes et representations, IMJ-PRG UMR7586 tel.(33)157279144 Bureau 639 Bat. Sophie Germain Case 7012 - 75205 PARIS Cedex 13

kalmarek commented 4 years ago

@fieker I'm for providing safe defaults, but when user decides to use objects which do not form an algebraic structure (Ints, arbs) to model computations in mathematical ideal object he/she needs to understand what is happening. And especially when squeezing the last bits of performance we can relax some safeguards, as only the advanced users will venture there.

So how far do you want to push this support?

An ideal situation would be to take pm_Integers, or SafeInt128, or WhateverInt and plug it into perms, polynomials and whatnot from Generic. It's supposed to be generic code, right? I fully second @jmichel7 point about usefulness and speed of SafeInts but if we decide go the (figurative) mile to support them, there is little reason not to go additional meter to support anything that subtypes Integer. This usually requires just a little bit more consideration when writing code (and of course no assumptions on the concrete type of Integers). I tried to write Perms so that PermGroup(SafeInt(50)) should work and pass all the tests out of the box. If it doesn't I consider this a bug (and will fix it). And there's not much more code to make it work, really. The rule of thumb is that if it works type-stably for UInt16 and BigInts it should work for all integers.

G = PermGroup(SafeInt(40)); 
A = [rand(G) for _ in 1:10]; # rand(G, 10) on master, array of `Perm{SafeInt}`s
let A = deepcopy(A)
    prod(order.(A)) # BigInt as `order` easily overflows
end
let A = deepcopy(A)
    prod(order.(SafeInt, A)) # SafeInt, usually overflows
end
let A = deepcopy(A)
    prod(order.(SafeInt128, A)) # SafeInt128, should be sufficient
end

yts = YoungTableau.(permtype.(A));
dim.(yts) # Array of BigInts
for yt in yts
    @show dim(SafeInt128, yt) # this will probably overflow for one of perms
end

... do we need to meet face to face at some point?

It would be much easier to discuss this in person, definitely, but given that Bill said that he is not tackling the issue before the release, let's postpone this until after the first release. Maybe we can schedule this for the next meeting and ask @rfourquet to join the discussion as by then he will have the fullest view of both julia and AA worlds.

wbhart commented 4 years ago

@kalmarek I literally have no idea how you could make the generic code safe for Int's without checking for overflows everywhere? And how would one do that in generic code? And what advantage would there be over using SafeInt's in the first place?

Do you have any idea just how much generic code there is now? This is a job that would never be finished. We just don't have the resources to be doing something like this.

If I put any time into something like this, I would put time into the linear algebra in Flint and make it (provably) use machine words where possible, with a fallback to fmpz's when there can be an overflow (I started work on this after learning that Normaliz does this heuristically with no proof of correctness). But just that task right there is already months of work for someone!!

On a related topic: you still didn't explain what promote_rule should return for BigInt and Poly{Int}. BigInt or Poly{Int}? Again, this is "complex coercion", which we are not supporting.

It's only possible to support rings in which there is a canonical (and safe) coercion from a safe model of the integers (e.g. from BigInt). This is not the case for Int, but it is the case for SafeInt (assuming you are prepared to raise an exception on overflow).

If you really believe you can implement a symmetric promote_rule system which works for all the cases that the current promote_rule system works, be my guest. But I claim it is nontrivial if you don't want to introduce Julia ambiguities that will drive everyone insane. Bear in mind we had a symmetric system before I changed it, to work around deficiencies in the existing system!

But if you think you can do better, I look forward to the PR.

And if you really believe you can safely support Int parameters in all our generic code without polluting it with zillions of overflow checks, I very much look forward to the PR.

But let me emphasise this so it's clear: I am not working on any of these things! I have far too much other important work to do. I cannot take a year out of Oscar development to support this stuff which would have marginal usefulness over say further speeding up Flint with word sized arithmetic where possible.

wbhart commented 4 years ago

Something that I should also stress is that we MUST release Oscar version 1.0 before the end of the year. That's a little over 2 months away, and we still have zero documentation, zero code to convert between all the types of the different systems and few mathematical examples to show off its usefulness. All of that MUST be delivered by the end of the year at the latest, with no possibility of extension! We still can't even build the system quickly on OSX (e.g. Singular.jl and Gap.jl).

@kalmarek How is it that you can even countenance some of the stuff you are suggesting? Don't you also have pressing research deadlines and projects you are involved with?

kalmarek commented 4 years ago

@wbhart I wrote:

let's postpone this until after the first release.

I mention those issues because I care, and not because I criticize You or someone else. I'm sorry if You felt like this. But if this is the response I might as well stop caring.

wbhart commented 4 years ago

@kalmarek This has nothing to do with me thinking I am being criticised, or anything personal, for that matter. It is about me not understanding why you keep suggesting to do things which seem more or less impossible, especially given the resources we have.

I've tried to explain why it would be hard, and I would welcome being proven wrong. But I can't keep going over the same issues. I don't believe it is possible to do what you want.

As I said before, I welcome interface conformance testsets. These would be very useful, and certainly possible, so long as they are reasonable. In particular, they have to test actual rings, and moreover, ones that we actually implement. This would already be of great benefit over what we have. I understand that you don't have time to implement them right now. Nor do I, and I would expect that no one does, due to the tight deadlines we are all under. So let's do it at some later date when one of us has the time.

fieker commented 4 years ago

On Sun, Oct 06, 2019 at 03:19:04PM -0700, kalmarek wrote:

@fieker I'm for providing safe defaults, but when user decides to use objects which do not form an algebraic structure (Ints, arbs) to model computations in mathematical ideal object he/she needs to understand what is happening. And especially when squeezing the last bits of performance we can relax some safeguards, as only the advanced users will venture there.

I guess my main problem is that I, as the author of a lot of the code, cannot predict what will happen if an overflow occurs - and when this is going to happen. I do not mind allowing different Int types, but predict that past 'trivial' stuff it will be difficult to use as you need to assume properties of the ring (like being a ring). Stupid point in case: given a set of (small) primes p_i and a (small) integer n, how do you factor the integer over the given primes (or show this cannot work)? a: for each prime p, compute the valuation and remove it. If the end result is 1, it worked. This would be small int-type-stable b: you compute gcd's of n and products of the primes and remove the products This is, asymptoticalluy and practically much faster, especially if you need to test a large number of integers. However, this cannot work in restricted ints...

Do you expect the documentation to spell out that intermediate results can be larger than the result or the input? Do you expect, in AA, to only see the 1st version? Or to code in such a way that internally BigInt can be used and translations happen?

I see the speed differential and hope there is some way of getting close to this with fmpz's (or BigInt's) and still using + (and not add(a,b,c)) although I do not have big hopes. Last time I checked the speed is due to llvm support for bit-types (primitive types)...

However, me, personally, have been burned too frequently by assuming some integer can never be large and thus using Int instead of the fmpz equivalent (in the magma kernel). This usually backfired a year later.

So to me two questions

how much work will it be to support
will it hurt in the long run (due to people not understanding the overflow) or will it hurt to not support that?

So how far do you want to push this support?

An ideal situation would be to take pm_Integers, or SafeInt128, or WhateverInt and plug it into perms, polynomials and whatnot from Generic. It's supposed to be generic code, right? Well, yes, but mathematically, for integers, not for Z/2^nZ. Mathematically, I can (and have) design algorithms for Z/2^nZ which are fast, correct, useful. However to understand when the results are meaningful when lifted to Z is sometimes difficult...

I fully second @jmichel7 point about usefulness and speed of SafeInts but if we decide go the (figurative) mile to support them, there is little reason not to go additional meter to support anything that subtypes Integer. This usually requires just a little bit more consideration when writing code (and of course no assumptions on the concrete type of Integers). Well.... it requires to stick to trivial algorithms to be predictable... or to be lucky. I tried to write Perms so that PermGroup(SafeInt(50)) should work and pass all the tests out of the box. If it doesn't I consider this a bug (and will fix it). And there's not much more code to make it work, really. The rule of thumb is that if it works type-stably for UInt16 and BigInts it should work for all integers.

I guess my concerns are
the additional work to allow this (should be much, I fully agree)
the back-lash when the results, due to overflow and zero divisors, are totally garbage
G = PermGroup(SafeInt(40)); 
A = [rand(G) for _ in 1:10]; # rand(G, 10) on master, array of `Perm{SafeInt}`s
let A = deepcopy(A)
prod(order.(A)) # BigInt as `order` easily overflows
end
let A = deepcopy(A)
prod(order.(SafeInt, A)) # SafeInt, usually overflows
end
let A = deepcopy(A)
prod(order.(SafeInt128, A)) # SafeInt128, should be sufficient
end
yts = YoungTableau.(permtype.(A)); dim.(yts) # Array of BigInts for yt in yts @show dim(SafeInt128, yt) # this will probably overflow for one of perms end
> ... do we need to meet face to face at some point?

It would be much easier to discuss this in person, definitely, but given that Bill said that he is not tackling the issue before the release, let's postpone this until after the first release. Maybe we can schedule this for the next meeting and ask @rfourquet to join the discussion as by then he will have the fullest view of both julia and AA worlds.

ahh well, we are planning to meet for perms anyway...

-- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: https://github.com/Nemocas/AbstractAlgebra.jl/issues/312#issuecomment-538793718

fieker commented 4 years ago

On Sun, Oct 06, 2019 at 04:27:35PM -0700, wbhart wrote:

Something that I should also stress is that we MUST release Oscar version 1.0 before the end of the year. That's a little over 2 months away, and we still have zero documentation, zero code to convert between all the types of the different systems and few mathematical examples to show off its usefulness. All of that MUST be delivered by the end of the year at the latest, with no possibility of extension! We still can't even build the system quickly on OSX (e.g. Singular.jl and Gap.jl).

@kalmarek How is it that you can even countenance some of the stuff you are suggesting? Don't you also have pressing research deadlines and projects you are involved with?

Bill, no-one asks you to do anyhting about this, in particularly, at this point. We have other things to do currently. However: a background discussion about allowing others to do this cannot harm. I find technical discussions about the technical feasibility always dangerous - half of the time the result is wrong anyway. We established that

doing this is technically difficult
has interesting pitfalls
potentially huge advantages
and equally big problems unless s.o. does the "work" neccessary to demonstrate that this is possible AND unless we decide that the risk is too large (to piss people of with wrong results) or to piss people off (by being unneccessarily slow), this cannot be settled. There is always the compromise betwen the expert ("I know what I am doing, why is this not allowed?") and the beginner ("This is wrong, why was I allowed to do this?"). In either case: ... but it was documented... will not retain users.

However, it is also clear, that whatever changes to promote, ... are being made, they need to be made and tested all through Oscar, ie. not only to AA, but also to Nemo Hecke Polymake Gap Singular

-- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: https://github.com/Nemocas/AbstractAlgebra.jl/issues/312#issuecomment-538799230

fieker commented 4 years ago

On Sun, Oct 06, 2019 at 03:19:04PM -0700, kalmarek wrote:

@fieker I'm for providing safe defaults, but when user decides to use objects which do not form an algebraic structure (Ints, arbs) to model computations in mathematical ideal object he/she needs to understand what is happening. And especially when squeezing the last bits of performance we can relax some safeguards, as only the advanced users will venture there.

So how far do you want to push this support?

An ideal situation would be to take pm_Integers, or SafeInt128, or WhateverInt and plug it into perms, polynomials and whatnot from Generic. It's supposed to be generic code, right? I fully second @jmichel7 point about usefulness and speed of SafeInts but if we decide go the (figurative) mile to support them, there is little reason not to go additional meter to support anything that subtypes Integer. This usually requires just a little bit more consideration when writing code (and of course no assumptions on the concrete type of Integers). I tried to write Perms so that PermGroup(SafeInt(50)) should work and pass all the tests out of the box. If it doesn't I consider this a bug (and will fix it). And there's not much more code to make it work, really. The rule of thumb is that if it works type-stably for UInt16 and BigInts it should work for all integers.
G = PermGroup(SafeInt(40)); 
A = [rand(G) for _ in 1:10]; # rand(G, 10) on master, array of `Perm{SafeInt}`s
let A = deepcopy(A)
    prod(order.(A)) # BigInt as `order` easily overflows
end
let A = deepcopy(A)
    prod(order.(SafeInt, A)) # SafeInt, usually overflows
end
let A = deepcopy(A)
    prod(order.(SafeInt128, A)) # SafeInt128, should be sufficient
end

I can easily see why you did this, but unless there is a generic way to
"switch" the default type of order away from BigInt, this is also a
vendor lock-in.
I'd actually had expected the return type of order then to be the type
of the group elems...
I do see all of this as difficult. In principal, julia seems to offer
big(x) to convert to the overflow-safe-type. However, I don't seem to be
able to make fmpz the safe-int type...

The difference between fmpz and BigInt is, of course, negliable for large contents (both use gmp), however for BigInt containing small integers, fmpz will be much faster, it should approach the speed of Int (when used with the add(a,b,c) interface intelligently, not when used via + in Julia directly)

And, given Nemo and Flint, we cannot use BigInt in any serious way... Life sucks.

yts = YoungTableau.(permtype.(A)); dim.(yts) # Array of BigInts for yt in yts @show dim(SafeInt128, yt) # this will probably overflow for one of perms end



> ... do we need to meet face to face at some point?

It would be much easier to discuss this in person, definitely, but given that Bill said that he is not tackling the issue before the release, let's postpone this until after the first release. Maybe we can schedule this for the next meeting and ask @rfourquet to join the discussion as by then he will have the fullest view of both julia and AA worlds.

-- 
You are receiving this because you were mentioned.
Reply to this email directly or view it on GitHub:
https://github.com/Nemocas/AbstractAlgebra.jl/issues/312#issuecomment-538793718

kalmarek commented 4 years ago

@fieker about the returned type by dim, order: yes, we had a discussion (with @thofma, if I remember correctly?!) when I worked on this code and this was the solution we came up with, as one of the reasonable things to do. Problem with returning the integer of type defining PermGroup was that you couldn't compute order(PermGroup(Int8(7))), those pesky small Ints are really small... ;)

by safe defaults I mean that e.g. our ZZ is true integer and this is what user will see, and it's a completely ok.

Do you expect the documentation to spell out that intermediate results can be larger than the result or the input? Do you expect, in AA, to only see the 1st version? Or to code in such a way that internally BigInt can be used and translations happen?

1) I don't expect, but it would be definitely user friendly, especially if overflow is likely even for middle-size numbers; 2) this is very much function dependent; e.g. in dim we made the decision that the operation will likely overflow, therefore we provide the one that works. Case in point: factorial vs. ^; the first throws, as overflow is very likely, the second silently overflows. And of course I'd try my best to provide one that will work with user supplied (safe or not, ringy or not) types.

I think that the policy of not overflowing at any cost is somehow defeating the purpose of generic functions, as even a function that doubles its argument mus pass through BigInt: f(x:T) where T = ( y::T = 2big(x); y). And I understand that we probably care more about correctness than average julia and I'd have nothing against e.g. making AA.zz defaulting to SafeInts to avoid accidental overflows, but this is an issue I am very much disinterested in.

In Oscar alone there are already four types of mathematical Integers: BigInts, fmpzs, pm_Integers and n_Zs from Singular. sooner or later somebody will write GAPInts as well and it's only natural, that when Polymake gives You an array of its integers you call perm on it and Your algorithm runs further. And it's good to be prepared for this, even though we will not be able predict all the possible interactions between components.

ahh well, we are planning to meet for perms anyway

I'd prefer not to bring the actual issue which, if somebody still remembers ;), is the conformance testing (and the asymmetry of generic == for Rings) during the groups meeting and rather postpone it until the next year, at the request of @wbhart

fieker commented 4 years ago

On Mon, Oct 07, 2019 at 12:48:27PM -0700, kalmarek wrote:

@fieker about the returned type by dim, order: yes, we had a discussion (with @thofma, if I remember correctly?!) when I worked on this code and this was the solution we came up with, as one of the reasonable things to do. Problem with returning the integer of type defining PermGroup was that you couldn't compute order(PermGroup(Int8(7))), those pesky small Ints are really small... ;)

by safe defaults I mean that e.g. our ZZ is true integer and this is what user will see, and it's a completely ok.

Do you expect the documentation to spell out that intermediate results can be larger than the result or the input? Do you expect, in AA, to only see the 1st version? Or to code in such a way that internally BigInt can be used and translations happen?

1) I don't expect, but it would be definitely user friendly, especially if overflow is likely even for middle-size numbers; likely is always hard... 2) this is very much function dependent; e.g. in dim we made the decision that the operation will likely overflow, therefore we provide the one that works. Case in point: factorial vs. ^; the first throws, as overflow is very likely, the second silently overflows. And of course I'd try my best to provide one that will work with user supplied (safe or not, ringy or not) types.

I think that the policy of not overflowing at any cost is somehow defeating the purpose of generic functions, as even a function that Agreed doubles its argument mus pass through BigInt: f(x:T) where T = ( y::T = 2big(x); y). And I understand that we probably care more about correctness than average julia and I'd have nothing against e.g. Yep, I see this a numerics vs. symbolics. making AA.zz defaulting to SafeInts to avoid accidental overflows, but this is an issue I am very much disinterested in.

In Oscar alone there are already four types of mathematical Integers: BigInts, fmpzs, pm_Integers and n_Zs from Singular. sooner or later somebody will write GAPInts as well and it's only natural, that when Polymake gives You an array of its integers you call perm on it and Your algorithm runs further. And it's good to be prepared for this, even though we will not be able predict all the possible interactions between components. However, at least my plan is, to avoid that "users" need to know this: on the oscar top-level all is going to be Int or fmpz, with conversion. This will not prevent a power user (you) to use the interface layer depper down and do differnt things. Note, that we also "promised" to sanitize our data types so that, eventually, fmpz = GapInt = SingularInt = PolymakeInt...

ahh well, we are planning to meet for perms anyway

I'd prefer not to bring the actual issue which, if somebody still remembers ;), is the conformance testing (and the asymmetry of generic == for Rings) during the groups meeting and rather postpone it until the next year, at the request of @wbhart OK

-- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: https://github.com/Nemocas/AbstractAlgebra.jl/issues/312#issuecomment-539174553

Nemocas / AbstractAlgebra.jl

provide interface-conformance testsets #312

`divexact`

`promote_rules`

316 #315

This is exactly the situation where SafeInt are useful...

This is exactly the situation where SafeInt are useful... But, while faster than fmpz/BigInt, they are slower than Int16....

The point is that they are in my experience 10 to 20% slower than Int16, which is still 50 times faster than fmpz/BigInt.