Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Those have better asymptotics but worse constants.


Specifically:

    It follows that, for sufficiently large n, Karatsuba's
    algorithm will perform fewer shifts and single-digit 
    additions than longhand multiplication, even though its 
    basic step uses more additions and shifts than the 
    straightforward formula. For small values of n, however, 
    the extra shift and add operations may make it run 
    slower than the longhand method. The point of positive 
    return depends on the computer platform and context. 
    As a rule of thumb, Karatsuba is usually faster when 
    the multiplicands are longer than 320–640 bits.
https://en.wikipedia.org/wiki/Karatsuba_algorithm#Efficiency...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: