Стремясь заполнить пробелы в моих знаниях об алгоритмах и структурах данных, я недавно начал курс 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.