Итак, в данной статье мы рассмотрим метод решения целочисленного умножения, предложенного Анатолием Карацубой в 1960г.
Пусть у нас будет два числа x и y. При этом y = 1234, а x = 5678.
Для начала обозначим первую и вторую половины числа x как a и b, чтобы рассматривать их отдельно. Таким образом a = 56, b = 78. Таким же образом поступим с числом y, обозначив образованное из него c и d. Получим c = 12, d = 34.
Вот теперь выполним последовательность операций предложенных Карацубой.
Шаг 1.
- Вычислить произведение a*c = 56*12 = 672
Шаг 2.
- Вычислить b*d = 78*34 = 2652
Шаг 3.
- Вычислить (a +b)*(c + d) = 134*46 = 6164
Шаг 4.
- Вычесть результаты первых двух шагов из результата третьего шага:
6164 - 672 - 2652 = 2840
Наконец, мы суммируем результаты шагов 1,2 и 4, но только после добавления четырех конечных нулей к ответу на шаге 1 и двух конечных нулей к ответу в шаге 4.
Шаг 5.
672*10^4 + 2840*10^2 + 2652 = 6 720 000 + 284 000 + 2652 = 7 066 652
Этот алгоритм показывает принципиальное отличие от того, с которым вы познакомились в школе, когда при целочисленном умножении "считали в столбик". Этот пример дает понимание того, что сфера алгоритмизации разнообразна.
Понравилась статья? Подпишись!
Для хорошего разработчика алгоритмов, пожалуй, самый важный принцип состоит в том, чтобы отказаться от соглашательства.