Thread overview  


October 02, 2017 [phobos] Issue6244, implementing 'powmod'  

 
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#Righttoleft_binary_method _______________________________________________ phobos mailing list phobos@puremagic.com http://lists.puremagic.com/mailman/listinfo/phobos 
October 02, 2017 Re: [phobos] Issue6244, implementing 'powmod'  

 
Posted in reply to Alex Jercaianu  A possible solution is to implement mul128 using primitives for 32 and 64bit 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 4digit number. Consider the twodigit 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 1digit multiplication and addition with carry. Now of course our base is not 10 but 2^^32, so we multiply two numbers, each having two 32bit "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#Righttoleft_binary_method > > _______________________________________________ > phobos mailing list > phobos@puremagic.com > http://lists.puremagic.com/mailman/listinfo/phobos _______________________________________________ phobos mailing list phobos@puremagic.com http://lists.puremagic.com/mailman/listinfo/phobos 
October 03, 2017 Re: [phobos] Issue6244, implementing 'powmod'  

 
Posted in reply to Andrei Alexandrescu  On Tuesday, 3 October 2017 at 01:42:44 UTC, Andrei Alexandrescu wrote: > A possible solution is to implement mul128 using primitives for 32 and 64bit 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 4digit number. > > Consider the twodigit 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 1digit multiplication and addition with carry. Now of course our base is not 10 but 2^^32, so we multiply two numbers, each having two 32bit "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 Thanks for the suggestion! I think I have also found a way to implement 'mulmod' without' mul128'. Is overflow well defined for unsigned types in D? For example, (MAX_UINT + 1) equals 0 for unsigned types? I will also come back with a 'mul128' implementation, since there is none available for the moment in the standard library. Thanks, Alex _______________________________________________ phobos mailing list phobos@puremagic.com http://lists.puremagic.com/mailman/listinfo/phobos 
Copyright © 19992021 by the D Language Foundation