[phobos] Issue6244, implementing 'powmod'
Andrei Alexandrescu
andrei at erdani.com
Tue Oct 3 01:42:44 UTC 2017
A possible solution is to implement mul128 using primitives for 32- and
64-bit numbers. A possible signature would be:
void mul128(ulong a, ulong b, out ulong lo, out ulong hi);
The technique is to do the multiplication "by hand" as if you had two
numbers having two digits each. You obtain a 4-digit number.
Consider the two-digit decimal numbers ab and cd, for example 43 and 65.
Then the multiplication "by hand" is:
(10a + b) * (10c + d) = 100ac + 10(ad + bc) + bd
Since a, b, c, d are single digits it follows we only need 1-digit
multiplication and addition with carry. Now of course our base is not 10
but 2^^32, so we multiply two numbers, each having two 32-bit "digits"
and we get 128 bits worth of result.
mul128() would be a generally useful function to put in druntime. I
think someone on the general forum has implemented it already, you may
want to ask.
Andrei
On 10/2/17 12:48 PM, Alex Jercaianu via phobos wrote:
> Hello,
>
> I am trying to implement the 'powmod' functionality as described here [1].
>
> The issue that I am having is that the algorithm uses multiplications
> which can cause overflow.
> If the base is 32 bits, then I can use 64 bit variables to handle the
> result of multiplications, however the problem arises if the base is 64
> bit.
>
> The pseudocode would look the following:
>
> while (exponent > 0)
> {
> if (exponent & 1)
> {
> result = mulmod(result, base, modulus);
> }
>
> base = mulmod(base, base, modulus);
> exponent >>= 1;
> }
>
> return result;
>
> The problem that I am facing is with the 'mulmod' function which should
> do multiplication and modulo of the result without overflow problems.
>
> Do you think that it would be a good idea to limit the base to 32 bits?
> Or does D have any facility similar to 'mulmod'?
>
> Thanks,
> Alex
>
> [1] -
> https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method
>
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos
More information about the phobos
mailing list