# What is faster? Modular Arithmetic functions and operations

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!

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

3 Likes

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?

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.

4 Likes

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

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

3 Likes

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.

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.

4 Likes

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

1 Like

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

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

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

1 Like
``````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()
``````

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.

3 Likes

This implementation halved the allocations. Thanks a lot!

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.

2 Likes

Write `digits = big(50000)` instead.

3 Likes

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

1 Like