• Tim Peters's avatar
    x_mul(): This failed to normalize its result. · 44121a6b
    Tim Peters yazdı
    k_mul():  This didn't allocate enough result space when one input had
    more than twice as many bits as the other.  This was partly hidden by
    that x_mul() didn't normalize its result.
    
    The Karatsuba recurrence is pretty much hosed if the inputs aren't
    roughly the same size.  If one has at least twice as many bits as the
    other, we get a degenerate case where the "high half" of the smaller
    input is 0.  Added a special case for that, for speed, but despite that
    it helped, this can still be much slower than the "grade school" method.
    It seems to take a really wild imbalance to trigger that; e.g., a
    2**22-bit input times a 1000-bit input on my box runs about twice as slow
    under k_mul than under x_mul.  This still needs to be addressed.
    
    I'm also not sure that allocating a->ob_size + b->ob_size digits is
    enough, given that this is computing k = (ah+al)*(bh+bl) instead of
    k = (ah-al)*(bl-bh); i.e., it's certainly enough for the final result,
    but it's vaguely possible that adding in the "artificially" large k may
    overflow that temporarily.  If so, an assert will trigger in the debug
    build, but we'll probably compute the right result anyway(!).
    44121a6b
Adı
Son kayıt (commit)
Son güncelleme
Demo Loading commit data...
Doc Loading commit data...
Grammar Loading commit data...
Include Loading commit data...
Lib Loading commit data...
Mac Loading commit data...
Misc Loading commit data...
Modules Loading commit data...
Objects Loading commit data...
PC Loading commit data...
PCbuild Loading commit data...
Parser Loading commit data...
Python Loading commit data...
RISCOS Loading commit data...
Tools Loading commit data...
.cvsignore Loading commit data...
.hgtags Loading commit data...
LICENSE Loading commit data...
Makefile.pre.in Loading commit data...
PLAN.txt Loading commit data...
README Loading commit data...
configure Loading commit data...
configure.in Loading commit data...
install-sh Loading commit data...
pyconfig.h.in Loading commit data...
setup.py Loading commit data...