harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Daniel Fridlender" <dfridlen...@gmail.com>
Subject Re: [classlib][java.math] optimization of BigInteger.modPow and BigInteger.pow
Date Tue, 07 Nov 2006 00:22:07 GMT
Hi Alexey,

yes we often tested the speed in our several attempts to improve
performance.  Comparing modPow before and after this new patch gave us
the following figures:

size         before              after
16         5.636e+05       6.351e+05
32         9.727e+04       1.293e+05
48         3.225e+04       4.623e+04
64         1.436e+04       2.148e+04
128               1941                3114
192                590                   970
256                252                   420
384                 75                    127
512                 32                     55

where the first column shows the size of the arguments in bytes and
the other two the number of modPow operations per 100 seconds before
and after the patch.

The method modPow is used in cryptography, we tested several
cryptographic algorithms obtaining in all cases figures in favor of
the optimized version (the one in the patch).
For instance, for RSA key generation we obtained:

size         before           after
512            3,00             2,06
1024        20,17            13,58
2048       280,38          149,48

where the first column shows the length of the key in bits and the
other two the time in seconds taken to perform 30 iterations of the
key generation algorithm before and after the patch.

Thanks,

Daniel

On 11/3/06, Alexey Petrenko <alexey.a.petrenko@gmail.com> wrote:
> Hi, Daniel.
>
> Great job!
>
> Have you made any performance testing to understand how much the patch
> increases the speed of the methods?
>
> SY, Alexey
>
> 2006/11/3, Daniel Fridlender <dfridlender@gmail.com>:
> > Hi,
> >
> > We have submitted in http://issues.apache.org/jira/browse/HARMONY-1981
> > an optimization of BigInteger methods modPow and pow.
> >
> > The optimization in modPow was achieved by introducing sliding windows
> > instead of the square-and-multiply method.  Some gain was obtained
> > also from an optimized Montgomery multiplication used for computing
> > squares.
> >
> > The method pow was optimized accordingly by improving the computation
> > of squares.
> >
> > Thanks
> >
> > Daniel
> >
>

Mime
View raw message