JDK-5100935 : No way to access the 64-bit integer multiplication of 64-bit CPUs efficiently
  • Type: Enhancement
  • Status: Resolved
  • Resolution: Fixed
  • Component: core-libs
  • Sub-Component: java.lang
  • Priority: P3
  • Affected Version: 5.0
  • OS: windows_2000
  • CPU: x86
  • Submit Date: 2004-09-13
  • Updated Date: 2017-06-28
  • Resolved Date: 2016-05-20
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availabitlity Release.

To download the current JDK release, click here.
9 b120Resolved
Related Reports
Relates :  
Relates :  
Relates :  
Relates :  
Relates :  
Relates :  

Name: js151677			Date: 09/13/2004

64-bit CPUs like AMD Opteron can multiply two 64-bit integers and produce a 128-bit result. in Java there is currently no way to access this feature. VMs even have no way to offer this capability to an application, because there is no 128-bit type for returning the result.

in the security area, asymmetric cryptography plays an important role. algorithms like RSA use long integer arithmentic extensively. for instance, certain baisc long integer operations like multiplication have quadratic running time. in this case, using a 64-bit multiplication as a basis instead of a 32-bit muliplication can decrease the number of required steps to a fourth. thus, time consuming RSA operations could be much faster just by exploiting 64-bit muliplication.
this feature could speed up the java.math.BigInteger class significantly.

the most natural thing would be to introduce a 128-bit type; e.g. long128.

use 32-bit multiplication with 64-bit results. however, using this takes four times longer in an algorithm with quadratic running time.
(Incident Review ID: 310503) 

Review thread: http://mail.openjdk.java.net/pipermail/core-libs-dev/2015-September/035289.html Review reprise: http://mail.openjdk.java.net/pipermail/core-libs-dev/2016-May/041248.html

I don't see this particular RFE strongly tied to value type; I think it would be helpful to provide a static method with this functionality even if an "Integer128" type is added as part of JDK 9+.

Do we want to pursue these multiply{Full,High}() methods in Java 9, or would this topic be better served by waiting until support for value types is in place? Or the effort could be split across two different stages?

Until we have support for value types, I would suspect we wouldn't want to return a long[] since code that wants this functionality will likely be performance-sensitive. Name alternatives to consider: For the (int, int) -> long case, "multiplyFull". For the high bits of (long, long) -> long, "multiplyHigh"

Perhaps it would be logical to implement this capability by adding these methods to java.lang.Math: /** * Returns the product of the arguments allowing overflowed values within the range of {@code long}. */ public long multiplyExtended(int x, int y) {} /** * Returns the product of the arguments allowing overflowed values within double the range of {@code long}. * The returned value is of length two, with the more significant element being in the zeroth position. */ public long[] multiplyExtended(long x, long x) {}

EVALUATION If a algorithm with quadratic complexity is being used, speeding up the integer multiples by a constant factor will have bounded benefit. It may be reasonable to provide a long multiply(int, int) method to at least model that machine capability. However, introducing a new primitive type into the language would be extremely complicated. The vm implementation of a class like BigInteger may or may not closely resemble the source code of the method; i.e. the vm could potentially use 64 x 64 -> 128 bit multiples even if this can't be expressed in Java source. ###@###.### 2004-09-17