Comments (20)
thofma
commented on June 3, 2024
What to do you mean by "now"? I did not observe a change to divrem in julia.
from abstractalgebra.jl.
wbhart
commented on June 3, 2024
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.
from abstractalgebra.jl.
thofma
commented on June 3, 2024
I cannot follow. They give the same answer. Do you have an example?
from abstractalgebra.jl.
wbhart
commented on June 3, 2024
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.
from abstractalgebra.jl.
wbhart
commented on June 3, 2024
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.
from abstractalgebra.jl.
thofma
commented on June 3, 2024
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.
from abstractalgebra.jl.
wbhart
commented on June 3, 2024
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.
from abstractalgebra.jl.
thofma
commented on June 3, 2024
Sorry, yes there would be not change to rem.
Currently mod(2, 5) and mod(-3, 5) return the same result.
from abstractalgebra.jl.
wbhart
commented on June 3, 2024
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?
from abstractalgebra.jl.
thofma
commented on June 3, 2024
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>
.
from abstractalgebra.jl.
wbhart
commented on June 3, 2024
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
from abstractalgebra.jl.
thofma
commented on June 3, 2024
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.
from abstractalgebra.jl.
fieker
commented on June 3, 2024
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)
from abstractalgebra.jl.
thofma
commented on June 3, 2024
I just did some more testing and searching and here is what I found out.
- Let's first look at
%,modandrem. 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.
- 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.
from abstractalgebra.jl.
wbhart
commented on June 3, 2024
We could get around 2 by demanding that mod take a positive modulus. We
would simply not define our mod for negative modulus.
from abstractalgebra.jl.
wbhart
commented on June 3, 2024
Sorry, I mean the second part of one, not 2.
from abstractalgebra.jl.
fieker
commented on June 3, 2024
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)
from abstractalgebra.jl.
wbhart
commented on June 3, 2024
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.
from abstractalgebra.jl.
thofma
commented on June 3, 2024
No, it is not true that julias mod and rem are the same.
julia> rem(3, -2)
1
julia> mod(3, -2)
-1Same for BigInt.
from abstractalgebra.jl.
wbhart
commented on June 3, 2024
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.
from abstractalgebra.jl.
Related Issues (20)
- How to convert an univariate polynomial to a multivariate polynomial? HOT 2
- `minpoly` `MethodError` HOT 2
- docs: duplicate entry for `evaluate`
- Missing or incomplete docstrings for various ring constructors
- `vars` for fractions of multivariate polynomials HOT 1
- New polynomial ring constructor implementation is type unstable
- [Bug] `view` only likes `UnitRange` even though it accepts other arguments HOT 6
- Loading this package breacks `show(Union{}[])` HOT 4
- `is_[lower/upper]_triangular` not useful for non-square matrices HOT 5
- The use of polynomial rings in multi-threaded programs HOT 3
- Rename `intersection` methods to `intersect`
- Try to export `Generic` HOT 1
- Pretty printing code (esp. indent) has issues with non-ASCII unicode strings HOT 6
- Should `macro show_name` / `@show_name` check for `:supercompact` in addition to `:compact` ? HOT 2
- Missing `Lowercase` in some printing functions HOT 2
- Implement `algebraic_closure(QQ)`
- Add a variant of `allow_unicode` which does not modify `LocalPreferences.toml` and only enables/disables unicode for the current session
- Invalidations caused by `lock(io::IOCustom)` HOT 2
- Documentation of aliases seems to fail on nightly? HOT 3
- Typo in incompatible rational function field error message
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from abstractalgebra.jl.