Checking divisibility efficiently

General Usage
,
1

Is there a function in Base like isdivisible(m::Integer, n::Integer) that returns true if m is divisible by n? A straightforward implementation would be

isdivisible(m, n) = iszero(m % n)

Modulo works just fine for Ints, but it allocates for BigInts:

julia> @btime isdivisible($(big(12)), 2);
  102.695 ns (4 allocations: 80 bytes)

There is a function for that in GMP, which I am using (see below), but I am wondering if I am missing an implementation from Base.

function mpz_isdivisible(x::BigInt, y::Int)
    r = ccall((:__gmpz_divisible_ui_p, Base.GMP.libgmp), Cint,
              (Base.GMP.MPZ.mpz_t, Culong), x, y)
    return r != 0
end

julia> @btime mpz_isdivisible($(big(12)), 2);
  7.717 ns (0 allocations: 0 bytes)
2

As a side note, Nemo.jl has is_divisible_by():

using Nemo
@btime is_divisible_by($(big(12)), 2)    # 7 ns (0 allocs: 0 bytes)
1 Like
3

Thank you. That probably answers my question. The exact function is there with many methods: AbstractAlgebra.jl/src/julia/Integer.jl at 396fdddbc1d1620a7b2866e7340e39b14228176e · Nemocas/AbstractAlgebra.jl · GitHub

That’s a strong indicator that Base does not have it. I’ll create an issue to see if there’s any interest in putting it into Base.

4

I don’t see why this should be in Base (things are moving out of Base, not into it), especially since the implementation is trivial, as you show: iszero(a % b). The performance issue can be helped by improving the performance of % for BigInt.

2 Likes
5

This probably belongs in IntegerMathUtils.jl

1 Like
6

Checking divisibility seems common enough to me and it is not trivial to implement it for BigInt, which is a type from Base.

Isn’t % for BigInts always going to allocate the result?

7

I did not know about this package. It might be a good fit. I still think that this function is common enough to have it in Base though.

I created an issue: Base: new function `isdivisible` · Issue #56212 · JuliaLang/julia · GitHub