Н.В. Клиначев

Алгоритм вычисления квадратного корня для микроконтроллеров с целочисленным АЛУ

Рабочие файлы: [IQsin] [IQatan2] [IQsqrt] [IQ-Математика]

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

Алгоритм вычисления корня [1] предполагает исполнение 16 итерационных приближений к искомому значению. Используются лишь самые быстрые операции целочисленного АЛУ (сложение и сдвиг). Для использования функции следует определить глобальную константу GL_Q, которая определяет количество разрядов в целом числе отведенных под дробную часть. Функция будет выполнять корректные вычисления, если значение константы будет чётным.

Чертёж 1

Листинг 1. Программный код dll-блока (javascript)

Отлаженный в модели javascript-код функции IQsqrt должен быть преобразован к эквивалентному C-коду. Но останется некоторое количество излишних операций. Цикл можно представить линейным кодом и в каждой отдельной итерации вычислить зависимые от счетчика цикла константы. Преобразованный код представлен ниже по тексту. Его можно проверить в модели. Вложенную функцию ITERATION_STEP при преобразовании в C-код следует представить макросом. В результате обработки такого кода препроцессором Си макросы будут раскрыты, константы – вычислены.

function _IQsqrt(val) {
    val = val >>> 0; // преобразование к unsigned long
    var temp = 0 >>> 0, g = 0 >>> 0;  // unsigned long

    if (val >= (1 << 30)) { g = 1 << 15; val -= 1 << 30; }

    // #define ITERATION_STEP(s)
    function ITERATION_STEP(q) {
        var s = 0 | q; /* delete this string from C-macros */
        temp = (g << s) + (1 << ((s << 1) - 2));
        if (val >= temp) { g += 1 << (s - 1); val -= temp; }
    }

    ITERATION_STEP(15);
    ITERATION_STEP(14);
    ITERATION_STEP(13);
    ITERATION_STEP(12);
    ITERATION_STEP(11);
    ITERATION_STEP(10);
    ITERATION_STEP(9);
    ITERATION_STEP(8);
    ITERATION_STEP(7);
    ITERATION_STEP(6);
    ITERATION_STEP(5);
    ITERATION_STEP(4);
    ITERATION_STEP(3);
    ITERATION_STEP(2);

    // #undef ITERATION_STEP

    temp = (g << 1) + 1;
    if (val >= temp) { g += 1; }
    return 0 | g << (GL_Q >> 1);
}

Листинг 2. Код функции IQsqrt (javascript)

Литература

  1. James Ulery. Computing Integer Square Roots. – URL: http://www.azillionmonkeys.com/qed/ulerysqroot.pdf. Дата обращения: 6.02.2017.
  2. М.И. Ледовской. Целочисленный алгоритм вычисления квадратного корня для микроконтроллеров // Известия Южного федерального университета, №3, том 75, 2007, с. 146-151. – URL: http://cyberleninka.ru/article/n/tselochislennyy-algoritm-vychisleniya-kvadratnogo-kornya-dlya-mikrokontrollerov.pdf. Дата обращения: 6.02.2017.

6.02.2017