Division (modulus) of large integers (max 200 digits)

2
votes

I am programming prime number generator (max 200 digits) in Pascal using the Miller–Rabin primality test.

I have already implemented multiple steps but I got stuck at the modular exponentiation part. I chose the Right-to-left binary method where (I assume) I have to implemenent A mod B where A and B are both (in worst case 200 digits). And to calculate the modulus I have to implement division of 2 numbers with max 200 digits. I respresent my long integers in an array where every element is a digit (0-9).

I have googled and I have not found any suitable algorithm for me (that would not take a lot of time to implement). So I am asking here if anyone has any experience with this. I doesnt have to be the fastest algorithm but it should not be "dumb" as euclidian divison that would take years and should be kind of easy to implement. I dont want do use any library (pure pascal)

2
algorithmmathintegerpascaldivision
Why are you storing them in base 10? - cdo256
no particular reason except its base 10 where I can think easily and I dont have to implement base 10 to binary and back. Everything I implemented until this worked easily with base 10. I guess it wouldnt be a problem to convert it into binary if there is a relatively simple algorithm that works in binary - honzaik
If you don't care about efficiency and don't want to directly implement full division -- implement multiplication if you haven't already done so, implement division by 2 (a special case which is easy to work out), and then use binary search to find the integer quotient. - John Coleman
Related: stackoverflow.com/q/5386377/4996248 - John Coleman
@harold: Even in base 10, if numbers reach 200 digits (or even just 30 digits), repeated extraction can become very slow. I already linked to my BigInteger code, which uses base 2^32, but the same principles apply. A basecase division (as described by Knuth, IIRC that is algorithm D in volume 2, but I could be wrong about that) is not terribly complicated, especially not in base 10. - Rudy Velthuis

2 Answers

1
votes

Read this answer for fast multiplication and this page for slower but easier to understand multiplication. Read this page for fast division using that multiplication algorithm. The time complexity will be proportional to the time complexity of the multiplication.

0
votes

thank you all for your responses. i have decided to use divison using binary search as suggested here Division (modulus) of large integers (max 200 digits) i realized its not probably what i want because overall my modular exponentiation is slow for larger numbers (60+digits) but the algorithm is pretty simple