Utente:AlbertoZanna/Sandbox

Long integer cubes

In 2010 Alberto Zanoni proposed a new method to compute the cube of a long integer, faster with respect to the "natural cube algorithm" (NCA) suggested by the definition n³ = n² × n. The idea is based on a divide and conquer approach (splitting in two) and the use of a modified unbalanced Toom-Cook multiplication method.

Consider a long integer n and split it into its high and low part. General formulas together with an example follow.

n(x)	= ax+b	123456 = 123 × 103 + 456 (with x = 103)
n(x)3	= (ax+b)3	1234563 =
	= (a3x3 + 3a2bx2 + 3ab2x + b3) $\qquad \qquad \qquad$ $\qquad$ $\qquad$ $\qquad$	= 1860867 × 109 + 6898824 × 106 + 25576128 × 103 + 94818816 = 1881640295202816

NCA in the above setting implies first computing the square:

n(x)2	= (ax+b)2	123 4562
	= a2x2 + 2abx + b2 $\qquad$ $\qquad$ $\qquad$ $\qquad$ $\qquad$	15 129 × 106 + 112 176 × 103 + 207 936 = 15 241 383 936

The polynomial n(x)² can be represented as follows (in the example: a₃ = 15; a₂ = 241; a₁ = 383; a₀ = 936)

n(x)² = a₃x³ + a₂x² + a₁x + a₀

so that the final product becomes

n(x)³ = (a₃x³ + a₂x² + a₁x + a₀)(ax + b) = n₄x⁴ + n₃x³ + n₂x² + n₁x + n₀

If n² is computed by using Karatsuba method (3 squares) and the product by using unbalanced Toom-3 method (5 products), 8 quadratic operations are needed in total. Zanoni's algorithm reduces them to 7 (one square less), by considering slightly different formulas.

From the polynomial point of view, consider the following product:

G'(x) = G₁(x)G₂(x) = (a²x² + 3b²)(ax + 3b) = a³x³ + 3a²bx² + 3ab²x + 9b³

differing by n(x)³ only in the constant term. The (extra) division by 9 (a fixed, "short" integer) needed to recover n(x)³ is a linear operation, which substitutes the 2ab product computation. Unfortunately, this cannot be directly applied to long integer cubing, as the final "recomposition" (in the example, setting x=10³ and perform the final sums) is incompatible with G'(x) management. Indicating the first factor of G(x) as

G₁(x) = g₃x³ + g₂x² + g₁x + g₀

the correct multiplication to be done is

G(x) = (g₃x³ + g₂x² + 3g₁x + 27g₀)(ax + 3b) = n₄x⁴ + n₃x³ + n₂x² + 9n₁x + 81n₀

It is then sufficient to divide the last two coefficients by 9 and 81, respectively, to obtain n(x)³ and perform the "recomposition". Actually, with a small modification of the unbalanced Toom-3 method inversion phase, it is possible to transform the division by 9 into a faster multiply-by-9-and-subtract operation.

Zanoni's method is effective only when the number of digits of n lies inside a range (depending on software and hardware environments), as using faster methods (higher Toom-Cook or Schönhage–Strassen algorithm) in other ranges revealed experimentally to be more effective.