Умножение и возведение в квадрат без аппаратной поддержки

[Starichok51]

B@R5uk, по приведенной тобой картинке видно, что внутри МК в одном цикле "спрятано" 3 такта.
но как я выше сказал, снаружи мы эти такты видеть не можем. именно поэтому я и сказал, что называть цикл тактом - не правильно.

[B@R5uk]

Размышлял я тут над тем, как бы всё-таки с помощью таблицы квадратов перемножить две четырёхбайтные величины. Ведь таблица в памяти уже есть, хотелось бы использовать ресурс по-полной. Даже составил шпаргалку:



Смотрю я на неё и думаю: многовато сложений и вычитаний, да ещё на каждое сложение надо извлечение из ПЗУ сделать, да на каждую разность модуль разности посчитать. Очень уж большое количество инструкций потребуется, а у меня ПЗУ 36% на всё про всё осталось. Умножение со сдвигами в цикле куда компактнее, хоть и медленнее.

И тут меня осенило: а почему бы не организовать и здесь цикл??!! Вон, даже однотипные повторяющиеся (со сдвигом) блоки есть. Если ещё подключить ОЗУ со скользящим указателем, реально даже сделать процедуру, работающую с одним из сомножителей произвольной длины. А если пожертвовать производительностью и запилить два вложенных цикла, можно вообще перемножать оба сомножителя произвольной длины весьма компактным кодом. Такой простор для творчества!

[Gudd-Head]

И всё-таки, я не очень хорошо представляю себе практическую применимость перемножения целых чисел разрядностью более 16 бит.

[B@R5uk]

Gudd-Head, разве не бывает ситуаций, когда надо находить произведение 32-битных чисел? Да вон хоть арифметика с плавающей точкой подразумевает умножение чисел разрядностью выше 16 бит.

Спойлер

В моём случае, как я уже писал, мне надо навести статистику поступающих трёхбайтных величин. Статистика — это среднее и среднеквадратичное отклонение:

μ = 1/N * Σ x_i
σ^2 = 1/N * Σ (x_i - μ)^2

Применение формул в лоб подразумевает хранение в памяти всех получаемых мной величин, а так же работа с плавающей точкой на всех этапах вычислений. На моём МК это нереализуемо практически (памяти всего то 128 байт). Поэтому я использую модернизированную формулу для расчётов среднеквадратичного отклонения:

(N σ)^2 = N * Σ x_i^2 - (Σ x_i)^2

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

В итоге, я ищу сумму квадратов 3-байтных величин, получаю 7-байтную величину, умножаю её на 3-байтную (количество событий N), в силу ограничений на величины у меня получается 8-байтная величина, а не 10-байтная. Из неё я вычитаю квадрат 4-байтной величны. Дальше уже идёт арифметика с плавающей точкой.

Между тем, накатал набросок процедуры умножения 32-битной величины на 8N-битную (4 байта на N байт). Время работы: 113 * N + 50 циклов (502 цикла для N = 4). Шпаргалка к процедуре (для N = 4) двумя постами выше.

Спойлер

Код: Выделить всё

