United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
JDK-5100935 : No way to access the 64-bit integer multiplication of 64-bit CPUs efficiently

Details
Type:
Enhancement
Submit Date:
2004-09-13
Status:
Open
Updated Date:
2014-03-23
Project Name:
JDK
Resolved Date:
Component:
core-libs
OS:
windows_2000
Sub-Component:
java.lang
CPU:
x86
Priority:
P3
Resolution:
Unresolved
Affected Versions:
5.0
Targeted Versions:
tbd_major

Related Reports
Relates:
Relates:

Sub Tasks

Description

Name: js151677			Date: 09/13/2004


A DESCRIPTION OF THE REQUEST :
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.

JUSTIFICATION :
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.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
the most natural thing would be to introduce a 128-bit type; e.g. long128.

CUSTOMER SUBMITTED WORKAROUND :
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) 
======================================================================

                                    

Comments
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
                                     
2004-09-17
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) {}

                                     
2013-11-04
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"
                                     
2013-11-15



Hardware and Software, Engineered to Work Together