Перейти к содержанию
Поиск
    

Квадратный корень в целых числах

Ответить

alex_shevchenko    0

alex_shevchenko
Опубликовано (изменено) · Жалоба

Процедура целочисленного извлечения квадратного корня из 16-битного числа методом вычисления "в столбик" и округлением до ближайшего целого. (MPLAB® ASM30 Assembler для семейства PIC24, dsPIC30, dsPIC33.) Время вычисления - max 85 тактов, за исключением значений 0 и 1 - 10 тактов.

 

;-----------------------------------------------------------------------------------------------------------------------;
;                    An integral calculation of the SQRT16                                    ;
;                                                                                             ;
;    Execution time:    85Tcy (2.88uS @ Tcy=33.9nS)                                                                        ;
;    SFR used:        W0,W1,W2,W3                                                                ;
;    Dependencies:    No dependencies                                                            ;
;    Inputs:            W0 = input 16-bit unsigned int value                                    ;
;    Outputs:        W0 = output SQRT value of input unsigned int                            ;
;                    W1 = remainder                                                            ;
;    Description:    Целочисленное извлечение квадратного корня из 16-битного числа методом вычисления "в столбик";
;                    с округлением до ближайшего целого.                                        ;
;-----------------------------------------------------------------------------------------------------------------------;
_Sqrt16:
        CP            W0,                #0x0001; Сравнение аргумента с '1'.
        BRA            GTU,            .+6; Если аргумент больше - переход к алгоритму извлечения корня, иначе:
        CLR            W1            ; Техническое обнуление регистра остатка.
        RETURN                    ; выход с аргументом в качестве результата.
        MOV            #0x0000,        W1; Предварительная очистка регистра результата.
        MOV            #0x4000,        W3; k = 0x4000
        IOR            W1,                W3,                W2; tmp = k | res
        LSR            W1,                W1; res >>= 1;
        CP             W2,                W0; 
        BRA            GTU,            . +6; if( x >= tmp ) {
        SUB            W0,                W2,                W0; x -= tmp;
        IOR            W1,                W3,                W1; res |= k; }
        LSR            W3,                #2,                W3; k >>= 2;
        BRA            NZ,                . -14; пока (k != 0) - переход на очередную итерацию.
        CP            W0,                W1; Сравнение результата и остатка.
        BRA            LEU,            . +4; Если остаток меньше либо равен - пропуск инструкции, иначе:                        
        INC            W1,                W1; инкремент результата.
        EXCH        W0,                W1; Технический своп регистров результата и остатка.
        RETURN                    ; Выход из процедуры.

 

 

P.S. После дизассемблирования стало понятно, что Q15sqrt(x) - использует разложение степенной функции в ряд Тейлора, с хорошей оптимизацией алгоритма. :)

Изменено пользователем alex_shevchenko

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

alex_shevchenko    0

alex_shevchenko
Опубликовано (изменено) · Жалоба

Вариант адаптивной процедуры целочисленного извлечения квадратного корня из 16-битного числа методом вычисления "в столбик" и округлением до ближайшего целого. Время вычисления сокращается в зависимости от разрядности числа и составляет 24-90 машинных циклов.

 

;-----------------------------------------------------------------------------------------------------------------------;
;					An integral calculation of the SQRT16	;
; 													;
; Execution time:	max 90Tcy								;
; SFR used:	W0,W1,W2,W3								;
; Dependencies:	No dependencies							;
; Inputs:		W0 = input 16-bit unsigned int value	;
; Outputs:		W0 = output SQRT value of input unsigned int;
; Description:	Целочисленное извлечение квадратного корня из 16-битного числа методом вычисления "в столбик";
;		с округлением до ближайшего целого.		;
;-----------------------------------------------------------------------------------------------------------------------;
_Sqrt16:
CP	W0,		#0x0001; Сравнение аргумента с '1'.
BRA	GTU,		.+4; Если аргумент больше - переход к алгоритму извлечения корня, иначе:
RETURN			; выход с аргументом в качестве результата.
MUL.UU	W2,		#0,		W2; Предварительная очистка регистра накопления результата/остатка.
FF1L	W0,		W1; Определение номера старшего разряда.
DEC	W1,		W1; Технический декремент номера разряда.
BCLR	W1,		#0; Проверка номера разряда на четность +
SUBR	W1,		#14,		W1; разбиение разрядов на пары.
BSW.C	W3,		W1; Инициализация начального приближения корня.
IOR	W2,		W3,		W1; tmp = W2 = k | res		
LSR	W2,		W2; res >>= 1;
CP	W1,		W0; 
BRA	GTU,		.+6; if( x >= tmp ) {
SUB	W0,		W1,		W0; x -= tmp;		
IOR	W2,		W3,		W2; res |= k;  }
LSR	W3,		#2,		W3; k >>= 2;
BRA	NZ,		.-14		
CP	W0,		W2; Срвнение результата и остатка.
BRA	LEU,		.+4; Если остаток меньше либо равен - пропуск инструкции, иначе					
INC	W2,		W2; инкремент результата.
EXCH	W0,		W2; Технический своп регистров результата и остатка.
RETURN			; Выход из процедуры.

