"balanced" unbalanced toom22

[David Harvey]

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  
> cases).
>
> 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.

Nice example.

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.

david