Реализация алгоритма Карацуба в python - PullRequest
Новая
       77

Реализация алгоритма Карацуба в python

0 голосов
/ 03 мая 2020

Ниже моя реализация python для алгоритма умножения Карацубы. Этот код, кажется, работает для большинства входных данных, но начинает давать сбой, когда цифры становятся слишком большими Например, при 64 ди git входах x = 3141592653589793238462643383279502884197169399375105820974944592 y = 2718281828459045235360287471352662497757247093699959574966967627 алгоритм завершается ошибкой. Но когда я использую только первые 35 цифр, алгоритм работает. Может кто-нибудь объяснить, где эта реализация не хватает? 

from math import floor, ceil
def karatsuba(x, y):
  sx = str(x)
  sy = str(y)
  n = max(len(sx), len(sy))
  if len(sx) == 1 and len(sy) == 1:
    return x*y
  m = ceil(n/2)
  a = int(x / (10**m))
  b = int(x % (10**m))
  c = int(y / (10**m))
  d = int(y % (10**m))
  ac = karatsuba(int(a), int(c))
  bd = karatsuba(int(b), int(d))
  adbc = karatsuba(int(a) + int(b), int(c) + int(d)) - ac - bd
  return int(str(ac) + '0' * 2 * m) + int(str(adbc) + '0' * m) + bd

1 Ответ

1 голос
/ 03 мая 2020 
a = int(x / (10**m))
c = int(y / (10**m))

Эти две строки подвержены ошибкам округления. В python3 оператор / является оператором деления с плавающей запятой. Просто измените / на // для целочисленного деления.

Попробуйте этот код, чтобы увидеть проблему 

x = 2222222222222222222222222222222222
p = 10**17
print(int(x/p))
print(int(x//p))
...