;==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==
;   Процедура умножает 4-байтную величину ABCD на N-байтную T...T
;   Исходные ресурсы:
;       -   r16 - r19   -   первый сомножитель (ABCD)
;       -   r20         -   количество N байт 2-го сомножителя
;       -   X:(X+N-1)   -   второй сомножитель (в ОЗУ)
;       -   X           -   указатель на второй сомножитель в ОЗУ и буфер результата
;   Возвращаемый результат:
;       -   r12 - r15   -   старшие 4 байта произведения
;       -   (X+N):(X+2N-1)
;                       -   младшие N байт произведения (в ОЗУ)
;   Используемые ресурсы:
;       -   zero        -   глобальный (для всей программы) регистр с нулевым значением
;       -   r4 - r11    -   квадраты байтов первого сомножителя
;       -   r21         -   очередной байт 2-го сомножителя
;       -   r22, r23    -   подгружаемые квадраты разностей и байтов 2-го сомножителя
;       -   r24         -   рабочий регистр
;       -   r25         -   счётчик итераций цикла
;       -   Z           -   указатель на таблицу квадратов в ПЗУ
;       -   STACK       -   1 байт стека
;   Размер процедуры 226 байт (113 инструкций)
;   Время выполнения 113 * N + 50 циклов (включая rcall и ret)
;--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
mul_32x8N:      ;   Подгрузка из ПЗУ квадратов байтов первого сомножителя
                ldi     ZH,     HIGH(2*SquareTable1)
                mov     ZL,     r16     ;   Байт D
                lpm     r5,     Z       ;   Старший байт D^2
                ldi     ZH,     HIGH(2*SquareTable0)
                lpm     r4,     Z       ;   Младший байт D^2
                mov     ZL,     r17     ;   Байт C
                lpm     r6,     Z       ;   Младший байт C^2
                ldi     ZH,     HIGH(2*SquareTable1)
                lpm     r7,     Z       ;   Старший байт C^2
                mov     ZL,     r18     ;   Байт B
                lpm     r9,     Z       ;   Старший байт B^2
                ldi     ZH,     HIGH(2*SquareTable0)
                lpm     r8,     Z       ;   Младший байт B^2
                mov     ZL,     r19     ;   Байт A
                lpm     r10,    Z       ;   Младший байт A^2
                ldi     ZH,     HIGH(2*SquareTable1)
                lpm     r11,    Z       ;   Старший байт A^2
                ;   Инициализация вспомогательных данных
                clr     r12             ;   Инициализация рабочих регистров
                clr     r13
                clr     r14
                clr     r15
                clr     r24
                mov     r25,    r20     ;   Счётчик итераций
mul_32x8N_1:    ;   Основной цикл процедуры
                ld      r21,    X       ;   Очередной байт T второго сомножителя
                ;   Расчёт модулей первых двух разностей
                mov     ZL,     r18     ;   Байт B
                sub     ZL,     r21     ;   Разность B - T
                brcc    mul_32x8N_2
                neg     ZL              ;   Модуль разности |B - T|
mul_32x8N_2:    push    ZL              ;   Сохранение |B - T| в стек
                mov     ZL,     r16     ;   Байт D
                sub     ZL,     r21     ;   Разность D - T
                brcc    mul_32x8N_3
                neg     ZL              ;   Модуль разности |D - T|
mul_32x8N_3:    ;   Прогрузка и вычитание из результата квадратов первых двух разностей
                lpm     r23,    Z       ;   Старший байт (D - T)^2
                ldi     ZH,     HIGH(2*SquareTable0)
                lpm     r22,    Z       ;   Младший байт (D - T)^2
                sub     r12,    r22
                sbc     r13,    r23
                pop     ZL              ;   Извлечение |B - T| из стека
                lpm     r22,    Z       ;   Младший байт (B - T)^2
                ldi     ZH,     HIGH(2*SquareTable1)
                lpm     r23,    Z       ;   Старший байт (B - T)^2
                sbc     r14,    r22
                sbc     r15,    r23
                sbc     r24,    zero    ;   Заём
                ;   Добавление квадратов байтов первого сомножителя
                add     r12,    r4      ;   Младший байт D^2
                adc     r13,    r5      ;   Старший байт D^2
                adc     r14,    r8      ;   Младший байт B^2
                adc     r15,    r9      ;   Старший байт B^2
                adc     r24,    zero    ;   Перенос
                ;   Подгрузка квадрата байта T второго сомножителя
                mov     ZL,     r21     ;   Байт T
                ldi     ZH,     HIGH(2*SquareTable0)
                lpm     r22,    Z       ;   Младший байт T^2
                ldi     ZH,     HIGH(2*SquareTable1)
                lpm     r23,    Z       ;   Старший байт T^2
                ;   Добавление квадрата байта T второго сомножителя
                add     r12,    r22     ;   Младший байт T^2
                adc     r13,    r23     ;   Старший байт T^2
                adc     r14,    r22     ;   Младший байт T^2
                adc     r15,    r23     ;   Старший байт T^2
                adc     r24,    zero    ;   Перенос
                ;   Сдвиг разрядов на один байт с сохранением одного байта произведения
                add     XL,     r20     ;   Сохранение в ОЗУ очередного байта
                st      X+,     r12     ;       произведения и перевод указателя
                sub     XL,     r20     ;       на следующий байт 2-го множителя
                mov     r12,    r13
                mov     r13,    r14
                mov     r14,    r15
                mov     r15,    r24
                clr     r24             ;   Инициализация старшего рабочего байта
                ;   Добавление квадрата байта T второго сомножителя
                add     r12,    r22
                adc     r13,    r23
                adc     r14,    r22
                adc     r15,    r23
                adc     r24,    zero    ;   Перенос
                ;   Добавление квадратов байтов первого сомножителя
                add     r12,    r6      ;   Младший байт C^2
                adc     r13,    r7      ;   Старший байт C^2
                adc     r14,    r10     ;   Младший байт A^2
                adc     r15,    r11     ;   Старший байт A^2
                adc     r24,    zero    ;   Перенос
                ;   Расчёт модулей вторых двух разностей
                sub     ZL,     r19     ;   Разность T - A
                brcc    mul_32x8N_4
                neg     ZL              ;   Модуль разности |A - T|
