Алгоритм быстрого умножения в сборке

Question

мое назначение - написать компилятор, который скомпилирует небольшой язык программирования на поддельный язык ассемблера (ячейки регистров и ячеек имеют неопределенную длину).

Что я должен сделать, это преобразование такой инструкции:

a = b * c 

к набору INC, З, ADD Инструкции (где я это указатель на память, есть только один регистр доступен), который будет выполнить умножение. Проблема заключается в том, что алгоритм должен выполнять свою работу в O (log n) времени.

Может кто-нибудь объяснить шаг за шагом алгоритм решения этой проблемы? Мой друг упомянул алгоритм Бута-Максорли, но я его почти не понимаю.

РЕДАКТИРОВАТЬ: Поддельные инструкции по сборке включают в себя: чтение, запись, НАГРУЗКА я, МАГАЗИНА я, ADD I, SUB я, ШР я, СХЛ я, INC, СБРОС, ПРЫГНУТЬ к, JZERO к, Джодд к (перехода к к если регистр нечетный)

Answer 1

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

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

Этот вопрос: How can I multiply and divide using only bit shifting and adding? может поэтому иметь отношение к делу. Реализация shift + add, которая является O (log2 n) в C, представлена ​​в качестве ответа на What is the time complexity of this multiplication algorithm?, но может быть адаптирована к вашему набору инструкций.