[This file contains notes to myself on multiplication. Mostly, it's the math behind Karatsuba and Toom-Cook.] Karatsuba: a AZ d b BY e c AY+BZ f - a - b d AZ e BY f (A+B)(Y+Z) = AY + AZ + BY + BZ O(3^(log2 n)) = O(n^(log2 3)) ~ O(n^1.58496) ================================================================ Toom-3: P1(x) = A x^2 + B x + C P2(x) = D x^2 + E x + F PP(x) = AD x^4 + (AE+BD) x^3 + (AF+BE+CD) x^2 + (BF+CE) x + CF = G x^4 + H x^3 + I x^2 + J x + K Use, eg, 0, 1, -1, 2, and infinity, to give 5 points to specify PP(): x = 0 1 -1 2 inf [ A B C ] [ 0 1 1 4 1 ] [ P1(0) P1(1) P1(-1) P1(2) P1(inf) ] [ ] [ 0 1 -1 2 0 ] = [ ] [ D E F ] [ 1 1 1 1 0 ] [ P2(0) P2(1) P2(-1) P2(2) P2(inf) ] recurse 5 times: PP(0) = P1(0) P2(0) = C F PP(1) = P1(1) P2(1) = (A + B + C) (D + E + F) PP(-1) = P1(-1) P2(-1) = (A - B + C) (D - E + F) PP(2) = P1(2) P2(2) = (4 A + 2 B + C) (4 D + 2 E + F) PP(inf) = P1(inf) P2(inf) = A D [ 0 1 1 16 1 ] [ 0 1 -1 8 0 ] [ G H I J K ] [ 0 1 1 4 0 ] = [ PP(0) PP(1) PP(-1) PP(2) PP(inf) ] [ 0 1 -1 2 0 ] [ 1 1 1 1 0 ] -1 [ 0 1 1 16 1 ] [ 0 1 -1 8 0 ] [ G H I J K ] = [ PP(0) PP(1) PP(-1) PP(2) PP(inf) ] [ 0 1 1 4 0 ] [ 0 1 -1 2 0 ] [ 1 1 1 1 0 ] or [ 0 1/2 -1 -1/2 1 ] [ 0 -1/2 1/2 1 0 ] [ G H I J K ] = [ PP(0) PP(1) PP(-1) PP(2) PP(inf) ] [ 0 -1/6 1/2 -1/3 0 ] [ 0 1/6 0 -1/6 0 ] [ 1 -2 -1 2 0 ] O(5^(log3 n)) = O(n^(log3 5)) ~ O(n^1.46497) Incidentally, this means that, for example, 3 C F - 3 (A + B + C) (D + E + F) - (A - B + C) (D - E + F) + (4 A + 2 B + C) (4 D + 2 E + F) - 12 A D must be a multiple of 6 (because it's 6H), something that can be verified by expanding: 3CF - (3AD + 3AE + 3AF + 3BD + 3BE + 3BF + 3CD + 3CE + 3CF) - (AD - AE + AF - BD + BE - BF + CD - CE + CF) + (16AD + 8AE + 4AF + 8BD + 4BE + 2BF + 4CE + 2CE + CF) - 12AD = 3CF - 3AD - 3AE - 3AF - 3BD - 3BE - 3BF - 3CD - 3CE - 3CF - AD + AE - AF + BD - BE + BF - CD + CE - CF + 16AD + 8AE + 4AF + 8BD + 4BE + 2BF + 4CD + 2CE + CF - 12AD = 3CF - 3CF - CF + CF - 3AD - AD + 16AD - 12AD - 3AE + AE + 8AE - 3AF - AF + 4AF - 3BD + BD + 8BD - 3BE - BE + 4BE - 3BF + BF + 2BF - 3CD - CD + 4CD - 3CE + CE + 2CE which (reassuringly!) leaves only 6AE + 6BD. <0, 1, -1, 2, inf> is possibly the best choice: Using 0, 1, -1, 2, -2 instead gives [ 0 1 1 16 16 ] [ 1/4 0 -5/4 0 1 ] [ 0 1 -1 8 -8 ] [ -1/6 -1/6 2/3 2/3 0 ] [ 0 1 1 4 4 ] whose inverse is [ -1/6 1/6 2/3 -2/3 0 ] [ 0 1 -1 2 -2 ] [ 1/24 1/12 -1/24 -1/12 0 ] [ 1 1 1 1 1 ] [ 1/24 -1/12 -1/24 1/12 0 ] Using 0, 1, 2, 3, 4 instead gives [ 0 1 16 81 256 ] [ 1/24 -5/12 35/24 -25/12 1 ] [ 0 1 8 27 64 ] [ -1/6 3/2 -13/3 4 0 ] [ 0 1 4 9 16 ] whose inverse is [ 1/4 -2 19/4 -3 0 ] [ 0 1 2 3 4 ] [ -1/6 7/6 -7/3 4/3 0 ] [ 1 1 1 1 1 ] [ 1/24 -1/4 11/24 -1/4 0 ] Each is worse in practice than the above. Using -inf is no help; that results in a line that's redundant with the inf line, because the top powers are even. ================================================================ Toom-4: P1(x) = A x^3 + B x^2 + C x + D P2(x) = E x^3 + F x^2 + G x + H PP(x) = I x^6 + J x^5 + K x^4 + L x^3 + M x^2 + N x + O Use, eg, 0, 1, -1, 2, -2, 3 and infinity, to give 7 points to specify PP(): x = 0 1 -1 2 -2 3 inf [ A B C D ] [ 0 1 -1 8 -8 27 1 ] [ P1(0) P1(1) P1(-1) P1(2) P1(-2) P1(3) P1(inf) ] [ ] [ 0 1 1 4 4 9 0 ] = [ ] [ ] [ 0 1 -1 2 -2 3 0 ] = [ ] [ E F G H ] [ 1 1 1 1 1 1 0 ] [ P2(0) P2(1) P2(-1) P2(2) P2(-2) P2(3) P2(inf) ] recurse 7 times: PP(0) = P1(0) P2(0) = D H PP(1) = P1(1) P2(1) = (A + B + C + D) (E + F + G + H) PP(-1) = P1(-1) P2(-1) = (D - C + B - A) (H - G + F - E) PP(2) = P1(2) P2(2) = (8A + 4B + 2C + D) (8E + 4F + 2G + H) PP(-2) = P1(-2) P2(-2) = (-8A + 4B - 2C + D) (-8E + 4F - 2G + H) PP(3) = P1(3) P2(3) = (27A + 9B + 3C + D) (27E + 9F + 3G + H) PP(inf) = P1(inf) P2(inf) = A E [ 0 1 1 64 64 729 1 ] [ 0 1 -1 32 -32 243 0 ] [ 0 1 1 16 16 81 0 ] [ I J K L M N O ] [ 0 1 -1 8 -8 27 0 ] = [ PP(0) PP(1) PP(-1) PP(2) PP(-2) PP(3) PP(inf) ] [ 0 1 1 4 4 9 0 ] [ 0 1 -1 2 -2 3 0 ] [ 1 1 1 1 1 1 0 ] inverse is [ 0 -1/12 1/4 5/12 -5/4 -1/3 1 ] [ 0 1/12 -1/6 -7/12 2/3 1 0 ] [ 0 1/24 -1/6 -1/24 2/3 -1/2 0 ] [ 0 -1/24 1/24 7/24 -1/24 -1/4 0 ] [ 0 -1/120 1/24 -1/24 -1/24 1/20 0 ] [ 0 1/120 0 -1/24 0 1/30 0 ] [ 1 -3 -5 15 4 -12 0 ] O(7^(log4 n)) = O(n^(log4 7)) ~ O(n^1.40368) Here, the top power is odd in the P1(x) and P2(x) formulae, but using -inf still doesn't help: the power is even in PP(inf) and the minus signs cancel in the P1(-inf) P2(-inf) product, so it's redundant. ================================================================ Toom-2, formulation 1: P1(x) = A x + B P2(x) = C x + D PP(x) = AC x^2 + (AD+BC) x + BD = E x^2 + F x + G Use, eg, 0, 1, and infinity, to give 3 points to specify PP(): x = 0 1 inf [ A B ] [ 0 1 1 ] [ P1(0) P1(1) P1(inf) ] [ ] [ ] = [ ] [ C D ] [ 1 1 0 ] [ P2(0) P2(1) P2(inf) ] recurse 3 times: PP(0) = P1(0) P2(0) = B D PP(1) = P1(1) P2(1) = (A + B) (C + D) PP(inf) = P1(inf) P2(inf) = A C [ 0 1 1 ] [ E F G ] [ 0 1 0 ] = [ PP(0) PP(1) PP(inf) ] [ 1 1 0 ] -1 [ 0 1 1 ] [ E F G ] = [ PP(0) PP(1) PP(inf) ] [ 0 1 0 ] [ 1 1 0 ] or [ 0 -1 1 ] [ E F G ] = [ PP(0) PP(1) PP(inf) ] [ 0 1 0 ] [ 1 -1 0 ] O(3^(log2 n)) = O(n^(log2 3)) ~ O(n^1.58496) This version is equivalent to original Karatsuba. ================================================================ Toom-2, formulation 2: P1(x) = A x + B P2(x) = C x + D PP(x) = AC x^2 + (AD+BC) x + BD = E x^2 + F x + G Use, eg, 0, -1, and infinity, to give 3 points to specify PP(): x = 0 -1 inf [ A B ] [ 0 -1 1 ] [ P1(0) P1(-1) P1(inf) ] [ ] [ ] = [ ] [ C D ] [ 1 1 0 ] [ P2(0) P2(-1) P2(inf) ] recurse 3 times: PP(0) = P1(0) P2(0) = B D PP(-1) = P1(-1) P2(-1) = (B - A) (D - C) PP(inf) = P1(inf) P2(inf) = A C [ 0 1 1 ] [ E F G ] [ 0 -1 0 ] = [ PP(0) PP(-1) PP(inf) ] [ 1 1 0 ] -1 [ 0 1 1 ] [ E F G ] = [ PP(0) PP(1) PP(inf) ] [ 0 -1 0 ] [ 1 1 0 ] or [ 0 1 1 ] [ E F G ] = [ PP(0) PP(1) PP(inf) ] [ 0 -1 0 ] [ 1 1 0 ] O(3^(log2 n)) = O(n^(log2 3)) ~ O(n^1.58496) This version is equivalent to alternative Karatsuba with subtraction to avoid recursive number bloat. ================================================================ Toom-2, formulation 3: P1(x) = A x + B P2(x) = C x + D PP(x) = AC x^2 + (AD+BC) x + BD = E x^2 + F x + G Use, eg, 0, -1, and 1, to give 3 points to specify PP(): x = 0 -1 1 [ A B ] [ 0 1 -1 ] [ P1(0) P1(-1) P1(1) ] [ ] [ ] = [ ] [ C D ] [ 1 1 1 ] [ P2(0) P2(-1) P2(1) ] recurse 3 times: PP(0) = P1(0) P2(0) = B D PP(-1) = P1(-1) P2(-1) = (B - A) (D - C) PP(1) = P1(1) P2(1) = (A + B) (C + D) [ 0 1 1 ] [ E F G ] [ 0 -1 1 ] = [ PP(0) PP(-1) PP(1) ] [ 1 1 1 ] -1 [ 0 1 1 ] [ E F G ] = [ PP(0) PP(-1) PP(1) ] [ 0 -1 1 ] [ 1 1 1 ] or [ -1 0 1 ] [ E F G ] = [ PP(0) PP(-1) PP(1) ] [ 1/2 -1/2 0 ] [ 1/2 1/2 0 ] O(3^(log2 n)) = O(n^(log2 3)) ~ O(n^1.58496) This gives a Karatsubaish reformulation (A b + B) (C b + D) = E b^2 + F b + G E = 1/2 (B - A) (D - C) + 1/2 (A + B) (C + D) - B D F = 1/2 (A + B) (C + D) - 1/2 (B - A) (D - C) G = B D which, while it will work, is more complex than either of the above two Toom-2 formulations and thus of no practical interest. ================================================================