mul_32x8N_4:    push    ZL              ;   Сохранение |A - T| в стек
                mov     ZL,     r17     ;   Байт C
                sub     ZL,     r21     ;   Разность C - T
                brcc    mul_32x8N_5
                neg     ZL              ;   Модуль разности |C - T|
mul_32x8N_5:    ;   Прогрузка и вычитание из результата квадратов вторых двух разностей
                lpm     r23,    Z       ;   Старший байт (C - T)^2
                ldi     ZH,     HIGH(2*SquareTable0)
                lpm     r22,    Z       ;   Младший байт (C - T)^2
                sub     r12,    r22
                sbc     r13,    r23
                pop     ZL              ;   Извлечение |A - T| из стека
                lpm     r22,    Z       ;   Младший байт (A - T)^2
                ldi     ZH,     HIGH(2*SquareTable1)
                lpm     r23,    Z       ;   Старший байт (A - T)^2
                sbc     r14,    r22
                sbc     r15,    r23
                sbc     r24,    zero    ;   Заём
                ;   Декремент счётчика циклов и переход к следующей итерации
                dec     r25
                breq    mul_32x8N_6
                rjmp    mul_32x8N_1
mul_32x8N_6:    ;   Деление результата на 2 для формирования искомого произведения
                add     XL,     r20     ;   Указатель -- за N-й байт результата в ОЗУ
                lsr     r24             ;   Деление на 2 старших 4-х байт результата
                ror     r15
                ror     r14
                ror     r13
                ror     r12
mul_32x8N_7:    ;   Деление младших N байт в ОЗУ на 2
                ld      r24,    -X      ;   Сдвиг указателя и чтение очередного байта
                ror     r24             ;   Деление на 2
                st      X,      r24     ;   Сохранение байта на место
                dec     r20             ;   Декремент счётчика байтов
                brne    mul_32x8N_7
                ret
;==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==

Что-то мне не очень нравится размер (11% от всего объёма ПЗУ). Надо бы написать для сравнения процедуру умножения двух 32-битных величин сдвигами и сложениями в цикле.

[Карбофос]

[uquote="B@R5uk",url="/forum/viewtopic.php?p=4213451#p4213451"]μ = 1/N * Σ x_i
σ^2 = 1/N * Σ (x_i - μ)^2

я использую модернизированную формулу для расчётов среднеквадратичного отклонения:

(N σ)^2 = N * Σ x_i^2 - (Σ x_i)^2[/uquote]
Чё, нормально.
Если не важен результат, а важен сам путь.

bollinger bands

Ну, не несёт в себе СКО от начала времён никакого смысла.

Тож, похоже, пустой вариант.
Я тебе столько времени сэкономил.
Охххххх
Тебе никто ничего не должен.

[B@R5uk]

Сделал под копирку с 200-го дока процедуру перемножения 4-байтных величин:

Спойлер

Код: Выделить всё

;==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==
;   Процедура перемножает две 4-байтные величины
;   Исходные ресурсы:
;       -   r16 - r19   -   первый сомножитель (затирается в процессе работы)
;       -   r20 - r23   -   второй сомножитель
;   Возвращаемый результат:
;       -   r12 - r15   -   Старшие 4 байта произведения
;       -   r16 - r19   -   Младшие 4 байта произведения
;   Используемые ресурсы:
;       -   r24         -   счётчик итераций
;   Размер процедуры 50 байт (25 инструкций)
;   Время выполнения 431 + 3 * Sb циклов (максимум 527 циклов, включая rcall и ret),
;       где Sb -- число единичных бит первого сомножителя
;--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
mul_32x32:      clr     r12
                clr     r13
                clr     r14
                clr     r15
                ldi     r24,    0x20
                lsr     r19
                ror     r18
                ror     r17
                ror     r16
