[phobos] Issue6244, implementing 'powmod'
Alex Jercaianu
alex.jercaianu at gmail.com
Tue Oct 3 12:47:07 UTC 2017
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 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
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
More information about the phobos
mailing list