divrem in Julia is now defined differently to in Nemo

[wbhart]

We probably need to define divmod and use it everywhere.

[thofma]

What to do you mean by "now"? I did not observe a change to divrem in julia.

[wbhart]

I actually have no memory of writing this (though clearly I did).

But I assume divrem is defined as per rem, i.e. the % operator in C, which does not give the positive modulus, as we define it in Nemo. Therefore if you have negative values, divrem with Nemo ZZ will give a different answer than if you use BigInt's in Julia. This means AA will give a different answer to Nemo.

[thofma]

I cannot follow. They give the same answer. Do you have an example?

[wbhart]

Yes, they do. But they really shouldn't. I didn't realise this. divrem(-3, 5) in Nemo currently returns (0, -3), but it should clearly return (-1, 2). This is a very strange definition of Euclidean division, otherwise.

[wbhart]

I guess what I mean is, when we type divrem, we currently mean Euclidean division. But Julia does not give that. Therefore, we should instead use divmod in Nemo and make it return the right thing, instead of what Julia (and apparently Nemo), currently return.

[thofma]

I don't see the problem. We currently have divrem(x, y) = div(x, y), rem(x, y) for Int, BigInt and fmpz. What we return is a valid Euclidean divsion. I don't see the point of changing rem and introducing yet another function for division.

[wbhart]

I wasn't suggesting that we change rem or divrem. They should agree with Julia. But I don't believe this is consistent. mod(2, 5) should return the same thing as mod(-3, 5), same for divmod. Otherwise it is not very mathematically useful.

[thofma]

Sorry, yes there would be not change to rem.

Currently mod(2, 5) and mod(-3, 5) return the same result.

[wbhart]

That's good, but we don't have divmod, or at least we don't use it when doing Euclidean division. This means we may end up with bugs in code due to inconsistent results, because we use divrem everywhere. Of course this means we would also need to change divrem to divmod everywhere when doing Euclidean division of polynomials, etc. It's a bit of a pain, but probably easier to do now, whilst Nemo, Hecke, AbstractAlgebra, etc., are not enormous. What do you think?

[thofma]

What should divmod(x, y) = q, r be? r == mod(x, y) and x == q*y + r?

…

On Wed, Sep 12, 2018, 21:42 wbhart ***@***.***> wrote: That's good, but we don't have divmod, or at least we don't use it when doing Euclidean division. This means we may end up with bugs in code due to inconsistent results, because we use divrem everywhere. Of course this means we would also need to change divrem to divmod everywhere when doing Euclidean division of polynomials, etc. It's a bit of a pain, but probably easier to do now, whilst Nemo, Hecke, AbstractAlgebra, etc., are not enormous. What do you think? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#101 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AKthoDHpD7RfKr2_D9ZFBwTSAKVDbKx0ks5uaQ8tgaJpZM4UggK3> .

[wbhart]

On Wed, 12 Sep 2018 at 15:46, thofma ***@***.***> wrote: What should divmod(x, y) = q, r be? r == mod(x, y) and x == q*y + r?

Natürlich

[thofma]

I think we have been bitten by this before (divrem not yielding something positive as the second argument) and I see how divmod would help with this. I would like to hear what @fieker thinks.

So the proposal is to introduce divmod, which would be the same as divrem for polynomial rings, but would always return a positive remainder for integers.

[fieker]

To me, divrem and divmod are mostly irrelevant as I mostly deal with % I hate the existence of those 2 variations as there is no logic, accessible to outsiders, to explain what's what and why. I'd probable prefer mod_sym, mod_pos (or rem_...) or s.th. similar that explains intrinsically what is happening. I assume that almost everyone will at least start with % as this is conveninent and available. My problem with divrem/ divmod is that in Julia Base is/was a dependency: generically divrem is/ was implemented in terms of div and rem Whereas we'd implement div via divrem... % is mapped to rem? I expect the bizarre distinction between mod and rem to come back and bite us via user complaints. Thus I'd probably do mod=rem and produce the mod_pos, mod_sym if this is important (and/ or rem_pos, rem_sym) My thoughts...

…