mul_32x32_1:    ;   Основной цикл процедуры
                brcc    mul_32x32_2
                add     r12,    r20
                adc     r13,    r21
                adc     r14,    r22
                adc     r15,    r23
mul_32x32_2:    ror     r15
                ror     r14
                ror     r13
                ror     r12
                ror     r19
                ror     r18
                ror     r17
                ror     r16
                dec     r24
                brne    mul_32x32_1
                ret
;==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==

Время выполнения 527 циклов максимум. Что-то у табличного подхода нет никакого выигрыша по сравнению с этой стандартной процедурой. Видать, надо всё таки формулу ab = ((a + b)^2 - (a - b)^2) / 4 использовать, а не формулу ab = (a^2 + b^2 - (a - b)^2) / 2. В полтора раза меньше сложений и операций чтения из ПЗУ.

Добавлено after 9 minutes 44 seconds:

[uquote="akl",url="/forum/viewtopic.php?p=4211767#p4211767"]Линейная программа суммы квадратов максимальных беззнаковых трехбайтных величин занимает 2967 циклов.[/uquote]Что-то мне кажется вы не правильно посчитали время работы. Ну не может быть так медленно, даже если код не самый оптимальный. Вот я тоже сделал умножение 3-байтных величин. Как и процедура выше, это копирка с официального дока. Время работы 325 циклов максимум.

Спойлер

Код: Выделить всё

;==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==
;   Процедура перемножает две 3-байтные величины
;   Исходные ресурсы:
;       -   r16 - r18   -   первый сомножитель (затирается в процессе работы)
;       -   r19 - r21   -   второй сомножитель
;   Возвращаемый результат:
;       -   r13 - r15   -   Старшие 3 байта произведения
;       -   r16 - r18   -   Младшие 3 байта произведения
;   Используемые ресурсы:
;       -   r22         -   счётчик итераций
;   Размер процедуры 40 байт (20 инструкций)
;   Время выполнения 277 + 2 * Sb циклов (максимум 325 циклов, включая rcall и ret),
;       где Sb -- число единичных бит первого сомножителя
;--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
mul_24x24:      ;   Подготовка старших байт результата и счётчика итераций
                clr     r13
                clr     r14
                clr     r15
                ldi     r22,    0x18
                lsr     r18
                ror     r17
                ror     r16
mul_24x24_1:    ;   Основной цикл процедуры
                brcc    mul_24x24_2
                add     r13,    r19
                adc     r14,    r20
                adc     r15,    r21
mul_24x24_2:    ror     r15
                ror     r14
                ror     r13
                ror     r18
                ror     r17
                ror     r16
                dec     r22
                brne    mul_24x24_1
                ret
;==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==

Код, конечно, в 3 раза медленнее, чем возведение в квадрат табличным методом, но его компактность, расход регистров (на 1 меньше, можно сделать на 2 меньше, если воспользоваться стеком) и отсутствие таблицы в 25% памяти заставляют задуматься.

[akl]

Что-то мне кажется вы не правильно посчитали время работы. Ну не может быть так медленно, даже если код не самый оптимальный.

Считает авр-студия. А умножение неоптимальное от слова совсем. Это была первая попытка сделать программу для AT90S2313 где-то в 1999м.

[Gudd-Head]

[uquote="B@R5uk",url="/forum/viewtopic.php?p=4213451#p4213451"]В моём случае, как я уже писал, мне надо навести статистику поступающих трёхбайтных величин.[/uquote]
Тогда изначально был неправильно выбран МК

[Demiurg]

2 Starichok51. Про циклы и такты. Ещё когда начал изучать AVR, помнится с того времени, что при запуске МК первая команда выполняется несколько тактов. То ли 3, то ли 4 такта. Затем внутренняя логика МК встаёт как надо. И конвейер выполняет команды за количество тактов, указанное в документации.

[Starichok51]

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

[Demiurg]

Вы все не так поняли. Я говорил не о времени запуска МК. А о внутренней логике МК. О триггерах. Первые несколько тактов подготавливают конвейер команд, чтобы после этих первых нескольких тактов была возможность работать за один такт, у большинства команд. За исключением тех, которые выполняются за несколько тактов. Уточнять в даташите.
Используется многофазное тактирование. Отсюда, выполнение самой первой команды всегда будет выполняться несколько тактов. Более точно скажут только производители МК AVR.

