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

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?

At Fri, 04 Jul 2008 03:43:09 +0200,
nicolas cellier wrote:
  Properly putting the pushRemappableOop:/popRemappableOop pair around
the allocation of LargeInt and it should work, as long as the depth of
the remapBuffer doesn't exceed 25.

  Or, you can pass an Array as a buffer (whose size can be calculated
beforehand, I think) from the image and stick the temporary LargeInts
to that buffer.

  It would be convenient if we had a simple interface for

  #allocate:headerSize:h1:h2:h3:doFill:with:

to have the doFill argument be false for arbitrary class.  Right now,
the memory region allocated will be written twice (0's and then the
computed result).  That would be a limiting factor.

-- Yoshiki