[squeak-dev] Karatsuba multiplication in a plugin using slang, is it doable ?

nicolas cellier ncellier at ifrance.com
Fri Jul 4 01:43:09 UTC 2008


Karatsuba algorithm is a simple divide and conquer algorithm to fast up 
LargeInteger multiplications which is worth above a few thousand bits.
(see http://en.wikipedia.org/wiki/Karatsuba_algorithm).

I would like to implement it in the LargeIntegersPlugin,
But:
- the algorithm is recursive
- it will create short-lived LargeIntegers at each recursion

So that makes me wonder if it is really doable in a plugin in slang, 
given that relocation might occur and mess the pointers...

The idea to handle the algorithm in pure C is just so boring...
(in which case, it would be simpler to handcraft a GMP plugin).

Any advice?




More information about the Squeak-dev mailing list