You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by "Daniel Fridlender (JIRA)" <ji...@apache.org> on 2006/11/08 01:38:51 UTC
[jira] Created: (HARMONY-2091) [classlib][java.math] optimization
of BigInteger.modInverse
[classlib][java.math] optimization of BigInteger.modInverse
------------------------------------------------------------
Key: HARMONY-2091
URL: http://issues.apache.org/jira/browse/HARMONY-2091
Project: Harmony
Issue Type: Improvement
Reporter: Daniel Fridlender
Priority: Minor
This is an optimization of modInverse consisting of implementing algorithms from the papers "The Montgomery Modular Inverse - Revisited" (by Savas, E; Koc, C) and "New Algorithm for Classical Modular Inverse" (by Lórencz, R) and also making some low-level optimizations like avoiding intermediate data construction by implementing specific ad-hoc combination of arithmetic operations.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Assigned: (HARMONY-2091) [classlib][java.math] optimization
of BigInteger.modInverse
Posted by "Mikhail Loenko (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-2091?page=all ]
Mikhail Loenko reassigned HARMONY-2091:
---------------------------------------
Assignee: Mikhail Loenko
> [classlib][java.math] optimization of BigInteger.modInverse
> ------------------------------------------------------------
>
> Key: HARMONY-2091
> URL: http://issues.apache.org/jira/browse/HARMONY-2091
> Project: Harmony
> Issue Type: Improvement
> Reporter: Daniel Fridlender
> Assigned To: Mikhail Loenko
> Priority: Minor
> Attachments: after.html, before.html, modInverse_gcd.diff
>
>
> This is an optimization of modInverse consisting of implementing algorithms from the papers "The Montgomery Modular Inverse - Revisited" (by Savas, E; Koc, C) and "New Algorithm for Classical Modular Inverse" (by Lórencz, R) and also making some low-level optimizations like avoiding intermediate data construction by implementing specific ad-hoc combination of arithmetic operations.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Commented: (HARMONY-2091) [classlib][java.math]
optimization of BigInteger.modInverse
Posted by "Mikhail Loenko (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-2091?page=comments#action_12448091 ]
Mikhail Loenko commented on HARMONY-2091:
-----------------------------------------
the patch causes failures in org.apache.harmony.tests.java.math.BigDecimalArithmeticTest
> [classlib][java.math] optimization of BigInteger.modInverse
> ------------------------------------------------------------
>
> Key: HARMONY-2091
> URL: http://issues.apache.org/jira/browse/HARMONY-2091
> Project: Harmony
> Issue Type: Improvement
> Reporter: Daniel Fridlender
> Assigned To: Mikhail Loenko
> Priority: Minor
> Attachments: after.html, before.html, modInverse_gcd.diff
>
>
> This is an optimization of modInverse consisting of implementing algorithms from the papers "The Montgomery Modular Inverse - Revisited" (by Savas, E; Koc, C) and "New Algorithm for Classical Modular Inverse" (by Lórencz, R) and also making some low-level optimizations like avoiding intermediate data construction by implementing specific ad-hoc combination of arithmetic operations.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Updated: (HARMONY-2091) [classlib][java.math] optimization
of BigInteger.modInverse
Posted by "Daniel Fridlender (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-2091?page=all ]
Daniel Fridlender updated HARMONY-2091:
---------------------------------------
Attachment: before.html
after.html
These html documents show the gain in performance obtained by applying the patch. The files show performance before and after the patch.
> [classlib][java.math] optimization of BigInteger.modInverse
> ------------------------------------------------------------
>
> Key: HARMONY-2091
> URL: http://issues.apache.org/jira/browse/HARMONY-2091
> Project: Harmony
> Issue Type: Improvement
> Reporter: Daniel Fridlender
> Priority: Minor
> Attachments: after.html, before.html, modInverse_gcd.diff
>
>
> This is an optimization of modInverse consisting of implementing algorithms from the papers "The Montgomery Modular Inverse - Revisited" (by Savas, E; Koc, C) and "New Algorithm for Classical Modular Inverse" (by Lórencz, R) and also making some low-level optimizations like avoiding intermediate data construction by implementing specific ad-hoc combination of arithmetic operations.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Commented: (HARMONY-2091) [classlib][java.math]
optimization of BigInteger.modInverse
Posted by "Daniel Fridlender (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-2091?page=comments#action_12449889 ]
Daniel Fridlender commented on HARMONY-2091:
--------------------------------------------
Yes, the patch was applied as expected, thanks.
> [classlib][java.math] optimization of BigInteger.modInverse
> ------------------------------------------------------------
>
> Key: HARMONY-2091
> URL: http://issues.apache.org/jira/browse/HARMONY-2091
> Project: Harmony
> Issue Type: Improvement
> Reporter: Daniel Fridlender
> Assigned To: Mikhail Loenko
> Priority: Minor
> Attachments: after.html, afterGcd.html, before.html, beforeGcd.html, modInverse_gcd.diff, modInverse_gcd.diff
>
>
> This is an optimization of modInverse consisting of implementing algorithms from the papers "The Montgomery Modular Inverse - Revisited" (by Savas, E; Koc, C) and "New Algorithm for Classical Modular Inverse" (by Lórencz, R) and also making some low-level optimizations like avoiding intermediate data construction by implementing specific ad-hoc combination of arithmetic operations.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Updated: (HARMONY-2091) [classlib][java.math] optimization
of BigInteger.modInverse
Posted by "Daniel Fridlender (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-2091?page=all ]
Daniel Fridlender updated HARMONY-2091:
---------------------------------------
Attachment: modInverse_gcd.diff
beforeGcd.html
afterGcd.html
The new patch should fix the problem.
I attach also performance comparison before and after the patch for the gcd method.
Thanks!
> [classlib][java.math] optimization of BigInteger.modInverse
> ------------------------------------------------------------
>
> Key: HARMONY-2091
> URL: http://issues.apache.org/jira/browse/HARMONY-2091
> Project: Harmony
> Issue Type: Improvement
> Reporter: Daniel Fridlender
> Assigned To: Mikhail Loenko
> Priority: Minor
> Attachments: after.html, afterGcd.html, before.html, beforeGcd.html, modInverse_gcd.diff, modInverse_gcd.diff
>
>
> This is an optimization of modInverse consisting of implementing algorithms from the papers "The Montgomery Modular Inverse - Revisited" (by Savas, E; Koc, C) and "New Algorithm for Classical Modular Inverse" (by Lórencz, R) and also making some low-level optimizations like avoiding intermediate data construction by implementing specific ad-hoc combination of arithmetic operations.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Resolved: (HARMONY-2091) [classlib][java.math] optimization
of BigInteger.modInverse
Posted by "Mikhail Loenko (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-2091?page=all ]
Mikhail Loenko resolved HARMONY-2091.
-------------------------------------
Resolution: Fixed
applied in revision 474164
Daniel, please confirm that it was applied as expected
> [classlib][java.math] optimization of BigInteger.modInverse
> ------------------------------------------------------------
>
> Key: HARMONY-2091
> URL: http://issues.apache.org/jira/browse/HARMONY-2091
> Project: Harmony
> Issue Type: Improvement
> Reporter: Daniel Fridlender
> Assigned To: Mikhail Loenko
> Priority: Minor
> Attachments: after.html, afterGcd.html, before.html, beforeGcd.html, modInverse_gcd.diff, modInverse_gcd.diff
>
>
> This is an optimization of modInverse consisting of implementing algorithms from the papers "The Montgomery Modular Inverse - Revisited" (by Savas, E; Koc, C) and "New Algorithm for Classical Modular Inverse" (by Lórencz, R) and also making some low-level optimizations like avoiding intermediate data construction by implementing specific ad-hoc combination of arithmetic operations.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Updated: (HARMONY-2091) [classlib][java.math] optimization
of BigInteger.modInverse
Posted by "Daniel Fridlender (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/HARMONY-2091?page=all ]
Daniel Fridlender updated HARMONY-2091:
---------------------------------------
Attachment: modInverse_gcd.diff
This patch contains the aforementioned optimization.
> [classlib][java.math] optimization of BigInteger.modInverse
> ------------------------------------------------------------
>
> Key: HARMONY-2091
> URL: http://issues.apache.org/jira/browse/HARMONY-2091
> Project: Harmony
> Issue Type: Improvement
> Reporter: Daniel Fridlender
> Priority: Minor
> Attachments: modInverse_gcd.diff
>
>
> This is an optimization of modInverse consisting of implementing algorithms from the papers "The Montgomery Modular Inverse - Revisited" (by Savas, E; Koc, C) and "New Algorithm for Classical Modular Inverse" (by Lórencz, R) and also making some low-level optimizations like avoiding intermediate data construction by implementing specific ad-hoc combination of arithmetic operations.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira