Стремясь заполнить пробелы в моих знаниях об алгоритмах и структурах данных, я недавно начал курс Coursera по этой теме, предложенный Стэнфордским университетом.
Первое задание по программированию включало построение алгоритма Карацубы на выбранном вами языке для умножения двух 64-значных чисел.
Что такое алгоритм Карацубы?
классический алгоритм разделяй и властвуй
Алгоритм берет две цифры длины n и рекурсивно разделяет эти цифры на длину n / 2, пока они не станут достаточно маленькими для вычисления с использованием умножения длинной рукой (3-го уровня). Рекурсивные алгоритмы - это алгоритмы, которые могут вызывать себя как подпрограмму с меньшим объемом ввода; для рекурсивного вызова подпрограммы входные данные должны быть меньше, чем в предыдущем вызове.
Учитывая входные параметры x и y длины n в некоторой базовой B (например, базе 10), сам алгоритм выглядит так:
x = a* B^m + b y = c* B^m + d x * y = B^m(ac) + B^m/2(ad+bc) + bd
Теперь вместо длительного умножения 1234 x 5678 вы можете сделать следующее:
a = 12 b = 34 c = 56 d = 78 n = 4 base of 10 x * y = 10^n(ac) + 10^(n/2)(ad + bc) + bd x * y = 10⁴(672) + 10²(2840) + 2652 x * y = 7006652
Математика казалась мне магией и имела смысл. Но как реализовать это в Ruby для 64-значного числа?
Я начал с Karatsuba wiki, чтобы найти псевдокод для моей собственной реализации Ruby:
procedure karatsuba(num1, num2) if (num1 < 10) or (num2 < 10) return num1*num2 /* calculates the size of the numbers */ m = max(size_base10(num1), size_base10(num2)) m2 = m/2 /* split the digit sequences about the middle */ high1, low1 = split_at(num1, m2) high2, low2 = split_at(num2, m2) /* 3 calls made to numbers approximately half the size */ z0 = karatsuba(low1,low2) z1 = karatsuba((low1+high1),(low2+high2)) z2 = karatsuba(high1,high2) return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)
Если любой из числовых входов меньше 10, их можно умножить напрямую, поскольку каждый вход содержит только 1 цифру. Затем нам нужно вычислить наибольший целочисленный размер в случае, если два целых числа имеют разную длину, а затем найти приблизительную среднюю точку в каждом целом числе, чтобы найти место для разделения x на a + б. Получив меньшие входные данные a, b, c и d, мы рекурсивно выполняем 3 вызова karatsuba для вычисления ac, ad, bc и bd. Как только у нас есть ac, ad, bc и bd в наименьших возможных единицах, мы вернем их в окончательное уравнение и дополним числа некоторой базой (в псевдокоде выше предполагается, что число базы 10 (например, 100, 1000)).
После нескольких часов набора текста и тестирования вариантов ввода я получил работающую реализацию Ruby!
def make_equal(num, mid, size) string = num.to_s.rjust(size, '0') return string.slice(0...mid).to_i, string.slice(mid..-1).to_i end def karatsuba(num1, num2) return num1 * num2 if num1 < 10 || num2 < 10 size = [num1.to_s.length, num2.to_s.length].max n = size/2 k = (size + 1) / 2 high1,low1 = make_equal(num1, k, size) high2,low2 = make_equal(num2, k, size) z0 = karatsuba(low1,low2) z1 = karatsuba((low1 + high1), (low2 + high2)) z2 = karatsuba(high1,high2) z3 = z1-z0-z2 return z2 * 10**(2*n) + ((z3) * 10**(n)) + z0 end
Целью вспомогательного метода make_equal
является создание подстрок одинаковой длины, что означает, что ваши входные строки необходимо изменить, чтобы они имели одинаковую длину (например, num1 = 99, num2 = 1234
). Метод добавит заполненные начальные нули на основе максимальной длины двух входных целых чисел и вернет два подцелых числа на основе определенной точки разделения mid
. Для целей задания, в котором нам давали два 64-значных целых числа, это не было проблемой, поскольку оба целых числа были одинаковой длины.
В процессе я узнал новый классный трюк с Ruby:
str.rjust(*args)
(например, str.rjust(n, '0')
, где n = integer
)
Этот метод Ruby String позволяет вам сравнить вашу строку с желаемой длиной строки. Если ваша строка короче, чем integer, метод вернет новую строку длины integer со строкой, выровненной по правому краю и дополненной padstr , который может быть любым. В моем случае я использовал это для дополнения моего более короткого целого числа num1
string ведущими нулями, чтобы сделать его равной длины с более длинной целочисленной строкой num2
.