На самом деле, длина 4 это плохо. Надо квадратичный алгоритм включать, когда длина около 100, или в крайнем случае 50. Точного значения не знаю, т.к. не пишу этот алгоритм.

Отдельный вопрос что показанный топикстартером код работает только после того как вернуть тудя явно позабытый normalize и только для чисел одинаковой длины.

Теперь по поводу высказываний предыдущих ораторов, по поводу алгоритма вообще и по поводу задачи вообще. Просто я недавно в очередной раз думал над тем, стОит ли включать алгоритм Карацубы в свой курс лекций, и поменял своё мнение с "да" на "вряд ли".

Алгоритм Карацубы действительно не очень "мощный". Умножение через быстрое преобразование Фурье (оно же Fast Fourier Transform) действительно заметно быстрее -- O(n log n) против O(n^1.585) у Карацубы. Более того -- код реализации БПФ (FFT) не сильно длиннее кода алгоритма Карацубы.

Основная проблема с БПФ -- надо понять и запомнить довольно много весьма нетривиальных преобразований высшей математики. И, честно говоря, я не напишу БПФ в условиях тура (без справочников), хотя при чтении объяснений БПФ каждый шаг вроде бы понятен.
 
Менять BASE на 10^9, IMHO, _НЕ_ стОит. Алгоритм Карацубы либо множит (A1+A2)*(B1+B2) как n/2-значные числа (игнорируя тот факт, что сумма двух n/2-значных чисел вполне может быть не n/2-значной а очень даже (n/2+1)-значной), либо усложняется за счёт того, что размеры подзадач могут быть разными (или n/2-значными или (n/2+1)-значными). Причём, при подсчёте произведения сумм произведений сумм <повторить "произведений сумм" ещё log(n)-2 раз>, всё это очень даже накапливается. Так что уже при BASE=1000 наверняка будут переполнения 32-битного инта.

Альтернатива "не допускать возрастания значений цифр, вовремя делая переносы" также имеет свои недостатки -- разбиение на подзадачи красиво, когда количество цифр является степенью двойки, и неприятно, когда оное количество нечётно. Особенно если пользоваться приёмом из следующего абзаца.

Наконец, один из главных тормозов многих реализаций Карацубы -- выделение/освобождение памяти в каждом рекурсивном вызове. Вместо этого можно один раз выделить о-о-очень длинный массив (вроде бы, должно хватать 12-кратного размера входных данных, но насчёт конкретного числа 12 я не уверен). После этого рекурсивным вызовам говорить "считайте произведение числа в ячейках с индексами с такого-то по такой-то на число в ячейках с индексами с такого-то по такой-то, формируя полученное произведение в ячейках с индексами с такого-то по такой-то, и имея полное право использовать для вспомогательных целей все ячейки от индекса такого-то и до конца". От этого скорость увеличивается в десятки раз, да и MIN_LENGTH_FOR_KARATSUBA очень даже можно ставить вовсе не 100 и не 50, а где-то 16 или 20 (в смысле с 16 или 20 работает быстрее, чем с 50 или 100).

Но реализация описанного в предыдущем абзаце требует настолько большой аккуратности, что, возможно, проще научиться писать БПФ.

Кстати, интересует, как насчёт выхода за пределы типа в БПФ -- там ведь, насколько я понимаю, зависимость от плавающей точки, и когда-то наступает момент, что точности 80-битного лонг дабла не хватает... для каких размеров начинает не хватать лонг дабла? для каких дабла? какие значения цифр умножаемых чисел являются "плохими" в этом смысле?