Re: Karatsuba multiplication in a plugin using slang, is it doable ?

At Fri, 04 Jul 2008 03:43:09 +0200,
nicolas cellier wrote:
> 
> 
> 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).

  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