Изменено пользователем IgorKossak
[codebox] для длинного кода!!!!

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Rst7    5

Rst7
Опубликовано · Жалоба
Вариант адаптивной процедуры ...

 

Это все хорошо, а название топика читали?

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

alex_shevchenko    0

alex_shevchenko
Опубликовано (изменено) · Жалоба

Все это легко перепихивается и на другие платформа. В данный момент пишу под PICи, а в АРМ влазить нет времени. B)

 

Еще пару десятков тактов в среднем можно сэкономить, если развернуть цикл в ущерб объему (для тех, кому важна скорость):

 

_Sqrt16:
 SUB		W0,		#0x0000,		W2; Сравнение аргумента с '0' + техническое перемещение.
 BRA		GTU,		.+4		; Если аргумент больше - переход к алгоритму извлечения корня, иначе:
 RETURN					; выход с аргументом в качестве результата.
 FF1L		W0,		W0		; Определение номера старшего разряда.
 DEC		W0,		W0		; Технический декремент номера разряда.
 LSR		W0,		W0		; Разбиение разрядов числа на пары.
 MUL.UU		W0,		#7,		W0; Вычисление длины прыжка с обнулением регистра результата W1.
 BRA		W0				; Переход к итерации с необходимым номером.		
; Итерация 1
 MOV		#0x4000,		W0		; k = 0x4000.
 BRA		.+4				; Сокращение одного машинного такта.
 NOP						; Техническое заполнение тела итерации.
 CP	 	W0,		W2		; 
 BRA		GTU,		.+6		; if(x >= tmp) {
 SUB		W2,		W0,		W2; x -= tmp;
 IOR		W1,		W0,		W1; res |= k; }
; Итерация 2
 MOV		#0x1000,		W0		; 
 IOR		W0,		W1,		W3; tmp = k | res
 LSR		W1,		W1		; res >>= 1;
 CP	 	W3,		W2		; 
 BRA		GTU,		.+6		; if(x >= tmp) {
 SUB		W2,		W3,		W2; x -= tmp;
 IOR		W1,		W0,		W1; res |= k; }
; Итерация 3
 MOV		#0x0400,		W0		; 
 IOR		W0,		W1,		W3; tmp = k | res
 LSR		W1,		W1		; res >>= 1;
 CP	 	W3,		W2		; 
 BRA		GTU,		.+6		; if(x >= tmp) {
 SUB		W2,		W3,		W2; x -= tmp;
 IOR		W1,		W0,		W1; res |= k; }
; Итерация 4
 MOV		#0x0100,		W0		; 
 IOR		W0,		W1,		W3; tmp = k | res
 LSR		W1,		W1		; res >>= 1;
 CP	 	W3,		W2		; 
 BRA		GTU,		.+6		; if(x >= tmp) {
 SUB		W2,		W3,		W2; x -= tmp;
 IOR		W1,		W0,		W1; res |= k; }
; Итерация 5
 MOV		#0x0040,		W0		; 
 IOR		W0,		W1,		W3; tmp = k | res
 LSR		W1,		W1		; res >>= 1;
 CP	 	W3,		W2		; 
 BRA		GTU,		.+6		; if(x >= tmp) {
 SUB		W2,		W3,		W2; x -= tmp;
 IOR		W1,		W0,		W1; res |= k; }
; Итерация 6
 MOV		#0x0010,		W0		; 
 IOR		W0,		W1,		W3; tmp = k | res
 LSR		W1,		W1		; res >>= 1;
 CP	 	W3,		W2		; 
 BRA		GTU,		.+6		; if(x >= tmp) {
 SUB		W2,		W3,		W2; x -= tmp;
 IOR		W1,		W0,		W1; res |= k; }
; Итерация 7
 MOV		#0x0004,		W0		; 
 IOR		W0,		W1,		W3; tmp = k | res
 LSR		W1,		W1		; res >>= 1;
 CP	 	W3,		W2		; 
 BRA		GTU,		.+6		; if(x >= tmp) {
 SUB		W2,		W3,		W2; x -= tmp;
 IOR		W1,		W0,		W1; res |= k; }
