Лекция 5 (2)

1. «Разделяй и властвуй»: умножение чисел

Алгоритмы и структуры данных (с примерами на языках Python и R)

2. Сложение в столбик: O(n)

3. Умножение в столбик: O(n2)

2
Умножение в столбик: O(n )

4. Рекуррентная формула

5. Рекуррентная формула

6. Алгоритм

Условие
• Реализуйте программу, которая вычисляет произведение двух
неотрицательных целых чисел x и y с использованием рекурсивного
алгоритма.
Идея алгоритма
• если y = 0, результат равен 0;
• рекурсивно вычисляется произведение x и ⌊y / 2⌋;
• если y чётно, результат равен 2z;
• если y нечётно, результат равен x + 2z, где z = multiply(x, ⌊y / 2⌋).

7. multiply (Python)

def multiply(x, y):
"""
x, y: неотрицательные целые числа
Возвращает произведение x * y.
"""
if y == 0:
return 0
z = multiply(x, y // 2)
if y % 2 == 0:
return 2 * z
else:
return x + 2 * z

8. multiply (R)

multiply <- function(x, y) {
# x, y: неотрицательные целые числа
# Возвращает произведение x * y
if (y == 0) {
return(0)
}
z <- multiply(x, y %/% 2)
if (y %% 2 == 0) {
return(2 * z)
} else {
return(x + 2 * z)
}
}

9. Ещё одна рекуррентная формула

10. Ещё одна рекуррентная формула

11. Ещё одна рекуррентная формула

12. Улучшенная рекуррентная формула

13. Улучшенная рекуррентная формула

14. Улучшенная рекуррентная формула

15. Улучшенная рекуррентная формула

16. Улучшенная рекуррентная формула

17. Алгоритм Карацубы (Python)

def karatsuba(x, y):
"""
x, y: неотрицательные целые числа
Возвращает произведение x * y по алгоритму Карацубы.
"""
n = max(x.bit_length(), y.bit_length())
if n <= 1:
return x * y
half = n // 2
x_l = x >> half
x_r = x - (x_l << half)
y_l = y >> half
y_r = y - (y_l << half)
p_1 = karatsuba(x_l, y_l)
p_2 = karatsuba(x_r, y_r)
p_3 = karatsuba(x_l + x_r, y_l + y_r)
return (p_1 << (2 * half)) + ((p_3 - p_1 - p_2) << half) + p_2

18. Алгоритм Карацубы (R)

karatsuba <- function(x, y) {
# x, y: неотрицательные целые числа Возвращает произведение x*y
bit_length <- function(n) {
if (n == 0) {
return(1)
}
length(intToBits(as.integer(n))) - match(1, rev(intToBits(as.integer(n)))) + 1
}
n <- max(bit_length(x), bit_length(y))
if (n <= 1) {
return(x * y)
}
half <- n %/% 2
x_l <- x %/% (2 ^ half)
x_r <- x %% (2 ^ half)
y_l <- y %/% (2 ^ half)
y_r <- y %% (2 ^ half)
p_1 <- karatsuba(x_l, y_l)
p_2 <- karatsuba(x_r, y_r)
p_3 <- karatsuba(x_l + x_r, y_l + y_r)
return(p_1 * (2 ^ (2 * half)) + (p_3 - p_1 - p_2) * (2 ^ half) + p_2)
}

19. Дерево рекурсии

20. Дерево рекурсии

21. Дерево рекурсии

22. Дерево рекурсии

23. Оценка времени работы

24. Оценка времени работы

25. Оценка времени работы

26. Оценка времени работы

27. Оценка времени работы

28. Оценка времени работы

29. Оценка времени работы

30. Сумма геометрической прогрессии: формула

31. Сумма геометрической прогрессии: формула

32. Сумма геометрической прогрессии: формула

33. Сумма геометрической прогрессии: скорость роста

34. Сумма геометрической прогрессии: скорость роста

35. Сумма геометрической прогрессии: скорость роста

36. Оценка на время работы

37. Оценка на время работы

38. Оценка на время работы

39. Оценка на время работы

40. Оценка на время работы

41. Почему можно считать, что n = 2k?

k
Почему можно считать, что n = 2 ?

42. Заключение

• сложение двух n-битовых чисел: O(n);
• умножение двух n-битовых чисел в столбик: O(n2);
• алгоритм Карацубы умножения двух n-битовых чисел: O(n1.59).