Тема: Python метод карацуби, потрібна допомога

Привіт, є ось такі числа X = 21625695688898558125310188636840316594920403182768
Y = 13306827740879180856696800391510469038934180115260
Тепер для цих двох значень, що у мене прописані спочатку потрібна кількість скільки раз зустрічалось ad+bc=105, ad+bc=72,ad+bc=12. Мені обраховує, 1 і 3 правильно, а 2 ні . Правильні відповіді при ad+bc=105 — 1 або 3 або 4, ad+bc=72 — 16 або 7, ad+bc=12 — 17 , 15 , 5. Можливо хтось зможе побачити професійним оком, де помилка і виправити іі, буду дуже вдячний
Вот код
import math
dictionary = dict()


def karat(x1, y1):
x1 = str(x1)
y1 = str(y1)

x2 = len(x1)
y2 = len(y1)

if (int(x2) == 1 and int(y2) == 1):
return int(x1) * int(y1)
else:
half1 = int(math.ceil(x2 / 2.0))
half2 = int(math.ceil(y2 / 2.0))

if (half1 < half2):
half = half1
else:
half = half2

h1 = x2 — half
h2 = y2 — half

if h1 == 0:
a = 0
else:
a = int(x1[0:h1])

if h2 == 0:
c = 0
else:
c = int(y1[0:h2])

b = int(x1[h1:x2])
d = int(y1[h2:y2])

ac = karat(a, c)
bd = karat(b, d)
adbc = karat(a + b, c + d) — ac — bd

if adbc in dictionary:
value = dictionary[adbc]
value = value + 1
dictionary.update({adbc: value})
else:
dictionary[adbc] = 1

results = ac * math.pow(10, x2) + adbc * math.pow(10, x2 / 2) + bd

return int(results)



result = karat(168528749932832829781465563927858366791935584939145345 6921116729, 711419284857775458796974462655857153672898316795455299989534 8492)
print(result)
print(’’)
for key in sorted(dictionary.keys()):
print(key, " :: ", dictionary[key])
input()

2

Re: Python метод карацуби, потрібна допомога

normal code (error not fix)

import math
dictionary = dict()

def karat(x1, y1):
    x1 = str(x1)
    y1 = str(y1)

    x2 = len(x1)
    y2 = len(y1)

    if (int(x2) == 1 and int(y2) == 1):
        return int(x1) * int(y1)
    else:
        half1 = int(math.ceil(x2 / 2.0))
        half2 = int(math.ceil(y2 / 2.0))

    if (half1 < half2):
        half = half1
    else:
        half = half2

    h1 = x2 - half
    h2 = y2 - half

    if h1 == 0:
        a = 0
    else:
        a = int(x1[0:h1])

    if h2 == 0:
        c = 0
    else:
        c = int(y1[0:h2])

    b = int(x1[h1:x2])
    d = int(y1[h2:y2])

    ac = karat(a, c)
    bd = karat(b, d)
    adbc = karat(a + b, c + d) - ac - bd

    if adbc in dictionary:
        value = dictionary[adbc]

        value = value + 1
        dictionary.update({adbc: value})
    else:
        dictionary[adbc] = 1

    results = ac * math.pow(10, x2) + adbc * math.pow(10, x2 / 2) + bd

    return int(results)


result = karat(1685287499328328297814655639278583667919355849391453456921116729, 7114192848577754587969744626558571536728983167954552999895348492)
print(result)
print('')

for key in sorted(dictionary.keys()):
    print(key, " :: ", dictionary[key])

input()

3

Re: Python метод карацуби, потрібна допомога

ya ne ponimayou, dai umovu

4

Re: Python метод карацуби, потрібна допомога

Для початку:
- зробіть код читаним. Використовуйте людські назви змінних (x_len, наприклад, виглядає значно краще за x2), стандартні  функції (min) і типи (defaultdict). Код буде легше розбирати - у першу ж чергу вам самому.
- перевірте, чи код працює, на невеликих числах. Порівняйте результат зі звичайним множенням. Наприклад, karat(101,101) у мене видає щось дивне.
- Ось це місце:

adbc * math.pow(10, x2 / 2)

мені виглядає дивним. А якщо x2 непарне?

Подякували: vlad1234562991

5

Re: Python метод карацуби, потрібна допомога

І взагалі, числа з рухомою комою неточні. Ви втрачаєте точність на цих перетвореннях для довгих чисел, там все має бути цілим.

Подякували: vlad1234562991