How to find the remainder (modulo) of a division of very large numbers (million digits)

Posted: March 14, 2022

A few years back, my team and I were contenders in the ACM-TCPC, I think it was the 2014 version of the competition.

One of the problems (out of ten), the black problem, had a very concise description it went something like the following: Given two large numbers $N$ and $M$, we have to return $N$%$M$, pretty straightforward, isn't it? Well, there is a catch: $N$ can go up to 1 million digits. To give you an idea, here is a file containing 1 million digits of $\pi$: 1-Million-Digits-of-Pi-$\pi$.txt

My team and I didn't solve that problem at the time, no team did. But I remember trying Java's BigInteger class, which didn't work because it exceeded the allowed runtime for the test use cases.

I looked it up afterward, and the solution was purely arithmetic, a piece of information that you either knew or didn't.

Here is a Python implementation :

#Lazy file reading: https://stackoverflow.com/questions/519633/lazy-method-for-reading-big-file-in-python
def read_in_chunks(f, chunk_size=8):
    while True:
        chunk = f.read(chunk_size)
        if not chunk:
            break
        yield chunk

#https://www.damienelliott.com/wp-content/uploads/2020/07/1-Million-Digits-of-Pi-%CF%80.txt
file_name = '1_million_digits_of_pi.txt'
#A random number for the denominator
denominator = '4626'
numerator = ''
with open(file_name) as f:
    #Extract chunks of size 8 one at it a time
    for chunk in read_in_chunks(f, len(denominator)*2):
        #Replace the extracted chunk by the partial remainder 
        numerator = str(int(numerator+chunk)%int(denominator))
    print(numerator)

The solution looks simple and it still amazes me, you think after solving hundreds of problems I got used to it, but am a sucker for easy to implement hard to think-of solutions like this one.