From b9ba3cb8db7ad2541ed923f8e80956f7230b2ac8 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Sun, 6 Mar 2016 21:48:04 +0100 Subject: A description of the Karatsuba algorithm MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- src/zmul.c | 6 ++++++ 1 file changed, 6 insertions(+) diff --git a/src/zmul.c b/src/zmul.c index 53e19f5..5b35d93 100644 --- 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; -- cgit v1.2.3-70-g09d2