2**HUGENUMBER Why not optimise it?

[Mike C. Fletcher]

 > Do you feel like implementing Karatsuba multiplication in
 > longobject.c?  That might actually be some use...
 >
Too bad I'm not a C programmer... here's a Python version, about 2 x 
slower than in-built mult.  The thing is, I don't see how you determine 
a proper threshold/split value (and all the ones I try wind up with 
horible timings):

import time

def karatsuba( x,y, threshold = 1000 ):
     """Karatsuba multiplication for Python longs

     1) how should threshold be determined
     2) should there be multiple splits for large numbers?
     """
     thresholdValue = (2L**threshold)-1
     # b is the power of 2 at which the split occurs...
     b = 1L<<threshold

     # short circuit if both values are small...
     if x&thresholdValue == x and y&thresholdValue == y:
         return x*y
     elif x<0 or y<0:
         # don't think this works for signed longs
         return x*y
     x0 = x&thresholdValue
     x1 = x>>threshold
     assert x == (x1*b+x0)
     y0 = y&thresholdValue
     y1 = y>>threshold
     assert y == (y1*b+y0)
     return ((1L<<(threshold*2))+b)*x1*y1 - b*(x1-x0)*(y1-y0) + (b+1)*x0*y0


def test( ):
     data = [
         (2L<<1000000,3L<<100000),
         (5L<<1000000,23L<<100000),
         (23L<<1000,45L<<2000),
         (23L<<10000,45L<<20000),
     ]
     for x,y in data:
         t = time.clock()
         a = x*y
         t = time.clock()-t
         print 'regular', t

         t = time.clock()
         b = karatsuba(x,y)
         t = time.clock()-t
         print 'Karatsuba', t
         assert a == b

if __name__ == "__main__":
     test()


Is the idea that you'd want to take a threshold like 30 and run blocks 
of 30 all the way along the number?  Oh, the gmp system seems to have 
Karatsuba multiplication for long ints, incidentally.

Okay, I feel better now, afternoon's work whacked by a chance to learn 
something new :) .  Thanks Michael!
Mike


Michael Hudson wrote:
> "Mike C. Fletcher" <mcfletch at rogers.com> writes:
> 
> 
>>Maybe I'll just give up on trying to interest people in Python
>>optimisation challenges.  The good-old days of idle speculation and
>>optimisation are dead.  Time to stop living in the past.  Idea
>>dropped, back to boring GUI work.
> 
> 
> Do you feel like implementing Karatsuba multiplication in
> longobject.c?  That might actually be some use...
> 
> Cheers,
> M.
> 


-- 
_______________________________________
   Mike C. Fletcher
   http://members.rogers.com/mcfletch/