On Wed, Sep 12, 2018 at 08:42:17PM -0700, thofma wrote: I think we have been bitten by this before (divrem not yielding something positive as the second argument) and I see how divmod would help with this. I would like to hear what @fieker thinks. So the proposal is to introduce divmod, which would be the same as divrem for polynomial rings, but would always return a positive remainder for integers. -- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: #101 (comment)

[thofma]

I just did some more testing and searching and here is what I found out.

1. Let's first look at %, mod and rem. There is no way we can be consistent with julia:

• julias mod is not the same as our mod: mod(x, y) will always have the same sign as y, that is,
  mod(1, -2) = -1. On the other hand, for fmpz mod(x, y) is always positive.
• % is just an alias for rem.

2. More worrying is the following: Very often one needs a div(x, y) such that x - div(x, y) * y = mod(x, y). Think for example of reduction of a row in the Hermite form algorithm. At the moment, div(x, y) and divrem(x, y) won't give you such a division. Consequently you will find something like https://github.com/thofma/Hecke.jl/blob/c3e395397d4a5d890446b40ef477e85870fab793/src/Sparse/HNF.jl#L369-L374

I don't see a clear way forward. I don't mind too much about 1), but 2) is very annoying.

[wbhart]

We could get around 2 by demanding that mod take a positive modulus. We would simply not define our mod for negative modulus.

[wbhart]

Sorry, I mean the second part of one, not 2.

[fieker]

What abut having q, r = quotrem(a,b) s.th. a = qb+r and r = rem(a, b) q, r = divmod(a,b) s.th. q = qb+r and r = mod(a, b)? divmod/ quotrem is nothing that a normal person would find or expect, but they do, it is compatible. Feel free to have different ideas about the names... There is also invmod and powmod which should acually be invrem and powrem for fmpz.... julia> invmod(-1, -7) -1 julia> invmod(fmpz(-1), fmpz(-7)) ERROR: DomainError with Modulus must be non-negative: -7: julia> rem(-1, -7) -1 julia> mod(-1, -7) -1 julia> rem(fmpz(-1), fmpz(-7)) -1 julia> mod(fmpz(-1), fmpz(-7)) 6 julia> rem(BigInt(-1), BigInt(-7)) -1 julia> mod(BigInt(-1), BigInt(-7)) -1 at least if fmpz should be like BigInt... I guess we can never achieve identical behaviour to core julia here. Where do we stop? For all other euclidean rings, *mod = *rem? More of a problem is the decision of % = rem or mod and the problem that Julia has it as rem, but for BigInt it behaves like mod...

…

On Thu, Sep 13, 2018 at 02:17:32AM -0700, thofma wrote: I just did some more testing and searching and here is what I found out. 1) Let's first look at `%`, `mod` and `rem`. There is no way we can be consistent with julia: - julias mod is not the same as our mod: mod(x, y) will always have the same sign as y, that is, mod(1, -2) = -1. On the other hand, for fmpz mod(x, y) is always positive. - % is just an alias for rem. 2) More worrying is the following: Very often one needs a div(x, y) such that x - div(x, y) * y = mod(x, y). Think for example of reduction of a row in the Hermite form algorithm. At the moment, div(x, y) and divrem(x, y) won't give you such a division. Consequently you will find something like https://github.com/thofma/Hecke.jl/blob/c3e395397d4a5d890446b40ef477e85870fab793/src/Sparse/HNF.jl#L369-L374 I don't see a clear way forward. I don't mind too much about 1), but 2) is very annoying. -- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: #101 (comment)

[wbhart]

On Fri, 14 Sep 2018 at 14:21, Claus Fieker ***@***.***> wrote: What abut having q, r = quotrem(a,b) s.th. a = qb+r and r = rem(a, b) q, r = divmod(a,b) s.th. q = qb+r and r = mod(a, b)?

Julia's mod and rem return the same thing. So I don't think this really solves anything. Mathematically, neither of them is useful, except in the case where the modulus is positive. And it's pretty standard that such a function should be called mod. I don't see the usefulness of quotrem at all.

[thofma]

No, it is not true that julias mod and rem are the same.

julia> rem(3, -2)
1

julia> mod(3, -2)
-1

Same for BigInt.

[wbhart]

The original ticket here is no longer valid. And we are basically doing this optimally, with our own internal hacked versions of div and divrem defined in terms of mod not rem. It's not possible to do better without breaking HNF and ResidueRing/Field.