Как реализовать умножение Карацубы с помощью битовых манипуляций - PullRequest
Новая
       29

Как реализовать умножение Карацубы с помощью битовых манипуляций

0 голосов
/ 04 ноября 2018

Я использую умножение Карацубы в Scala (мой выбор) для онлайн-курса. Учитывая, что алгоритм предназначен для умножения больших чисел, я выбрал тип BigInt, который поддерживается Java BigInteger . Я хотел бы эффективно реализовать алгоритм, который с использованием арифметики с основанием 10 скопирован ниже из Википедии: 

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 = floor(m/2)
  /* split the digit sequences in 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 ^ (m2 * 2)) + ((z1 - z2 - z0) * 10 ^ m2) + z0

Учитывая, что BigInteger внутренне представляется как int[], если я могу вычислить m2 в терминах int[], я могу использовать сдвиг битов, чтобы извлечь нижнюю и верхнюю половину числа. Точно так же последний шаг также может быть достигнут с помощью сдвига битов.

Однако это легче сказать, чем сделать, так как я не могу обернуться вокруг логики. Например, если максимальное число 999, двоичное представление - 1111100111, нижняя половина - 99 = 1100011, верхняя половина - 9 = 1001. Как мне получить вышеуказанный сплит?

Примечание: Существует существующий вопрос , который показывает, как реализовать арифметику на BigInteger, но не сдвиг битов. Следовательно, мой вопрос не является дубликатом.

1 Ответ

0 голосов
/ 05 ноября 2018

Чтобы иметь возможность использовать сдвиг битов для разделения и рекомбинации, основание должно быть степенью двойки. Использование двух, как в связанном ответе, вероятно, разумно Тогда «длина» входов может быть найдена непосредственно с помощью bitLength, и разделение может быть реализовано как: 

// x = a + 2^N b
BigInteger b = x.shiftRight(N);
BigInteger a = x.subtract(b.shiftLeft(N));

Где N - это размер, который a будет иметь в битах.

Учитывая, что BigInteger реализован с 32-битными конечностями, имеет смысл использовать 2³² в качестве основы, гарантируя, что большие сдвиги включают только перемещение целых чисел, а не более медленный путь кода, где BigInteger смещено на значение от 1 до 31. Это можно сделать, округлив N до кратного 32.

Конкретная константа в этой строке, 

if (N <= 2000) return x.multiply(y);                // optimize this parameter

Вероятно, не следует слишком доверять, учитывая этот комментарий. Для производительности должно быть ограничено некоторые , в противном случае рекурсивное разбиение идет слишком глубоко. Например, когда размер чисел равен 32 или меньше, явно лучше просто умножить, но, вероятно, хорошее отсечение намного выше. В этом источнике самого BigInteger обрезание выражается через количество конечностей вместо битов и устанавливается равным 80 (так 2560 бит) - у него также есть другой порог, выше которого он переключается 3-х кратное умножение Toom-Cook вместо умножения Карацубы.

...