Filter
Top Products
62 General 64-Bit Optimizations Chapter 3
25112 Rev. 3.06 September 2005
Software Optimization Guide for AMD64 Processors
3.2 64-Bit Arithmetic and Large-Integer Multiplication
Optimization
Use 64-bit arithmetic for integer multiplication that produces 128-bit or larger products.
Background
Large-number multiplications (those involving 128-bit or larger products) are utilized in
cryptography algorithms, which figure importantly in e-commerce applications and secure
transactions on the Internet. Processors cannot perform large-number multiplication natively; they
must break the operation into chunks that are permitted by their architecture (32-bit or 64-bit
additions and multiplications).
Rationale
Using 64-bit rather than 32-bit integer operations dramatically reduces the number of additions and
multiplications required to compute large products. For example, computing a 1024-bit product using
64-bit arithmetic requires fewer than one quarter the number of instructions required when using
32-bit operations:
In addition, the processor performs 64-bit additions just as fast as it performs 32-bit additions, and the
latency of 64-bit multiplications is only slightly higher than for 32-bit multiplications. (The processor
is capable of performing a 64-bit addition each clock cycle and a 64-bit multiplication every other
clock cycle.)
Example
Consider the multiplication of two unsigned 64-bit numbers a and b, represented in terms of 32-bit
numbers a1:a0 and b1:b0.
a = a1 * 2
32
+ a0
b = b1 * 2
32
+ b0
The product of a and b, c, can be expressed in terms of products of the 32-bit components, as follows:
c = (a1 * b1) * 2
64
+ (a1 * b0 + a0 * b1) * 2
32
+ (a0 * b0)
Comparing... 32-bit arithmetic 64-bit arithmetic
Number of multiplications 256 64
Number of additions with carry 509 125
Number of additions 255 63