Умножение Карацубы или самые красивые алгоритмы в мире :)

Спросили тут недавно: а какой самый красивый алгоритм я знаю?

Если не размышлять слишком долго над понятием красоты в программировании, навскидку приходят в голову примерно следующие решения:

• Ханойская башня,
• Quicksort,
• динамическое программирование,
• умножение Карацубы,
• CORDIC...
• а также почти любой код, который был написан до Вас в качестве решения Вашей задачи :)

Ну, а чтобы заметка не была "пустой", вот правильное по виду рекурсивное умножение Карацубы на Javascript, скорее, демка, чем действительно быстродействующее (можно выполнить как код HTML):

<div id="karatsubaResult"></div>
<script type="text/javascript">
function karatsubaMultiplication (x, y) {
 if (x < 10 || y < 10) return x*y;
 let n = Math.min (('' + x).length, ('' + y).length);
 let pow10HalfN = Math.pow (10,     parseInt(n / 2));
 let pow10N     = Math.pow (10, 2 * parseInt(n / 2));
 let a = parseInt (x / pow10HalfN);
 let b = x % pow10HalfN;
 let c = parseInt (y / pow10HalfN);
 let d = y % pow10HalfN;
 return pow10N * karatsubaMultiplication(a, c) + 
   pow10HalfN * (karatsubaMultiplication(a, d) + karatsubaMultiplication(b, c)) + 
   karatsubaMultiplication(b, d);
}

document.getElementById('karatsubaResult').innerHTML = ''+karatsubaMultiplication(12345,6789);
</script>

19.06.2018, 23:01 [2513 просмотров]