# What is faster? Modular Arithmetic functions and operations

**URL:** <https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211>\
**Category:** Performance\
**Tags:** question\
**Created:** [December 3, 2020, 5:03pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211 "2020-12-03T17:03:45Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Renan\_Rabelo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/renan_rabelo/32/8048_2.png) [@Renan\_Rabelo](https://discourse.julialang.org/u/Renan_Rabelo)\
**Post date:** [December 3, 2020, 5:03pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/1 "2020-12-03T17:03:45Z")

</div>

I need to calculate the remainder of a 50000 digits BigInt divided by a 49999 digits BigInt

What’s the fastest way to do it?

mod()? mod1()? x%y? rem()?

Is there any package to do it?

Thanks!

---

<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:** [December 3, 2020, 5:08pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/2 "2020-12-03T17:08:31Z")

</div>

`mod` and `%` are exactly the same thing. All four of these answers will be almost exactly the same speed. `mod1` will give an answer off by 1, and if both numbers are positive, `mod` and `rem` will be exactly the same.

---

<div class="post-metadata">

**Author:** ![Renan\_Rabelo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/renan_rabelo/32/8048_2.png) [@Renan\_Rabelo](https://discourse.julialang.org/u/Renan_Rabelo)\
**Post date:** [December 3, 2020, 5:13pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/3 "2020-12-03T17:13:19Z")

</div>

In modular arithmetic “x = y (mod n)” is equivalent to "n divides x - y’.  
Is possible to divide two HUGE BigInt and verify if is an Integer?  
Or BigInt can’t be divided?

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [December 3, 2020, 5:19pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/4 "2020-12-03T17:19:40Z")

</div>

I don’t think 50,000 digits is that big these days? Did you actually try it? I’m guessing it will be quite fast.

---

<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:** [December 3, 2020, 5:21pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/5 "2020-12-03T17:21:33Z")

</div>

Dividing and checking the remainder is not going to be nearly as fast as computing `mod` directly.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [December 3, 2020, 5:21pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/6 "2020-12-03T17:21:41Z")

</div>

```julia
julia> x = big(10)^50000;

julia> y = big(10)^49999 - 1;

julia> @time x % y
 0.000023 seconds (3 allocations: 20.312 KiB)
10

```

These all run instantaneously in the REPL.

---

<div class="post-metadata">

**Author:** ![Renan\_Rabelo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/renan_rabelo/32/8048_2.png) [@Renan\_Rabelo](https://discourse.julialang.org/u/Renan_Rabelo)\
**Post date:** [December 3, 2020, 5:23pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/7 "2020-12-03T17:23:54Z")

</div>

I tried but when the number gets too big the division starts to fail.

My code is based on dividing 2 huge numbers and checking if the remainder is 0. If the remainder is 0 then the division results in an Integer.

But when I divide the “IsInteger()” checking don’t work properly.

---

<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:** [December 3, 2020, 5:27pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/8 "2020-12-03T17:27:43Z")

</div>

This is because if you are dividing 2 huge numbers, the difference between the result and the nearest integer can get very small. This is one of the reasons why just using `mod` is a better idea.

---

<div class="post-metadata">

**Author:** ![yha](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yha/32/3502_2.png) [@yha](https://discourse.julialang.org/u/yha)\
**Post date:** [December 3, 2020, 5:37pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/9 "2020-12-03T17:37:56Z")

</div>

> [@Oscar\_Smith](#):
>
> `mod` and `%` are exactly the same thing.

Actually, `%` is `rem`, not `mod` (a bit unfortunate, I think, since `mod` is so much more useful than `rem`).

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [December 3, 2020, 5:38pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/10 "2020-12-03T17:38:04Z")

</div>

Please paste a minimal example of what you are trying to do.

---

<div class="post-metadata">

**Author:** ![Renan\_Rabelo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/renan_rabelo/32/8048_2.png) [@Renan\_Rabelo](https://discourse.julialang.org/u/Renan_Rabelo)\
**Post date:** [December 3, 2020, 5:38pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/11 "2020-12-03T17:38:23Z")

</div>

Using x = big(10) is better than x::BigInt = 10?

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [December 3, 2020, 5:39pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/12 "2020-12-03T17:39:40Z")

</div>

I would write that as x = BigInt(10).  
big(10) is a nice shorthand that also works for floats.

---

<div class="post-metadata">

**Author:** ![Renan\_Rabelo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/renan_rabelo/32/8048_2.png) [@Renan\_Rabelo](https://discourse.julialang.org/u/Renan_Rabelo)\
**Post date:** [December 3, 2020, 5:43pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/13 "2020-12-03T17:43:13Z")

</div>

```julia
function findNumber()
    digits::BigInt = 50000
    current::BigInt = 6
    next::BigInt = current
    for c in 1:digits-1
        for k in 0:9
            next = current + k*(10^c)
            if ((next^2) - next)%(10^(c+1)) == 0
                current = next
                continue
            end
        end
    end
    text = open("NUMBER.txt","w")
    write(text, string(current))
    close(text)
end
@time findNumber()

```

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [December 3, 2020, 6:01pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/14 "2020-12-03T18:01:46Z")

</div>

I don’t understand what the code is supposed to do but you are repeatedly recalculating `10^c`. You can store that in a variable.

---

<div class="post-metadata">

**Author:** ![Renan\_Rabelo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/renan_rabelo/32/8048_2.png) [@Renan\_Rabelo](https://discourse.julialang.org/u/Renan_Rabelo)\
**Post date:** [December 3, 2020, 6:12pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/15 "2020-12-03T18:12:25Z")

</div>

This implementation halved the allocations. Thanks a lot!

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [December 3, 2020, 6:37pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/16 "2020-12-03T18:37:36Z")

</div>

And you moved it out of the loop over `k`?  
And update it by multipliying it by 10 each time.

Also, `k * 10^c` you can replace with an addition from the previous time.

---

<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:** [December 3, 2020, 8:01pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/17 "2020-12-03T20:01:05Z")

</div>

> [@Renan\_Rabelo](#):
>
> `digits::BigInt = 50000`

Write `digits = big(50000)` instead.

---

<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:** [December 3, 2020, 10:34pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/18 "2020-12-03T22:34:18Z")

</div>

> [@Renan\_Rabelo](#):
>
> ```julia
> for k in 0:9
> next = current + k*(10^c)
> if ((next^2) - next)%(10^(c+1)) == 0
> current = next
> continue
> end
> end
> 
> ```

Are you sure about this code? Here, `continue` does nothing, perhaps you meant `break`?

---

<div class="post-metadata">

**Author:** ![Renan\_Rabelo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/renan_rabelo/32/8048_2.png) [@Renan\_Rabelo](https://discourse.julialang.org/u/Renan_Rabelo)\
**Post date:** [December 3, 2020, 11:00pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/19 "2020-12-03T23:00:26Z")

</div>

Already changed that

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [December 3, 2020, 11:03pm UTC](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211/20 "2020-12-03T23:03:59Z")

</div>

You can get a big speed up if you use [https://github.com/jump-dev/MutableArithmetics.jl](https://github.com/jump-dev/MutableArithmetics.jl) to do the math pre-allocated and in place.

[Next page](https://discourse.julialang.org/t/what-is-faster-modular-arithmetic-functions-and-operations/51211.md?page=2)