Сборка студии Atmel: квадратный корень из 8-битного числа

Question

Я работаю с ATmega328P в Atmel Studio, и мне нужно создать функцию / алгоритм, который берет 8-битное число и вычисляет его квадратный корень. Результат должен быть представлен в двух регистрах, один для целочисленной части и другой для десятичной части.

Я думал об этом: корень должен быть где-то между указанным числом и 0 (или 1). Таким образом, я бы сделал lsr (делим на 2), и он проверил бы, больше он, меньше или равен, и затем попытался бы снова с большей точностью, чтобы получилось все более и более точным.

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

Спасибо за любые советы и помощь.

Answer 1

Просто для полноты (или бесполезного показа), вот как выполнить задачу только с целыми числами, без умножения, с помощью линейного поиска (который должен быть в большинстве случаев для значений 0-15 еще быстрее, чем бинарный поиск с умножением).).

root = -1
square = 0
addValue = 1
while (square <= input) {
    square += addValue
    addValue += 2
    ++root
}
; here root == trunc(sqrt(input))

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

Написание правильного десятичного sqrt с 8-битными целочисленными регистрами на самом деле довольно трудоемкий процесс, и я не собираюсь отнимать у вас все самое интересное.:П..

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

Т.е. значения от 0,00 до 15,99 можно превратить в 11-битные целые, выполнив *100 (0-1599), а значение sqrt (100*100) равно 100, поэтому при вводе *10000 вы получите значения 0-2550000 (необходимо минимум 22 бита, округлить до 24b), затем сделать целочисленный квадратный корень, который даст вам результат * 100 (и помещается в 11 бит), так что вы можете далее разделить его на два значения, разделив на 100.

Это может показаться простым для человека, но в реальном мире при выполнении десятичных вычислений с регистрами 8/16b это часто делалось по этому принципу, но вместо этого использовались степени двух, т. Е. *256*256, что можно сделать просто путем сдвига значения Осталось 16 бит И деление на 256 смещает значения на 8 вправо.

Таким образом, для каждого метода с двоичными числами вам нужно будет создать 24-битные части кода сложения / вычитания / сдвига. Тогда входной номер - это самые верхние 8 бит 24-битного числа. (т.е. входное значение 10 => (10<<16) == 0x0A0000) => Простое переключение. Вычислите sqrt этого значения (0x0329 или 0x032A, зависит от того, удастся ли вам сделать только усечение или округление до последнего бита), и все, результат наверняка уместится в 12 бит, а верхние 4 - это целая часть 0-15, младшие 8 бит являются десятичными в значении "количество 1/256" (0x29/256 = 0,16015625). Который может быть снова разделен простым сдвигом / сдвигом, то есть не требуется операция mul/div.

Так что все еще будет много работы, но это разумно (делать 24-битное умножение / деление на 8-битном процессоре намного сложнее, чем делать расширение add/sub/shift). И объясните, почему вы выбрали формат результата с фиксированной запятой 4:8, чтобы использовать целые 8 бит точности десятичной части результата и упростить его для дальнейших двоичных вычислений. (в 8:8 с фиксированной точкой 0,5 = 0x0080 ... попробуйте добавить это и посмотрите, что произойдет: 0x0080 + 0x0080 = 0x0100 = 1.0 без какого-либо сложного изменения результата... именно так мы делали десятичные вычисления с низкой точностью на 8-битных процессорах Например, для эффектов sin/cos также умножение / деление проще, опять же для 0.5: 0x0080 * 0x0080 = (0x4000>>8) = 0x0040 = 0.25).