Base: new function `isdivisible`

[barucden]

Base does not provide a function for checking divisibility:

"""
    isdivisible(m, n)

Return true if `m` is divisible by `n`.
"""
isdivisible(m::Integer, n::Integer)

It can be implemented as iszero(rem(m, n)) but that's not the optimal implementation for all types from Base (it allocates for a BigInt).

AbstractAlgebra.jl from Nemo implements this exact function: https://github.com/Nemocas/AbstractAlgebra.jl/blob/396fdddbc1d1620a7b2866e7340e39b14228176e/src/julia/Integer.jl#L121-L151
I would like to have it in Base.

(Discussed on Discourse: https://discourse.julialang.org/t/checking-divisibility-efficiently/121418)

[ararslan]

FWIW I agree with @oscardssmith's comment on Discourse that IntegerMathUtils seems like a good home for that function. I would be interested to know whether any code in Base or the stdlibs could be meaningfully simplified by having this function available. If so, I'd consider that a positive signal for inclusion in Base. However, I suspect the answer is no (though I could well be wrong).

[barucden]

Understood. There are some divisibility checks in Base.

julia/base/array.jl

Line 2455 in d36417b

iszero(d % step(r)) || return nothing

julia/base/arrayshow.jl

Line 225 in d36417b

print(io, (i - first(rowsA)) % hmod == 0 ? hdots : repeat(" ", length(hdots)::Int))

julia/base/int.jl

Line 117 in d36417b

isodd(n::Real) = isinteger(n) && !iszero(rem(Integer(n), 2))

julia/base/int.jl

Line 137 in d36417b

iseven(n::Real) = isinteger(n) && iszero(rem(Integer(n), 2))

julia/base/range.jl

Line 1209 in d36417b

if !iszero(rem(start1 - start2, g))

julia/base/reinterpretarray.jl

Line 444 in d36417b

if sizeof(T) % sizeof(S) == 0

Some are in stdlibs (e.g., checking leap year in Dates).

I wouldn't say this is exactly "meaningfully simplified" (after all, how much can you simplify a divisibility check?):

- if sizeof(T) % sizeof(S) == 0
+ if isdivisible(sizeof(T), sizeof(S))

It is more explicit, maybe. I would say it is similar to replacing x % 2 == 0 with iseven(x).

I am mostly interested in it for the BigInt type for which x % n allocates, and so x % n == 0 is not cheap, whereas it is cheap for Ints.

[adienes]

I am mostly interested in it for the BigInt type for which x % n allocates, and so x % n == 0 is not cheap, whereas it is cheap for Ints.

not to derail this issue, but this statement makes me wonder if, with a fast isdivisible function, shouldn't % in fact get a fast path isdivisible(x, n) && return 0 for BigInt ?

[barucden]

As I understand it, rem(x::BigInt, n) returns a BigInt, so you would have to return big(0) to keep the method type-stable, which would again allocate.

[adienes]

BigInt are officially immutable though (despite the fact that they are mutable in practice) so one could return big"0" or any other shared obj and allocate only exactly once per program execution

[oscardssmith]

I do think it would be worth considering whether % should take the type of the 2nd argument rather than the promotion type. GMP has optimized methods for BigInt%Int which would recover the performance for most cases.

[ararslan]

I do think it would be worth considering whether % should take the type of the 2nd argument rather than the promotion type.

In that case, divrem would potentially give you a heterogeneous tuple, which feels... weird. But that consideration is pretty orthogonal to the proposed feature here.

I wouldn't say this is exactly "meaningfully simplified" (after all, how much can you simplify a divisibility check?)

I actually find the examples and the iseven analogy fairly compelling. I'd be on board with adding it to Base, for whatever that's worth.

[barucden]

I understand that the general idea is to keep Base as small as possible, but this seems like a small addition (we need just a few methods IMHO) with clearly defined meaning, so it is unlikely to ever change, meaning the maintenance burden should be close to none.

Anyway, I guess we should wait for other people's opinion? So far I haven't convinced many 😆

[jmichel7]

A closely related function which should be considered at the same time is LinearAlgebra.exactdiv. This function is currently used in
det_bareiss, but is important more generally for writing some linear algebra over a ring. The general meaning is that
exactdiv(a,b) should return c when in the ring where they lie we have a=b*c (in a field it is the same as /). This makes det_bareiss work over the integers, but more generally, work for example in polynomial rings, as soon as exactdiv is defined. Actually, it would be very useful that exactdiv returns a failure when exact division does not occur, like returning nothing (maybe more useful than raising an error). Anyway I think exactdiv and isdivisible should be considered at the same time with the idea that they could be expanded to any ring.

[barucden]

Isn't that what ÷ / div is supposed to do? That is, for integers a, b, c, if isdivisible(a, b), then a ÷ b (or div(a, b)) returns c such that a = b * c. I see that exactdiv in LinearAlgebra is even defined using div:

julia/stdlib/LinearAlgebra/src/generic.jl

Line 1781 in f1990e2

exactdiv(a::Integer, b::Integer) = div(a, b)

---

By the way, in case this function actually finds its way into Base – what should be the result of isdivisible(0, 0)? True, because 0 = 0 * x for any x? False, because nothing can be divided by zero? An error, because that's what iszero(rem(0, 0)) would do?

[nsajko]

Isn't that what ÷ / div is supposed to do?

@barucden div(5.0, 2.0) == 2, but 5.0 / 2.0 == 2.5 != 2. So presumably this exactdiv would be useful for generic programming.

[sumiya11]

I sometimes also needed a % b == 0 for a big int a and a machine int b. I think adding __gmpz_divisible_ui_p from @barucden 's discourse post to base/gmp.jl can be a nice thing in itself.

[sumiya11]

Though, in my opinion, for readability a % b == 0 can be preferable to isdivisible(a, b). I somehow get the order of arguments to isdivisible(a, b) wrong in half of the cases in other languages.