Karatsuba multiplication

The time for direct multiplication is proportional to n² where n is the number of figures in the multiplicands x,y. When choosing a big base B=2ⁿ and and writing

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 @ +! ;

: bsplit \ w ad -- u v 
  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

How to use BigZ - part 3

The binomial coefficients for big integers

The number of possibilities to choose k objects from n objects soon get to big for a single cell number. The word bschoose gives a big integer result for single cell inputs.

: bschoose \ n k -- b
  bone 0
  ?do dup i - bs*
     i 1+ bs/mod drop
  loop drop ;

 ok
2000 500 bschoose cr b.
5648284895675941420424412140748481039502890353942825357221051675360331984776743417002364625179991976070068866284527555107208940603781511988000970130381311935878493235111594076219803768997324618773852975824828528735285833615310777764160933348372329757027402537319600321600269195597902747298520883357267710485334098751949232380773741897267988881873218260056305793069941805234442045890109611836653468404129012879905442075185208447514284775689056520318572740750419026192611832748925888424320  ok

This word produce big integers with single cell factors that can be analysed by the word 

sfacset \ b -- b' set

2000 1000 bschoose sfacset bdrop cr zet.

{2,5,7,11,13,17,19,23,37,41,43,53,59,67,73,79,101,103,113,127,131,149,151,167,173,179,181,211,251,257,263,269,271,277,281,283,337,347,349,353,359,367,373,379,383,389,397,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999} ok

The word bsetprod calculates the big product of the singles in set

: bsetprod \ set -- b
  bone                   \ big one
  foreach                \ make ready for do-loop
  ?do zst> bs* loop ;

and can be used to calculate the radical for big integers with single cell factors:

: bsradical \ b -- b'
  sfacset bdrop 
  bsetprod ;

50 25 bschoose bsradical cr b.
1504888171878  ok

Erdős squarefree conjecture (proved 1996) states that the central binomial coefficient (2n)Cn is not squarefree if n>4. The word sqrfacset calculates the set of all factors that occurs more than once: 

: sqrfacset \ b -- set
  bdup bsradical b/
  sfacset bdrop ;

20000 10000 bschoose sqrfacset cr zet.
{2,3,7,11,23,29,41,47,53,61,71,73,79,109,127,137,139} ok

The word

: maxel \ set -- n   non e
  zst> zst@ swap >zst zdrop ;

gives the maximal element in a set of integers.

: erdprime \ n -- p
  dup 2* swap bschoose
  sqrfacset maxel ;