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!

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

Already changed that

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