• API
• FAQ
• Tools
• Archive
daily pastebin goal
13%
SHARE
TWEET

# Recursive Karatsuba Pseudocode

Zeda Jul 4th, 2017 48 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.

Top