"balanced" unbalanced toom22
dmharvey at nyu.edu
Thu Aug 7 18:21:49 CEST 2008
On Aug 7, 2008, at 9:18 AM, Niels Möller wrote:
> It may be more enlightning to investigate (both theoretically and
> practically) what happens with the only *slightly* unbalanced case,
> say 200x198 or more generally n x (n-2). If I get this example right,
> I get for one level of Karatsuba
> 100x100 and 100x98 vs 2 100x99 (and one 100x100 which is the same in
> both cases)
> and after another level
> 50x50 and 50x48 vs 2 50x49 (and an additional 7 50x50 in both
> By induction, this should propagate all the way down until we get
> below the Karatsuba threshold, where there ought to be a very small
> difference, if measurable at all.
Similarly, if you start with 200x196 (to get rid of the odd/even
issue) then after two levels of karatsuba it's
8*(50x50) + 1*(50x46) vs 5*(50x50) + 4*(50x49).
As in your example, these should be the same cost once you reach
subquadratic territory. I think it's clear from these examples that
if you start with something relatively balanced, it shouldn't really
matter which approach you take (except for added overhead).
The thing I find irritating is that induction doesn't quite work, if
you start with something unbalanced enough. In the "balanced"
version, all the nodes in the tree are either full products or
products with about the same amount of unbalanced-ness as the
original product. The "unbalanced" version has all nodes being full
products, except for a single path that gets progressively more
unbalanced. It's very hard to say what happens to that last node.
More information about the gmp-devel