daily pastebin goal
46%
SHARE
TWEET

Recursive Karatsuba Pseudocode

Zeda Jul 4th, 2017 46 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top