On Mon, 7 Mar 2016 14:08:04 +0200
Vasily Kolobkov <polezaivsani_AT_openmailbox.org> wrote:
> From 9677f7bf03f91966a5118033a7fdcb641c1dc935 Mon Sep 17
> 00:00:00 2001 From: Vasily Kolobkov <>
> Date: Mon, 7 Mar 2016 14:00:06 +0200
> Subject: [PATCH] Attune example to classical axiomatics
>
> ---
> src/zmul.c | 2 +-
> 1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/src/zmul.c b/src/zmul.c
> index 6023664..71115df 100644
> --- a/src/zmul.c
> +++ b/src/zmul.c
> _AT_@ -6,15 +6,15 @@ void
> zmul(z_t a, z_t b, z_t c)
> {
> /*
> * Karatsuba algorithm
> *
> * Basically, this is how you were taught 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
> + = 4⋅3⋅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;
> z_t z0, z1, z2, b_high, b_low, c_high, c_low;
> int b_sign, c_sign;
Sorry, it is correct. 4010 is split to 40⋅10² + 10, and
3020 is split to 30⋅10² + 20. 40⋅10² ⋅ 30⋅10² = 40⋅30⋅10⁴.
Simplifying further to 4⋅3⋅10⁶ would be misleading as that
is not how it is calculated in the Karatsuba algorithm,
rather 40⋅30 is calculated with Karatsuba algorithm and
therefore split again.
Received on Mon Mar 07 2016 - 13:35:13 CET