The Coq mailing list

[roconnor AT theorem.ca]

I have a new revised version of Karatsuba's Multiplication, O(n^lg 3), in
Coq.  It is available at <http://r6.ca/Karatsuba/Karatsuba.tar.gz>.  The
revised version has removed all internal proof objects, and no longer uses
well-founded recursion.  The result is that the code less obviously
implements Karatsuba's Multiplication correctly, but it now runs fast
under call-by-value evaluation.  It is, of course, proved that this
multiplication is extensionally equivalent to regular multiplication.

-- 
Russell O'Connor                                      <http://r6.ca/>
``All talk about `theft,''' the general counsel of the American Graphophone
Company wrote, ``is the merest claptrap, for there exists no property in
ideas musical, literary or artistic, except as defined by statute.''