J'essaye de faire la multiplication de Karatsuba. Chaque fois que le nombre de chiffres dépasse 16, python remplit les valeurs d'ordures à la fin lors de la multiplication par une puissance de 10Python en ajoutant des valeurs de poubelle à la fin du nombre sur la multiplication
Par exemple:
5789640666777942 * pow (10, 16) = 57896406667779421501721023610880
OU
10023051467610476 * pow (10, 8) = 1002305146761047575625728
Je suis à la fin de mon esprit pour résoudre ce problème. Je travaille sur le code depuis un mois (avec d'autres parties entre les deux). Toute aide serait appréciée.
EDIT: affichage du code entier:
def Karatsuba(X, Y, n):
m = long(ceil(1.0*long(long(n)/2)))
n = long(2*long(m))
dem = pow(10, long(m))
a = long(long(X)/dem)
b = long(long(X)%dem)
c = long(long(Y)/dem)
d = long(long(Y)%dem)
print "X %d Y %d" % (X, Y)
print "a b c d n m = %d %d %d %d %d %d" %(a, b, c, d, n, m)
if n > 2:
print "n > 2 hence m n %d %d" % (m, n)
p = long(Karatsuba(long(a), long(c), long(m)))
print "p = %d" % p
q = long(Karatsuba(long(b), long(d), long(m)))
print "q = %d" % q
r = long(Karatsuba(long(long(a)+long(b)), long(long(c)+long(d)), long(m)))
print "r = %d" % r
r = long(long(r) - long(p) - long(q))
print "p = %d" % p
print "q = %d" % q
print "r = %d" % r
else:
print "n <= 2 hence m n %d %d" % (m, n)
p = a*c
print "P, A, C = %d %d %d" % (p, a, c)
q = b*d
print "Q, B, D = %d %d %d" % (q, b, d)
r = (a+b) * (c+d) - p - q
print "P = %d" % p
print "Q = %d" % q
print "R = %d" % r
result = long(add(add(long(q), long(long(r) * pow(10, long(m)))), long(long(p) * pow(10, long(n)))))
print "result %d p %d n %d p*pow(10, n) %d r %d m %d r*pow(10, m) %d q %d" %(long(result), long(p), long(n), long(long(p)*pow(10, long(n))), long(r), long(m), long(long(r)*pow(10, long(m))), long(q))
return str(result)
X = long(argv[1])
Y = long(argv[2])
print Karatsuba(X, Y, len(argv[1]))
Je suis en train de se multiplier: 7878064237045606 7349065192669285 et
J'utilise l'ordinateur 64 bits. Et python est 2.7.12. 64 bits.
Fermeture de la question. Solution trouvée ici:
Karatsuba algorithm working for small numbers but not for big ones, can't see why
Problème est la fonction de puissance donne la sortie comme flottant. Construit en ** fonctionne mieux.
Je ne peux reproduire aucun de vos exemples. Publiez un exemple complet présentant le problème. (Je suppose que vous avez une valeur à virgule flottante intermédiaire.) – molbdnilo
Mise à jour de la question. Pouvez-vous vérifier maintenant? –
Attendez, votre fonction Karatsuba donne-t-elle la mauvaise sortie? Ou une multiplication de pythons? –