Множення великих чисел методом Карацуби
Автор: Мар'ян Сеньків • Октябрь 9, 2022 • Лабораторная работа • 411 Слов (2 Страниц) • 177 Просмотры
Міністерство освіти і науки України
Тернопільський національний технічний університет імені Івана Пулюя
Кафедра комп’ютерних наукових
Звіт
з лабораторної роботи №1
з курсу: “Теорія алгоритмів”
на тему: “ Множення великих чисел методом Карацуби”
Прийняв:
Михайлович Т. В.
Тернопіль, 2021
Лабораторна робота №1
Завдання:
[pic 1]
Хід роботи
Код (Python):
import math
amount_105 = 0
amount_72 = 0
amount_12 = 0
def calculateKaratsuba(x, y):
x = str(x)
y = str(y)
len_x = len(x)
len_y = len(y)
global amount_105, amount_72, amount_12
n = max(len_x, len_y)
if n == 1:
return int(x)*int(y)
half_n = n // 2
devider_x = len_x - half_n
devider_y = len_y - half_n
a = x[0:devider_x]
b = x[devider_x:len_x]
c = y[0:devider_y]
d = y[devider_y:len_y]
if a == '':
a = 0
if b == '':
b = 0
if c == '':
c = 0
if d == '':
d = 0
ac = calculateKaratsuba(a, c) # a*c
bd = calculateKaratsuba(b, d) # b*d
multipy = calculateKaratsuba( int(a) + int(b) , int(c) + int(d) ) #(a+b)*(c+d)
...