Алгоритм Karatsuba. Алгоритм быстрого возведения в степень

Алгоритм Karatsuba

Алгоритм Karatsuba - это эффективный метод умножения больших целых чисел. Он основан на разбиении чисел на более мелкие части и последующем умножении этих частей с использованием рекурсии.

Алгоритм работает следующим образом:

Если числа a и b достаточно малы (меньше 10), то умножаем их обычным способом и возвращаем результат.
Разбиваем числа a и b на две части пополам. Пусть a1 и a0 - левая и правая части числа a, соответственно, а b1 и b0 - левая и правая части числа b.
Вычисляем следующие произведения:
- z0 = Karatsuba(a1,b1)
- z2 = Karatsuba(a0,b0)
- z1 = Karatsuba(a1 + a0, b1 + b0) – z0 – z2
Возвращаем результат умножения a и b в виде: z0 * 10^(2n) + z1 * 10^n + z2 где n - количество цифр в каждой из частей числа (т.е. половине от общего количества цифр).

Рекурсивное применение алгоритма Karatsuba позволяет уменьшить сложность умножения двух n-значных чисел с O(n^2) до O(n^(1.58)), что делает его особенно эффективным для работы с очень большими числами.

python

def karatsuba(x, y):
	# БАЗА: Если числа достаточно малы, умножаем их обычным способом.
	if len(str(x)) == 1 or len(str(y)) == 1:
		return x * y
	
	# Разбиваем числа X и Y на две части попалам
	n = max(len(str(x)), len(str(y))) // 2
	xLeft, xRight = divmod(x, 10 ** n)
	yLeft, yRight = divmod(y, 10 ** n)
	
	# Рекурсивно вычисляем значения
	z0 = karatsuba(xLeft, yLeft) # 1 5 = 5
	z2 = karatsuba(xRight, yRight) # 2 6 = 12
	z1 = karatsuba(xLeft + xRight, yLeft + yRight) - z0 - z1
	# 3 11 = 33 - 5 - 12
	return z0 * 10**(2*n) + z1 * 10**n + z2

Алгоритм быстрого возведения в степень

Алгоритм быстрого возведения в степень - алгоритм быстрого возведения в степень является эффективным методом для возведения числа в большую степень. Он основан на методе разделяй и властвуй и использует бинарное представление степени. Сложность O(logN)

Алгоритм:

Если степень n равняется 0, то возвращаем число 1.
Если степень n равняется 1, то возвращаем число a.
Если степень n четная, то разбиваем задачу на две подзадачи, каждая из которых состоит в возведении числа a в степень, в два раза меньшую исходной, и последующем возведении результата в квадрат. (Если n четное, то результат = (a^2)^(n/2))
Если степень n нечетная, то разбиваем задачу на две подзадачи, первая из которых состоит в возведении числа a в степень, на единицу меньшую исходной, а вторая - в возведении результата первой подзадачи в квадрат и последующем умножении на число a. (Если n нечетное, то результат = a * (a^2)^((n-1)/2))

python

def power(a, n):
	if n == 0:
		return 1
	if n == 1:
		return a
	if n % 2 == 0:
		return power(a * a, n // 2)
	return a * power(a * a, (n - 1) // 2)

Алгоритм Karatsuba. Алгоритм быстрого возведения в степень ​