; Итерация 8
 IOR		W1,		#0x0001,		W3; tmp = k | res
 LSR		W1,		W0		; res >>= 1;
 CP	 	W3,		W2		; 
 BRA		GTU,		.+6		; if(x >= tmp) {
 SUB		W2,		W3,		W2; x -= tmp;
 IOR		W0,		#0x0001,		W0; res |= k; }
; Округление до ближайшего целого	
 CP		W2,		W0		; Сравнение результата с остатком.
 BRA		LEU,		.+4		; Если остаток меньше, либо равен - пропуск инструкции, иначе:
 INC		W0,		W0		; инкремент результата.
 RETURN					; Выход из процедуры.

Изменено пользователем IgorKossak
[codebox] для длинного кода!!!!!!!

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

alex_shevchenko    0

alex_shevchenko
Опубликовано (изменено) · Жалоба

Маленькая оговорка:

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

Если где-то между ними:

 

SUBR W1, #14, W1 ; разбиение разрядов на пары.

BSW.C W3, W1 ; Инициализация начального приближения корня

 

произойдет прерывание без сохранения контекста (LB статусного регистра SR), то результат вычисления может быть потерян.

Если нет желания возиться с контекстом, то лучше использовать что-то вроде:

 

SUBR W1, #14, W1 ; разбиение разрядов на пары.

MOV #0x0001, W3 ;

SL W3, W1, W3 ; Инициализация начального приближения корня.

 

или

 

DISI #2 ; выкл. прерываний на две инструкции.

SUBR W1, #14, W1 ; разбиение разрядов на пары.

BSW.C W3, W1 ; Инициализация начального приближения корня

 

Т.е. на один такт больше.

Изменено пользователем alex_shevchenko

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

GenaSPB    11

GenaSPB
Опубликовано · Жалоба
прерывание без сохранения контекста

Ой... поясните, где в жизни на такое можно напороться?

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

ReAl    0

ReAl
Опубликовано · Жалоба
Еще пару десятков тактов в среднем можно сэкономить, если развернуть цикл в ущерб объему (для тех, кому важна скорость):
А чтобы меньше людям мешать -- в тег codebox завернуть этот оффтопик нельзя было? Раз не выходит не лезть в ARM-ветку со своим пиком?

 

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

 

Ладно бы ещё было на С, но с какой-то пик-фичой типа атрибутов, без которой код работоспособен, но просто с ними он на пике эффективнее.

Если считаете, что это легко спортить на арм, то спортьте и покажите. Нет -- зачем это тут?

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

IgorKossak    0

IgorKossak
Опубликовано · Жалоба

alex_shevchenko, длинные простыни Вашего кода позаворачивал в тэги codebox там где это было возможно.

Вклинивание в ветку ARM с пиками пока терплю.

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

Модератор.

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

alex_shevchenko    0

alex_shevchenko
Опубликовано · Жалоба

To IgorKossak,

 

Банами меня не напугаешь. Зависание в форумах для меня не есть жизненно необходимым, а так - от нехрен делать в перерывах между делом. Обойдусь легко. И если мало интересует содержание и наполненность ресурса - можешь банить и удалять. Не имею возражений.

Но все-таки, наверное, будет правильно, если перенести это с одноименным названием в ветку к пикам. А то некоторые армисты при слове PIC аж из себя выходят и бьются в конвульсиях. Сердечко может не выдержать.

Please. :biggrin:

 

 

P.S. Крайне неудачно настроен интерфейс движка. Одна минута на редактирование - это издевательство над пользователями. Редактор - совсем не wysiwyg. И ту ерунду, которую он высыпает в и тоге на экран, я успеваю только просмотреть, но изменить что-то уже нет возможности. Поэтому - или миритесь с конечным результатом, или СДЕЛАЙТЕ УДОБНЫЙ ИНТЕРФЕЙС ПОЛЬЗОВАТЕЛЯ.

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

IgorKossak    0

IgorKossak
Опубликовано · Жалоба
наверное, будет правильно, если перенести это с одноименным названием в ветку к пикам.

Какой же Вы умный задним числом. Отчего же сразу не разместить тему где положено?

или миритесь с конечным результатом, или СДЕЛАЙТЕ УДОБНЫЙ ИНТЕРФЕЙС ПОЛЬЗОВАТЕЛЯ.

Я поставлю вопрос иначе - или соблюдайте правила форума на том, что есть или на появляйтесь здесь вообще. Ка Вы без форума, так и форум без Вас вполне способен обойтись.

 

И последнее - публичное обсуждение действий модератора запрещено правилами, так что получИте обещанные 15 суток.

Модератор.

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
К сожалению, ваш контент содержит запрещённые слова. Пожалуйста, отредактируйте контент, чтобы удалить выделенные ниже слова.
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
×
  • Создать...