CODEWITHSUNDEEP
pascalmodulusbignum
Luka
Luka

Reputation: 207

How to calculate with a number this big?

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 10100 000 and M is less than 108 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.

Upvotes: 5

Views: 897

Answers (1)

gammatester
gammatester

Reputation: 1141

There are some big number packages floating around, e. g. the the open source package MPArith by Wolfgang Erhardt. 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 big number packages. If you want to compute ab mod n you do not compute ab and then reduce it modulo 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 in the Wikipedia article on Modular exponentiation.

For modules n of order 108 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 big number code with its 20 milliseconds.

Upvotes: 3

Related Questions