What is faster? Modular Arithmetic functions and operations

General Usage Performance
1

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!

2

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
3

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?

4

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
5

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

2 Likes
6 
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
7

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.

8

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
9

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

1 Like
10

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

11

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

12

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

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

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
15

This implementation halved the allocations. Thanks a lot!

16

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
17

Write digits = big(50000) instead.

3 Likes
18

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

1 Like
19

Already changed that

20

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

1 Like