How to calculate with a number this big?

Question

I am learning Pascal on my own for a month now and I came up to one problem I can't seem to solve. Basically I have 2 numbers, N and M, where N is less than 10^{100 000} and M is less than 10⁸ and both are greater than 0. I need to calculate N mod M.

I can't figure out how to do it, not even with QWord. I tried it with string but I don't know a good way. It always ends up too complex for me because I use a for function where I get the last number from the string N and string M then I subtract them with two if functions (where last digit of N is higher or the same as last digit of M, and if it's lower). Basically it gets too complex for this easy problem I think.

Answer 1

There are some bignum packages floating around, e.g. the the open source MPArith package from http://www.wolfgang-ehrhardt.de/mp_intro.html. With the included demo calculator you can easily beat your time limit:

D:\Xtools\MPArith>t_calc.exe
T_CALC using MPArith V1.26.05 (31/32 bit) [mp_calc]  (c) W.Ehrhardt 2006-2013
Karatsuba cutoffs:  mul/sqr = 16/32,   Toom-3 cutoffs: mul/sqr = 32/64
Burnikel/Ziegler div cutoff = 32,   MaxBit = 520093696,   MaxFact = 22623931
Type "?<enter>" to get some info about commands, "\q" or "quit" to end.

[D]:=> 10^100000 mod (10^8-1)
Result = 1
[D]:=> .
Time = 20.128 ms
[D]:=> 10^100000;
Result =  [>0, 332193 bits,  chksum=$CE01C341,  time=46.994 ms]

But depending on your requirements and examples you may even get your results without bignum packages. If you want to compute a ^ b mod n you do not compute a ^ b and then reduce mod n in a second step, but you reduce every product in a loop. And you should use fast binary exponentiation, see e.g. the description and pseudo code at http://en.wikipedia.org/wiki/Modular_exponentiation. For modules n of order 10^8 you need to reduce a product of two 31/32 bit integers and therefore you need int64 or so to accumulate the products (which should not be a problem for you Pascal version which has QWord). I guess such a program would be much faster than the MPArith bignum code with it's 20 milliseconds.