Умножение 5-значных чисел в уме считается либо невозможным, либо ограниченным областью знаний. Сегодня вы научитесь достигать невозможного самостоятельно, увидев некоторые методы решения проблем и шаги, которые я предпринял для разработки этого алгоритма. В конце я также включу код, реализующий этот новый подход, если вам интересно.
Более продвинутые методы, такие как алгоритм Карацубы, имеют дополнительные накладные расходы, поэтому они превосходят традиционные методы только при превышении нескольких сотен цифр. Из-за этого такие библиотеки, как Java BigInteger, используют традиционный подход до достижения этого предела.
Этот подход требует значительно меньше памяти, что значительно упрощает ментальную арифметику, а также уменьшает количество шагов суммирования. Это также отличный кандидат для устройств с ограниченными ресурсами.
Сравнение с другими алгоритмами умножения двух N-значных чисел:
- Метод начальной школы: 2N² + 2N сложения с использованием умного подхода, который позволяет избежать добавления нулей. При выполнении в уме вам также необходимо запомнить промежуточные значения, которые необходимо суммировать, тогда как реализация кода может повторно использовать пространство результатов.
- Умножение решетки: N² + 2N сложений плюс дополнительная память для всех переносов в верхних треугольниках каждой ячейки. Это требует на N² меньше сложений, чем метод начальной школы, если суммировать по диагоналям, а не добавлять большие значения со многими нулями, которые они представляют.
- Этот алгоритм: Только N² добавлений и очень эффективно использует память, отслеживая только один перенос.
Все 3 алгоритма выполняют одинаковое количество умножений с разницей в количестве сложений и эффективности использования памяти.
Путь к открытию
Подход, которому учат в школе, требует вычисления множества больших промежуточных значений, из-за чего вычисления в уме быстро разваливаются:
Чтобы найти более эффективный подход, мы применим метод начальной школы, но будем использовать переменные вместо цифр и проанализируем, как они влияют на ответ.
Мы начнем с умножения однозначных чисел и постепенно будем увеличивать количество цифр, ища закономерности. Мы выберем одни и те же наименее значимые переменные при работе с меньшим количеством цифр, чтобы переменные были одинаковыми на всех итерациях:
Этот метод имеет решающее значение для того, чтобы увидеть закономерности с меньшими усилиями.
Однозначные числа:
Никаких новых идей не появляется после умножения однозначных цифр, потому что мы пока ничего не говорим.
Квадратные скобки обозначают цифру в результате без переноса. Мой подход заключается в том, чтобы решить более простую версию задачи с крошечными цифрами, где перенос не требуется, а затем в конце развить решение для обработки переноса.
двухзначные числа:
Мы видим, что последняя цифра, [H*D], одинакова для обеих итераций, но мы не можем сделать вывод, поскольку у нас есть только 2 выборки.
3-значные числа:
О, это выглядит интересно, так как 2-я последняя цифра, [H*C + G*D], теперь тоже совпадает! Давайте посмотрим на еще одну итерацию, чтобы получить более сильный сигнал.
4-значные числа:
Шаблон расширяется здесь, поэтому мы видим, что:
- Последняя цифра всегда [H*D]
- 2-я последняя цифра всегда [H*C + G*D] при умножении чисел, которые имеют по крайней мере 2 цифры
- 3-я последняя цифра всегда [H*B + G*C + F*D] при умножении чисел, состоящих как минимум из 3 цифр.
Инсайты
- k-я последняя цифра всегда имеет одинаковую структуру при умножении любых чисел, содержащих не менее k цифр.
- k-я последняя цифра результата состоит только из последних k цифр каждого из входных данных.
Первый пункт многообещающий, так как он предполагает, что мы могли бы вычислить каждую цифру, если бы обнаружили закономерность для kпоследней цифры. Однако умножение двух k-значных чисел дает результат с 2*k цифрами, поэтому мы на полпути. Мой план состоит в том, чтобы найти шаблон для последних k цифр и адаптировать его ко всему результату, поскольку я ожидаю, что согласованный шаблон будет применяться ко всем цифрам.
Второй пункт еще более многообещающий, поскольку он предполагает, что мы должны иметь возможность постепенно генерировать результат в обратном порядке, начиная с наименее значащей цифры, вместо того, чтобы вычислять весь результат одним гигантским усилием. Это должно помочь снизить умственную нагрузку.
Разблокировка шаблона k-й последней цифры
Я большой сторонник визуального рисования проблемы, когда это возможно, поскольку наша зрительная кора намного лучше выявляет закономерности по сравнению с аналитическими подходами. Используя 4-значную итерацию, давайте нарисуем линию между всеми цифрами, которые нужно умножить для каждой цифры в результате.
Последняя цифра:[H*D]
2-я последняя цифра:[H*C + G*D]
3-я и последняя цифра:[H*B + G*C + F*D]
4-я и последняя цифра:[H*A + G*B + F*C + E*D]
5-я последняя цифра: [G*A + F*B + E*C]
6-последняя цифра: [F*A + E*B]
Седьмая-последняя цифра: [E*A]
Эврика!
Рисунок цифр на удивление легко визуализировать!
- Создайте скользящее окно, достаточно широкое, чтобы вместить все цифры. Начните с окна справа, содержащего последнюю цифру каждого входа.
- Перекрестите каждую цифру в окне с противоположной диагональю. Умножьте все цифры, которые пересекаются, и сложите произведения вместе, чтобы получить текущую цифру в результате.
- Сдвиньте окно влево на 1 позицию и повторяйте предыдущий шаг, чтобы сгенерировать следующую цифру, пока в окне больше не будет цифр.
Скользящее окно легко визуализировать с помощью большого и указательного искателя.
Преимущество шага 2 заключается в том, что он невероятно эффективно использует память, поскольку вам нужно только отслеживать текущий счет и добавлять к счету по одной паре пересекающихся цифр за раз. Это позволяет легко выполнять мысленно с несколькими пробными прогонами.
Переноситься
Применение описанного выше подхода терпит неудачу, поскольку некоторые из вычисляемых цифр в конечном итоге занимают более 1 цифры после добавления пересекающихся пар. Так как это не может быть правильным, давайте сохраним только последнюю цифру вычисления и перенесем остальные, чтобы посмотреть, что произойдет.
Давайте умножим 87 X 96 = 8352 с новым подходом:
tally = 6 * 7 = 42
Отсечь последнюю цифру подсчета результата и перенести остальные:
result = _ _ _ 2 (2 from 42) carry-over = 4 (after chopping off the last digit from 42)
Сдвиньте окно влево, чтобы сгенерировать следующую цифру:
tally = 4 + 6*8 (carry-over + first criss-cross)
= 4 + 48
= 52
tally = 52 + 9*7 (tally + remaining criss-cross)
= 52 + 63
= 115
отрезать последнюю цифру от подсчета как следующую цифру в результате:
result = _ _ 52 (5 from 115 in front of previous result of _ _ _ 2) carry-over = 11 (after chopping off the last digit from 115)
Сдвиньте окно влево в последний раз:
tally = 11 + 9*8 (carry-over + criss-cross)
= 11 + 72
= 83
Поскольку мы не можем сдвинуть окно дальше влево, число 83 становится оставшимися цифрами результата:
result = 8352 (tally 83 in front of the previous result of _ _ 52)
Успехов, результат соответствует нашим ожиданиям!
Подход работает таким же образом при работе с другим количеством цифр, поскольку вам просто нужно выровнять оба числа по правому краю и прекратить перекрестное пересечение, когда цифры заканчиваются, поскольку отсутствующие цифры являются нулями.
Прежде чем продемонстрировать свои новые навыки, я рекомендую выполнить несколько пробных прогонов с двузначными числами, постепенно добавляя по одной цифре за раз, поскольку для адаптации к такому образу мышления требуется немного практики. Я рекомендую записывать цифры результата, когда вы вычисляете их справа налево, так как в конечном итоге вам все равно нужно будет представить ответ, так что запоминать на одну вещь меньше.
Вот реализация Kotlin, которая работает с базой 10 цифр:
/**
* Multiplies [value1] times [value2] where these are arrays
* with 1 digit per element.
*/
fun multiply(value1: IntArray, value2: IntArray): IntArray {
val smaller: IntArray
val larger: IntArray
if (value1.size < value2.size) {
smaller = value1
larger = value2
} else {
smaller = value2
larger = value1
}
val result = IntArray(smaller.size + larger.size) { 0 }
var resultIndex = result.lastIndex
var carry = 0
// Handle the first phase until the window no longer hangs off
// the right side
for (windowStart in larger.lastIndex downTo 1) {
var tally = carry
// criss-cross the right side of the smaller value with left side
// of the larger value
var smallerIndex = smaller.lastIndex
// Stop when no digits are left in the smaller value
// as those will all be zeros
val numStepsInCurrentWindow = min(smaller.size, larger.size - windowStart)
for (largerIndex in windowStart until windowStart + numStepsInCurrentWindow) {
tally += smaller[smallerIndex] * larger[largerIndex]
smallerIndex--
}
val (nextDigit, updatedCarry) = getNextDigitAndCarry(tally)
carry = updatedCarry
result[resultIndex] = nextDigit
resultIndex--
}
// Handle the second phase where the window slides off the left side
// until no digits are left in the smaller value
for (windowEnd in smaller.lastIndex downTo 0) {
var tally = carry
var smallerIndex = windowEnd
for (largerIndex in 0..windowEnd) {
tally += smaller[smallerIndex] * larger[largerIndex]
smallerIndex--
}
val (nextDigit, updatedCarry) = getNextDigitAndCarry(tally)
carry = updatedCarry
result[resultIndex] = nextDigit
resultIndex--
}
// handle the remaining carry. An efficient implementation
// in a binary base would use a bit shift without looping here
while (carry > 0) {
val (nextDigit, updatedCarry) = getNextDigitAndCarry(carry)
result[resultIndex] = nextDigit
carry = updatedCarry
resultIndex--
}
return result
}
/**
* Computes the next digit in the result along with the carry-over.
*
* An efficient implementation would remove this function as it
* creates an object in the tight inner loops.
*/
fun getNextDigitAndCarry(tally: Int): Pair<Int, Int> {
// Bit shifts would be more efficient here when dealing with a binary base
val carry = tally / 10
return Pair(tally - 10 * carry, carry)
}
Если вам это интересно, вы можете получить полный доступ к тысячам других подобных авторов, присоединившись к Medium.
