xy=(x0+B*x1)(y0+B*y1)=x0y0 + (x0*y1+x1*y0)B + x1*y1*B²

there are four multiplications of smaller numbers, also here the calculation time is proportional to n². However

(x0*y1+x1*y0)=(x0+x1)(y0+y1)-x0*y0-x1*y1

why it's enough to calculate three smaller multiplications

x0*y0, x1*y1 and (x0+x1)(y0+y1).

The multiplication with B are fast left shifting and if the shifting and the addition where cost free, the recursive Karatsuba multiplication would be very efficient

but unfortunately the extra math (and in Forth also some stack juggling) takes a lot of time and the method is efficient only for rather big numbers. For very big numbers, however, it's very efficient.

Here is the way I implemented it in ANS Forth:

: bcells* \ big m -- big*C^m

cells top$ locals| n ad mb |

ad ad mb + n move

ad mb erase

mb bvp @ +! ;

\ C is the number of digits in a cell

: bcells/ \ big m -- big/C^m

cells top$ locals| n ad mb |

ad mb + ad n move

mb negate bvp @ +! ;

dup nextfree <

if bvp @ dup @ vp+ bvp @ ! !

else drop bzero

then ;

\ A big number is split on the big stack at address ad

: btransmul \ x y -- x0 x1 y0 y1 m B=2^bits

len1 len2 max cell + lcell 1+ rshift \ m

dup >r cells

>bx first over + bsplit

bx> first + bsplit r> ;

\ x=x0+x1*B^m y=y0+y1*B^m

0x84 value karalim \ break point byte length for termination.

: b* \ x y -- xy

len1 len2 max karalim <

if b* exit then

btransmul >r \ x0 x1 y0 y1

3 bpick 2 bpick recurse >bx \ bx: x0*y0

2 bpick 1 bpick recurse >bx \ bx: x0*y0 x1*y1

b+ >bx b+ bx> recurse \ (x0+x1)(y0+y1)

bx b- by b- r@ bcells* \ z1*C^m

bx> r> 2* bcells* bx> b+ b+ <top ;

\ Karatsuba multiplication

## No comments:

## Post a Comment