# Checking divisibility efficiently

**URL:** <https://discourse.julialang.org/t/checking-divisibility-efficiently/121418>\
**Category:** General Usage\
**Tags:** numbers, math\
**Created:** [October 17, 2024, 11:31am UTC](https://discourse.julialang.org/t/checking-divisibility-efficiently/121418 "2024-10-17T11:31:41Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![barucden](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/barucden/32/26154_2.png) [@barucden](https://discourse.julialang.org/u/barucden)\
**Post date:** [October 17, 2024, 11:31am UTC](https://discourse.julialang.org/t/checking-divisibility-efficiently/121418/1 "2024-10-17T11:31:42Z")

</div>

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

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

```

Modulo works just fine for `Int`s, but it allocates for `BigInt`s:

```julia-repl
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.

* * *

```julia
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-repl
julia> @btime mpz_isdivisible($(big(12)), 2);
  7.717 ns (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [October 17, 2024, 12:03pm UTC](https://discourse.julialang.org/t/checking-divisibility-efficiently/121418/2 "2024-10-17T12:03:55Z")

</div>

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

```julia
using Nemo
@btime is_divisible_by($(big(12)), 2) # 7 ns (0 allocs: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![barucden](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/barucden/32/26154_2.png) [@barucden](https://discourse.julialang.org/u/barucden)\
**Post date:** [October 17, 2024, 12:10pm UTC](https://discourse.julialang.org/t/checking-divisibility-efficiently/121418/3 "2024-10-17T12:10:42Z")

</div>

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](https://github.com/Nemocas/AbstractAlgebra.jl/blob/396fdddbc1d1620a7b2866e7340e39b14228176e/src/julia/Integer.jl#L121-L151)

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.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [October 17, 2024, 12:32pm UTC](https://discourse.julialang.org/t/checking-divisibility-efficiently/121418/4 "2024-10-17T12:32:59Z")

</div>

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`.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [October 17, 2024, 12:36pm UTC](https://discourse.julialang.org/t/checking-divisibility-efficiently/121418/5 "2024-10-17T12:36:39Z")

</div>

This probably belongs in IntegerMathUtils.jl

---

<div class="post-metadata">

**Author:** ![barucden](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/barucden/32/26154_2.png) [@barucden](https://discourse.julialang.org/u/barucden)\
**Post date:** [October 17, 2024, 12:40pm UTC](https://discourse.julialang.org/t/checking-divisibility-efficiently/121418/6 "2024-10-17T12:40:12Z")

</div>

> [@DNF](#):
>
> 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)`.

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

> [@DNF](#):
>
> The performance issue can be helped by improving the performance of `%` for `BigInt`.

Isn’t `%` for `BigInt`s always going to allocate the result?

---

<div class="post-metadata">

**Author:** ![barucden](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/barucden/32/26154_2.png) [@barucden](https://discourse.julialang.org/u/barucden)\
**Post date:** [October 17, 2024, 12:47pm UTC](https://discourse.julialang.org/t/checking-divisibility-efficiently/121418/7 "2024-10-17T12:47:04Z")

</div>

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](https://github.com/JuliaLang/julia/issues/56212)