Какой подход лучше умножить на два байта, используя только сдвиг битов и сложение?
Начальный вопрос:
Группа из нас (студенты, изучающие электронику, Великобритания) недавно в свое время взялись за программирование микроконтроллера PIC16F84A. Возникла необходимость в умножении двух 8-битных чисел без известных мин / макс для каждого. Одноклассник представил следующую идею.
multiply_numbers:
; Takes numbers in Num1 and Num2, and returns product in OutH:OutL
clrf OutH ; clear all non-input variables
clrf OutL
mult_loop
bcf STATUS,c ; clear carry bit
movfw Num2
addwf OutL ; add Num2 to OutL
btfsc STATUS,c ; check carry bit
incf OutH ; if set, increment OutH
decfsz Num1 ; decrement Num1
goto mult_loop ; if Num1 is not zero, repeat loop
return ; else return
Я чувствовал, что это, хотя и довольно короткое с точки зрения строк кода, может занять относительно длительное время для выполнения больших чисел. Я немного подумал и начал двигаться по пути смещения одного числа вправо, другого влево, и добавления числа со сдвигом влево определенное количество раз по пути к выходу, чтобы получить окончательный ответ. Я не совсем сделал это правильно, но потом наткнулся на этот вопрос на SO, который дал мне идею выразить одно из входных чисел как:
N = a_0 + a_1 * 2 + a_2 * 2 ^ 2 + a_3 * 2 ^ 3 +... + a_7 * 2 ^ 7
С этой отправной точки я придумал этот метод для умножения двух 8-битных чисел, чтобы получить 16-битный вывод (сохраненный в двух 8-битных регистрах).
multiply_numbers:
; Takes numbers in Num1 and Num2L, and returns product in OutH:OutL
clrf Num2H ; clear all non-input variables
clrf OutL
clrf OutH
mult_loop
btfsc Num1,0 ; test LSB of Num1
call add_num16 ; if set, add Num2H:Num2L to OutH:OutL
call shift_left ; shift Num2H:Num2L left (multiply by 2)
rrf Num1,f ; shift Num1 right
clrw ; clear working register (0x00)
bcf STATUS,z ; clear zero bit (3) of the STATUS register
addwf Num1,w ; add 0x00 to Num1
btfss STATUS,z ; if Num1 is zero, then exit loop
goto mult_loop ; else, continue with another iteration
return
add_num16
movfw Num2H
addwf OutH,f ; add Num2H to OutH
bcf STATUS,c ; clear carry bit (0) of the STATUS register
movfw Num2L
addwf OutL,f ; add Num2L to OutL
btfsc STATUS,c ; check carry bit
incf OutH,f ; increment OutH if set (OutL overflowed)
return
shift_left
bcf STATUS,c ; clear carry bit
rlf Num2L,f ; rotate Num2L left (carry -> LSB, MSB -> carry)
rlf Num2H,f ; rotate Num2H left, using carry bit from Num2L
return
Я думаю, что этот второй пример в большинстве случаев быстрее, просто потому, что цикл будет повторяться только до 8 раз, а не до 256 раз.
Я прав в своем предположении об их относительной скорости / эффективности? И действительно ли второй блок кода функционирует так, как я намереваюсь (есть ли потенциальные проблемы с ним, которые я пропустил)? Наконец, можно ли еще больше оптимизировать это умножение, используя методы, которые еще не используются?
Заранее спасибо.
PS Все переменные / регистры были правильно определены с их собственным адресом. Обширные комментарии к коду объясняются тем, что мы пытаемся скомпилировать набор подпрограмм, к которым мы можем вернуться в будущем, и все еще с одного взгляда узнаем, что происходит и почему.
PPS Этот вопрос связан с личным / хобби интересом к программированию этой фотографии и не имеет никакого отношения к какой-либо текущей курсовой работе и т. Д. Просто чтобы развеять любые ваши подозрения, которые у вас могли быть!
Микроконтроллер: PIC16F84A
Среда разработки: MPLABX IDE v1.10
Компилятор: mpasm (v5.43)
Редактировать № 1:
- Вместо тестирования младшего бита Num1 и добавления сдвинутого влево Num2H:Num2L к OutH:OutL, протестируйте MSB Num1 и добавьте Num2 к сдвинутому влево OutH:OutL.
- Сделайте shift_left встроенным, а не вызываемой подфункцией.
- Разверните 'mult_loop', чтобы оптимизировать восьмую итерацию.
Способ 2 улучшен:
multiply_numbers:
; Takes numbers in Num1 and Num2, and returns product in OutH:OutL
clrf OutL ; clear all non-input variables
clrf OutH
; 1st iteration
btfsc Num1,7 ; test MSB of Num1
call add_num8 ; if set, add Num2 to OutH:OutL
bcf STATUS,c ; clear carry bit
rlf OutL,f ; rotate OutL left (carry -> LSB, MSB -> carry)
rlf OutH,f ; rotate OutH left, using carry bit from OutL
rlf Num1,f ; shift Num1 left
; 2nd iteration
btfsc Num1,7
call add_num8
bcf STATUS,c
rlf OutL,f
rlf OutH,f
rlf Num1,f
; 3rd iteration
btfsc Num1,7
call add_num8
bcf STATUS,c
rlf OutL,f
rlf OutH,f
rlf Num1,f
; 4th iteration
btfsc Num1,7
call add_num8
bcf STATUS,c
rlf OutL,f
rlf OutH,f
rlf Num1,f
; 5th iteration
btfsc Num1,7
call add_num8
bcf STATUS,c
rlf OutL,f
rlf OutH,f
rlf Num1,f
; 6th iteration
btfsc Num1,7
call add_num8
bcf STATUS,c
rlf OutL,f
rlf OutH,f
rlf Num1,f
; 7th iteration
btfsc Num1,7
call add_num8
bcf STATUS,c
rlf OutL,f
rlf OutH,f
rlf Num1,f
; 8th iteration
btfss Num1,7 ; test MSB of Num1
return ; if not set, then return. else...
add_num8
bcf STATUS,c ; clear carry bit (0) of the STATUS register
movfw Num2
addwf OutL,f ; add Num2L to OutL
btfsc STATUS,c ; check carry bit
incf OutH,f ; increment OutH if set (OutL overflowed)
return
2 ответа
Да, но вы, вероятно, можете сделать лучше. Есть куча классических "хитростей", чтобы сделать это.
Во-первых, зная, что множитель можно интерпретировать как сумму степеней двойки, вы умно просто добавляете множитель к множителю, когда бит умножения ненулевой.
Во-вторых, добавленная стоимость - это только размер мультипликатора. Хотя вам нужен 16 (частичный и) конечный продукт, вам не нужно делать 16-битные добавления; Вы можете делать 8-битные добавления и распространять любой перенос. Обычно это легко сделать на ассемблере.
Чтобы сократить время, вы не хотите звонить и добавлять подпрограмму в середине цикла. Введите код, чтобы сэкономить время, затрачиваемое на вызов, возврат и оптимизировать любое перетасовывание регистров. Наконец, вы делаете цикл только ровно 8 раз; Стоит развернуть такой цикл 8 раз, чтобы избежать перегрузки счетчика и снизить "давление регистра", вызванное переключением со счетчиком, что дает вам больше свободы для оптимизации.
Обратите внимание, что я ничего не сказал о контроллере PIC, и на самом деле я не знаю его инструкций. Но то, что я сказал, относится ко всем, кто реализует 8-битное умножение. (Есть эквивалентные трюки для 16, 32 и 64-битных умножений). Таким образом, можно абстрактно написать следующий код:
mul16: // computes M1 * M2 --> P where M1 and M2 are 8 bit values, P is 16 bits
// P is represent by Plow and Phigh 8 bit values.
// reset the (partial) product
Plow=0; Phigh=0; // all 16 bits
// First iteration:
if msb(M1)==1 then { Plow+=M2; if carry then Phigh++; /* propagate carry */ }
shift M1 left bit;
shift (Phigh,Plow) left one bit
// Second iteration
<same as first>
<3rd ..7th iteration, same as first>
// 8th iteration
if msb(M1)==1 then { Plow+=M2; if carry then Phigh++ }
// dont bother: shift M1 left bit;
// dont bother: shift (Phigh,Plow) left one bit
<done>
Вы можете ловко заметить, что то, что написано как "если msb(M1)..." и "сдвиг M1 влево на один бит", часто легко реализуется с помощью команд ассемблера "сдвиг влево" или в отчаянии, добавляя значение к себе:-} Точно так же, "если нести... добавить один" часто реализуется с помощью инструкции "добавить перенос".
Я оставляю это вам, чтобы перекодировать это для ПИК.
Боже мой Я не писал код умножения на ассемблере около 30 лет. Это восходит ко временам написания кода для Apple II на 6502 ассемблере.
Вы абсолютно правы, что второй подход гораздо быстрее. 8 добавлений и 8 смен намного, намного быстрее, чем до 256 добавлений.
Тем не менее, я думаю, что у вас есть это задом наперед.
Вы хотите начать с MSB num1, и если этот бит равен 1, добавьте num2 к вашему результату. После каждого бита, кроме младшего разряда num1, сдвиньте результат влево на 1.