Эффективное умножение переменной длины # [Концептуальная]

Question

EDIT

Так что, похоже, я "недооценил", что означают числа различной длины. Я даже не думал о ситуациях, когда операнды имеют длину 100 цифр. В этом случае мой предложенный алгоритм определенно не эффективен. Возможно, мне понадобится реализация, сложность которой зависит от количества цифр в каждом операнде, а не от его числового значения, верно?

Как предложено ниже, я рассмотрю алгоритм Карацубы ...

---

Напишите псевдокод алгоритма, который принимает два числа произвольной длины (представленных в виде строк) и вычисляет произведение этих чисел. Используйте эффективную процедуру для умножения большого числа произвольной длины. Проанализируйте эффективность вашего алгоритма.

Я решил выбрать (полу) легкий выход и использовать русский крестьянский алгоритм. Это работает так:

a * b = a/2 * 2b if a is even 
a * b = (a-1)/2 * 2b + a if a is odd

Мой псевдокод:

rpa(x, y){
    if x is 1
        return y
    if x is even
        return rpa(x/2, 2y)
    if x is odd
        return rpa((x-1)/2, 2y) + y
}

У меня есть 3 вопроса:

1. Эффективно ли это для чисел произвольной длины? Я реализовал это в C и попробовал числа различной длины. Время выполнения во всех случаях было почти мгновенным, поэтому трудно сказать эмпирически ...
2. Могу ли я применить теорему магистра, чтобы понять сложность ...?
   • a = # подзадач в рекурсии = 1 (макс. 1 рекурсивный вызов во всех состояниях)
   • n / b = размер каждой подзадачи = n / 1 -> b = 1 (проблема не меняет размер ...?)
   • f (n ^ d) = работа, выполненная вне рекурсивных вызовов = 1 -> d = 0 (сложение, когда a нечетно)
   • a = 1, b ^ d = 1, a = b ^ d -> сложность в n ^ d * log (n) = log (n)
   • это логично, поскольку мы вдвое уменьшаем проблему на каждом шаге, верно?
3. Что мог бы иметь в виду мой профессор, предоставляя числа произвольной длины "в виде строк". Зачем это делать?

Большое спасибо заранее

Answer 1

Что мог бы иметь в виду мой профессор, предоставляя числа произвольной длины "в виде строк". Зачем это делать?

Это фактически меняет все в проблеме (и делает ваш алгоритм неверным). Это означает, что 1234 предоставляется как 1,2,3,4, и вы не можете работать напрямую с целым числом. Вам необходимо проанализировать ваш алгоритм с точки зрения #additions, #multiplications, #divisions. Вы должны ожидать, что деление будет немного дороже, чем умножение, а умножение будет намного дороже, чем сложение. Так что хороший алгоритм старается уменьшить количество делений и умножений.

Проверьте алгоритм Карацубы , (ps не копируйте его, это не то, что хочет ваш учитель) - один из самых быстрых для этой спецификации.

Answer 2

Добавить 3): Родные целые числа ограничены тем, как большие (или маленькие) числа они могут представлять (например, 32- или 64-разрядные целые числа).Чтобы представлять числа произвольной длины, вы можете выбрать строки, потому что тогда вы не ограничены этим.Проблема, конечно, в том, что ваши арифметические единицы на самом деле не созданы для добавления строк; -)