Комментарии 7
Это алгоритм умножения на арифмометре "Феликс".
Процессоры без инструкций умножения появились раньше тех, что с умножением. Например, это i8080, 6502, Z80 и прочие 8-битки, на основе которых делались домашние и школьные компьютеры 80х гг.
А потом появились микроконтроллеры. Большинство 8-битных МК не имело инструкций умножения.
Поэтому вашим изобретением люди пользовались с незапамятных времён вплоть до середены-конца 2000х, когда массовые микроконтроллеры обзавелись аппаратными умножителями.
Помимо отсутствия инструкции умножения, отсутствовал также сдвиг на произвольное количество бит за один машинный цикл. Аппаратно такой сдвиг реализовать почти так же сложно, как и умножитель. Сдвигать можно было только на один бит. Можно было сдвигать несколько раз на один бит, но за каждый сдвиг надо было тратить машинный цикл.
Ещё отсутствовала команда поиска первого установленного бита.
С использованием только команд сдвига на один разряд и команд проверки одного бита алгоритмы умножения программировались немного по-другому, хотя суть была такой же — умножение в столбик.
А ещё были хитрые трюки для ускорения умножения. Например, используя тождество (a+b)^2=a^2+2*a*b+b^2, можно было, имея способ быстрого возведения в квадрат (обычно с помощью таблицы квадратов) реализовать умножение.
А потом появились микроконтроллеры. Большинство 8-битных МК не имело инструкций умножения.
Поэтому вашим изобретением люди пользовались с незапамятных времён вплоть до середены-конца 2000х, когда массовые микроконтроллеры обзавелись аппаратными умножителями.
Помимо отсутствия инструкции умножения, отсутствовал также сдвиг на произвольное количество бит за один машинный цикл. Аппаратно такой сдвиг реализовать почти так же сложно, как и умножитель. Сдвигать можно было только на один бит. Можно было сдвигать несколько раз на один бит, но за каждый сдвиг надо было тратить машинный цикл.
Ещё отсутствовала команда поиска первого установленного бита.
С использованием только команд сдвига на один разряд и команд проверки одного бита алгоритмы умножения программировались немного по-другому, хотя суть была такой же — умножение в столбик.
А ещё были хитрые трюки для ускорения умножения. Например, используя тождество (a+b)^2=a^2+2*a*b+b^2, можно было, имея способ быстрого возведения в квадрат (обычно с помощью таблицы квадратов) реализовать умножение.
метод умножения «в столбик» известен не менее четырёх тысячелетий
©wiki
©wiki
Ой, а когда мне было лет 13, я на ассемблере треугольники текстурированные рисовал, возможно, изобрел пару давно известных алгоритмов. Тоже на Хабр сразу писать?
Инструкции mul и даже imul появились в x86 раньше чем bsf и btc.
Другое дело если бы речь шла о мелкоконтроллере без аппаратного умножения…
Другое дело если бы речь шла о мелкоконтроллере без аппаратного умножения…
АСПушкин
«О, сколько нам открытий чудных
Готовят просвещенья дух,
И опыт, сын ошибок трудных,
И гений, парадоксов друг,
И случай, бог изобретатель.»
Готовят просвещенья дух,
И опыт, сын ошибок трудных,
И гений, парадоксов друг,
И случай, бог изобретатель.»
На самом деле все уже
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Перемножение чисел без умножения