Заголовок сообщения: квадратный корень на асме AVR
Добавлено: Пт апр 01, 2011 16:24:47
Подскажите пожалуйста удобоваримый алгоритм для целочисленного расчёта квадратного корня из 32-битного числа для реализации на ассемблере AVR (mega128). Попалась “sqrt32_fast” - square root routine - но она нерабочая. Есть реализации на Си, например:
Код:
unsigned short isqrt( unsigned long ul) { unsigned long sqr = 0; unsigned long temp; unsigned long mask = 0x40000000; do{ temp = sqr | mask; sqr >>= 1; if( temp <= ul ){ sqr |= mask; ul -= temp; } }while( mask >>= 2 ); if( sqr < ul && sqr < 0xFFFF ) ++sqr; // округление результата return (unsigned short)sqr;
Но с Си я не дружу. Кому не сложно, переведите на более понятный построчно (достаточно цикл DO) Или ткните, где есть хорошая инфа на эту тему Спасибо всем заглянувшим.
Заголовок сообщения: Re: квадратный корень на асме AVR
Добавлено: Пт апр 01, 2011 17:11:33
Встал на лапы
Зарегистрирован: Вт мар 22, 2011 22:31:01 Сообщений: 102
Рейтинг сообщения:0
В асме не силен, даю подробные комментарии, думаю разберемся:
Код:
unsigned short isqrt( unsigned long ul) { //объявление функции с одним параметром - без знаковое целое 2 байта unsigned long sqr = 0; // объявление переменной - без знаковое целое 2 байта unsigned long temp; // объявление переменной - без знаковое целое 2 байта unsigned long mask = 0x40000000; // объявление переменной - без знаковое целое 2 байта. В переменную записывается значение 0x40000000 do{ // цикл с пост условием (проверка произойдет после выполнения тела цикла) temp = sqr | mask; // побитное "или" между sqr и mask, результат записывается в temp sqr >>= 1; // сдвиг переменной sqr на 1 бит вправо if( temp <= ul ){ // условный оператор если temp меньше равно ul sqr |= mask; // побитное "или" между sqr и mask, результат записывается в sqr ul -= temp; // вычисляется разница между ul и temp результат записывается в ul } }while( mask >>= 2 ); // Сдвинуть mask на два бита в право, результат записать в mask, выполнять цикл пока mask > 0. if( sqr < ul && sqr < 0xFFFF ) ++sqr; // округление результата (если sqr меньше ul "и" sqr меньше 0xFFFF в sqr записывается sqr+1) return (unsigned short)sqr; // возвращение результата работы функции, тип переменной приводится к без знаковое целое 1 байт
Можно попробовать посмотреть в исходниках avr-libc в математической библиотеке...
_________________ Когда уже ничего не помогает - прочтите, наконец, инструкцию. Лучший оптимизатор находится у вас между ушей. (Майкл Абраш, программист Quake и QuakeII) Избыток информации ведёт к оскудению души - Леонтьев А. (сказано в 1965 г.)
Заголовок сообщения: Re: квадратный корень на асме AVR
Добавлено: Пт апр 01, 2011 17:39:28
Встал на лапы
Зарегистрирован: Вт мар 22, 2011 22:31:01 Сообщений: 102
Рейтинг сообщения:0
ChipKiller писал(а):
unsigned long - 4 байта
да конечно 4 байта. Извините бес попутал
ChipKiller писал(а):
на ассемблер перевести можно, но понятнее вряд-ли будет - AVR 8-ми битный, а корень берется из 4-х байтной величины.
Дык какая разница со сколькими байтами работать. Я когда-то и с трех! байтными числами работал, когда мне памяти не хватало... Причем выполнял с ними весь спектр арифметических и логических операций
Заголовок сообщения: Re: квадратный корень на асме AVR
Добавлено: Пт апр 01, 2011 17:52:21
Тут же дело не в понятности. У меня вся программа написана на асме. Мне необходимо произвести расчёт среднеквадратического значения, имея массив 16-битных чисел. Вся остальная обработка уже реализована. Осталась фигня - корень. Да и 4-байтные числа меня не пугают. Нелинейные преобразования на асме, в которые входит и корень - это весьма специфичные задачи.
Опс. Извиняюсь. День выдался сумотошным, рецидивы 1-го апреля, видать...
_________________ Когда уже ничего не помогает - прочтите, наконец, инструкцию. Лучший оптимизатор находится у вас между ушей. (Майкл Абраш, программист Quake и QuakeII) Избыток информации ведёт к оскудению души - Леонтьев А. (сказано в 1965 г.)
Заголовок сообщения: Re: квадратный корень на асме AVR
Добавлено: Пт апр 01, 2011 18:58:59
промоделировал я этот алгоритм в Labview. Что-то не правильно в этом алгоритме. Несколько раз перепроверил. При любом входном значении на выходе 0x7FFF.
Чуть позже: Но исходник на Си работает правильно. Я моделировал по комментариям. Всё ли верно в комментариях (не считая типы переменных)
у меня есть алгоритм дл PIC но думаю его лехко можно переписать и под AVR если желаете скину.
_________________ Мечтатель - не тот, кто сидит на диване и думает о несбыточном, а тот, кто всеми силами стремится воплотить несбыточное в реальность.
Заголовок сообщения: Re: квадратный корень на асме AVR
Добавлено: Сб апр 02, 2011 08:19:26
Jack_A писал(а):
Тема еще актуальна ? Лет 12 тому назад делал такое. Значит, аргумент - 2-байтное беззнаковое целое число ?
Аргумент - 4 байтное беззнаковое число (32-битное). Результат - 2-байтное
Цитата:
у меня есть алгоритм дл PIC но думаю его легко можно переписать и под AVR если желаете скину.
На просторах инета я видел решение для пика, причём вроде как фирменное. Но там очень уж непохожая с атмелом архитектура АЛУ. Проще написать с нуля. Попробую за выходные написать (время найти надо). Я обязательно выложу, что получится, на всеобщее обозрение.
Хороший алгоритм, быстро сходится. А для поиска первого приближения я высчитывал номер позиции самого старшего ненулевого бита и делил его на 2, число с 1 в этой позиции ( остальные нули ) было хорошим приближением.
Заголовок сообщения: Re: квадратный корень на асме AVR
Добавлено: Сб апр 02, 2011 11:55:00
Метод приближений - это по-моему метод Герона. Есть ещё метод Ньютона. Самый простой - это метод, при котором происходит вычитание по очереди нечётных чисел, но при больших числах он очень затратный по времени.
Заголовок сообщения: Re: квадратный корень на асме AVR
Добавлено: Сб апр 02, 2011 13:21:29
Ну в общем вот - предоставляю вашему вниманию полный текст расчёта квадратного корня. Принимаются все замечания по оптимизации. Время расчёта при частоте кварца 16 МГц - ~65 мкс. В принципе, меня устраивает. У меня лимит по времени - 80 мкс. Но, как говорят, нет предела совершенству. Возможно, даже в таком виде кому-то будет полезна. Большое спасибо все принимающим участие в данном вопросе. Отдельное спасибо Errorkpi за расшифровку программы на Си
unsigned short isqrt( unsigned long ul) { unsigned long sqr = 0; unsigned long temp; unsigned long mask = 0x40000000; ...
Какая приятная встреча Где только не гулял этот исходник со времени опубликования в RU.ALGORITHMS (смотреть в самом низу страницы) в 1998 и в RU.EMBEDDED в 1999... Там в RU.ALGORITHMS и объяснение есть. И другие варианты, но только для асма i386
_________________ Лень в виде мании величия: «ты гений, зачем стараться?». В виде комплекса: «всё равно не выйдет, зачем упираться?». Как логика: «если достаточно, зачем знать и уметь больше?». Цель одна: остановить. Не любит тепло работающих мышц и шум работающего мозга.
loop: movw temp0, sqr0 movw temp2, sqr2 or temp0, mask0 or temp1, mask1 or temp2, mask2 or temp3, mask3 lsr sqr3 rol sqr2 rol sqr1 rol sqr0 cp ul0, temp0 cpc ul1, temp1 cpc ul2, temp2 cpc ul3, temp3 brcs skip or sqr0, mask0 or sqr1, mask1 or sqr2, mask2 or sqr3, mask3 sub ul0, temp0 sbc ul1, temp1 sbc ul2, temp2 sbc ul3, temp3 skip: lsr mask3 rol mask2 rol mask1 rol mask0 lsr mask3 rol mask2 rol mask1 rol mask0 ; while( mask >>= 2 ) mov temp0, mask0 or temp0, mask1 or temp0, mask2 or temp0, mask3 brne loop
; если mask0..mask3 разместить в r24,r25,r26,r27, ; то последние команды можно заменить на ; while( mask >>= 2 ) sbiw mask0, 0 brne loop sbiw mask2, 0 brne loop
_________________ Лень в виде мании величия: «ты гений, зачем стараться?». В виде комплекса: «всё равно не выйдет, зачем упираться?». Как логика: «если достаточно, зачем знать и уметь больше?». Цель одна: остановить. Не любит тепло работающих мышц и шум работающего мозга.
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения