daily pastebin goal
46%
SHARE
TWEET

Recursive Karatsuba Pseudocode

Zeda Jul 4th, 2017 43 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. This is pseudocode for a space-optimized recursive implementation of the Karatsuba multiplication algorithm.
  2.  
  3. MUL(X,Y,N):
  4. ;X points to the first multiplicand of N digits
  5. ;Y points to the second multiplicand of N digits
  6. ;N is an integer power of 2
  7. ;Assumes yucky big endian
  8.     X.loc = scrap-6+4N  ;\
  9.     Y.loc = X.loc+N     ; |The location of the local X,Y, and Z vars
  10.     Z.loc = Y.loc+N     ; |M is the location of the results of sub multiplies
  11.     M.loc = X.loc-N     ;/
  12.     IF N==1:            ;\
  13.         X*Y->Z[0:2]     ; |Base Case
  14.         RETURN          ;/
  15.     COPY(X,inputX,N)    ;Copy the input X to the local X variable
  16.     COPY(Y,inputY,N)    ;Copy the input Y to the local Y variable
  17.     MUL(X[N/2:N],Y[N/2:N],N/2)  ;Multiply the bottom half of the digits of X and Y
  18.     COPY(Z[N:2N],M,N)           ;Copy the result of the previous multiply to the bottom half of Z
  19.     MUL(X[0:N/2],Y[0:N/2],N/2)  ;Multiply the top half of the digits of X and Y
  20.     COPY(Z[0:N],M,N)            ;Copy the result of the previous multiply to the top half of Z
  21.     sign=0
  22.     SUB(X[0:N/2],X[N/2:N],N/2)  ;Subtract the bottom half of X from the top half, returning flags
  23.     IF underflow
  24.         NEG(X[0:N/2],N/2)
  25.         sign=1
  26.     SUB(Y[0:N/2],Y[N/2:N],N/2)  ;Subtract the bottom half of Y from the top half, returning flags
  27.     IF underflow
  28.         NEG(Y[0:N/2],N/2)
  29.         sign=~sign
  30.     MUL(X[0:N/2],Y[0:N/2],N/2)
  31.     SUB(M[0:N],Z[0:N],N)
  32.     SUB(M[0:N],Z[N:2N],N)
  33.     IF sign==1
  34.         ADDir(Z[0:3N/2],M[0:N],N) ;ADD N digits, then continue as long as there is overflow
  35.         RETURN
  36.     ELSE
  37.         SUBir(Z[0:3N/2],M[0:N]) ;SUB N digits, then continue as long as there is underflow
  38.         RETURN
RAW Paste Data
Top