libzahl

commit b9ba3cb8db7ad2541ed923f8e80956f7230b2ac8
parent 6a56b2eb154636e48d8f07aa3864bbc3885b99a1
Author: Mattias Andrée <maandree@kth.se>
Date:   Sun,  6 Mar 2016 21:48:04 +0100

A description of the Karatsuba algorithm

Signed-off-by: Mattias Andrée <maandree@kth.se>

Diffstat:
M
src/zmul.c
 | 
6
++++++

1 file changed, 6 insertions(+), 0 deletions(-)
diff --git a/src/zmul.c b/src/zmul.c
@@ -7,6 +7,12 @@ zmul(z_t a, z_t b, z_t c)
 {
 	/*
 	 * Karatsuba algorithm
+	 * 
+	 * Basically, this how you were toughed to multiply large numbers
+	 * by hand in school: 4010⋅3020 = (4000 + 10)(3000 + 20) =
+	 = 40⋅30⋅10⁴ + (40⋅20 + 30⋅10)⋅10² + 10⋅20, but the middle is
+	 * optimised to only one multiplication:
+	 * 40⋅20 + 30⋅10 = (40 + 10)(30 + 20) − 40⋅30 − 10⋅20.
 	 */
 
 	size_t m, m2;