В дополнение к вышестоящим объяснениям добавлю: мне сначала было легче разобраться с быстрым умножением матриц (умножение Штрассена,
https://ru.wikipedia.org/wiki/Алгоритм_Штрассена). Это один из самых наглядных (в математическом смысле) быстрых алгоритмов типа "разделяй и властвуй". Для меня проще думать в терминах матриц, нежели составных частей чисел.
