Hacker Newsnew | comments | show | ask | jobs | submit login

I think only smaller than 4...

I wonder if this works in binary :D




That was my first thought, so I checked, and yes, it does. You just change the carrying rules. But by the time you've accounted for the number of digits you'd need to do anything useful, it's fairly useless except from a theoretical computational perspective - even when converted to logic circuits, I'm guessing it's not the most efficient solution out there.

-----


Actually, this method is one of the most efficient ways to multiply in software. It's called the "Comba" method in that context, and is efficient for multiplying 32x32 words or smaller, due to cache effects and function overhead required by more complicated algorithms. Over about 32 words on many architectures, the algorithmic advantage of the Karatsuba method wins out.

-----




Applications are open for YC Winter 2016

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: