CheesecakeCuber
Veteran
Only two mistakes:
your coefficients (including 'answer') should be strings because you're ljusting them. Also watch out. Don't add strings to get the answer cuz thats concatenating. (aka 123+ 456= 123456)
You're ljusting to 2*minLength+len answer. You know what it should be, I hopeimport time
import math
import random
#Karatsuba alg is cool
def splitString(string,number):
#Converts "string" variable input to string then splits for Karatsuba
string = str(string)
return [string[0:len(string)-number], string[len(string)-number:len(string)]]
def karatsubaMulti(x,y):
#Where "x" and "y" are your factors
minLength = min(len(str(x))/2,len(str(y))/2)
if int(minLength) <= 1:
#Does naive alg
return x*y
else:
a = int(splitString(x,minLength)[0])
b = int(splitString(x,minLength)[1])
c = int(splitString(y,minLength)[0])
d = int(splitString(y,minLength)[1])
coefficient1 = str(karatsubaMulti(a,c))
coefficient2 = str(karatsubaMulti(b,d))
try:
answer = str((karatsubaMulti((a + b),(c + d)) - int(coefficient1) - int(coefficient2)))
except:
answer = str(((a + b)*(c + d) - int(coefficient1) - int(coefficient2)))
return int(coefficient1.ljust((int(2*minLength)) + (len(coefficient1)),'0')) + int(answer.ljust(int(minLength) + int(len(answer)),'0')) + int(coefficient2)
k=0
##test 12000 times for errors
for awsiuhfds in range(0,1200):
ta,tb = random.randint(220,20000000),random.randint(220,20000000)
if karatsubaMulti(ta,tb)==ta*tb:
k=k+1
pass
else:
print karatsubaMulti(ta,tb)
print ta*tb
print "----"
raw_input(str(k)+" successes out of 1200.")
OMG, I'm so stoopid. Thanks Alex. I really appreciate all your help through my tedious project. I hope I didn't annoy you with my trivial questions.
yea...twill be furn tho, when I can akchually compute successfully. It'll be liek when you helped me with Karatsuba. Karatsuba seems so simple nao. I even wrote a zero padding function, that, to my knoledge, werks. Just needs to be formatted since my keyboards stoopid...