Тут смотрите. Быстро, навскидку. Искать более конкретную информацию сейчас нет возможности. Речь идёт о выборке, декодировании команд конвейером.

Смотрите: Первый такт. Вычитка команды. Второй такт. Отправка в дешифратор. Третий такт. Выполнение команды. Четвертый такт. Запись результата в регистры. Пока выполняются эти самые первые такты, внутренняя логика принимает нужные состояния, чтобы в дальнейшем все последующие команды выполнялись за кол-во тактов соответствующее их битности и так далее и тому подобное. Грубо, приближенно, примерно так. Более точно ищите в литературе, материалах инета.

И это высший пилотаж инженерной мысли. Когда ты заранее создал условия для выполнения поставленной задачи. Готовь сани летом, телегу зимой. Приготовить рабочее место и инструмент, чтобы ты потом не бегал, не тратил время на суету.

[Starichok51]

нет в AVR конвейера команд.

[Demiurg]

Я сейчас быстро не найду, где я прочитал про AVR. Но в этом материале было подробно расписано, как была достигнута возможность выполнения команды за один такт. Лично мне нет надобности доказывать вам, мне достаточно, что я знаю об этой особенности. Что вы будете делать с этим, это ваше дело.
Можете задать вопрос на более профессиональных площадках.

Предлагаю опыт. МК AVR могут работать на самых минимальных частотах. Вплоть до отсутствия. Поэтому, делаем следующее. Фьюзами настраиваем МК на мгновенное включение. Внешнее тактирование. Тестовую программу пишем на ассемблере. Начинаем подавать импульсы, и смотрим, когда МК дернет лапкой. Код программы может быть одной командой.

sbi DDRx, x

Для окончательного убеждения последующие команды.

nop
cbi DDRx, x
nop
sbi DDRx, x

Все команды однотактные

[Starichok51]

прежде чем дернуть лапкой, сначала нужно настроить порт на выход.

[Demiurg]

Кхм. Рулим нижним ключом. По схеме открытый сток.

[akl]

Вариант умножения двух 5-байтных величин. Используется младшая часть регистрового файла и один регистр старшей части.

mult40.txt

(861 байт) 64 скачивания

[Jack_A]

Я считаю, что все эти разговоры про "такты - циклы" - просто сотрясение воздуха. Открываем ДШ, находим .

Что такое #Clocks - смотрим соответствующий раздел System Clock с учётом System Clock Prescaler путём CLKPR. Всё. Неоднократно проверено практикой на Studio. И никаких тебе конвейеров, траволаторов и прочих транспортных средств.
Насчёт "первая команда выполняется дольше"... Включили оборудование, оно работает сутки, выполнены триллионы команд. И вдруг у нас тюкнуло: а самя-то первая после включения команда за сколько выполнилась?
Али я не прав?

[Demiurg]

С одной стороны ты прав. Не все ли равно, сколько тактов выполняется самая первая команда. Просто Старичок стал спорить. С одной стороны. С другой, знать, как разработчики МК добились выполнения большинства команд за один такт. Хотя бы для эрудиции

Вообще, опыт стоит провести. Просто нужно садиться и паять. А со временем сейчас не ахти. Тем более, дачный сезон начался. Либо на триггере импульсы соображать, либо брать ещё один тестовый МК, чтобы убрать дребезг кнопок, и выдавать импульсы с кнопки.

Мне самому интересно, спрятано ли от пользователя, за сколько тактов выполнится самая первая команда. И если спрятана, то как. А если не спрятано, то и чудесно.

[Jack_A]

Я считаю - не нужная это затея. Так можно до отдельного транзистора дойти, а там - и до электрона/дырки. ДШ даёт нам достаточный для разработчика уровень абстракции. Разве что побороться с Микрощипами, сделать лучше, что особенно актуально в плане импортозамещения.
А в практическом смысле - дача важнее: запасаться картошкой, фруктами. Солью, дровами в свете последних ситуёвин.

[Starichok51]

как разработчики МК добились выполнения большинства команд за один такт.

сколько можно повторять - не за один такт ,а за один ЦИКЛ!!!
а сколько там внутри "спрятано" тактов, мы не видим, потому этого не знаем.