寻找一个有效的整数平方根算法的ARM Thumb2 [英] Looking for an efficient integer square root algorithm for ARM Thumb2

问题描述

我要寻找一个快速的，只整数算法找到一个无符号整数的平方根（整数部分）。
在code必须在ARM的Thumb 2处理器的优异性能。这可能是汇编语言或C code。

I am looking for a fast, integer only algorithm to find the square root (integer part thereof) of an unsigned integer. The code must have excellent performance on ARM Thumb 2 processors. It could be assembly language or C code.

任何提示的欢迎。

推荐答案

<一个href=\"http://www.embedded.com/electronics-blogs/programmer-s-toolbox/4219659/Integer-Square-Roots\">Integer杰克·W·克伦肖的平方根可以作为另一个参考价值。

Integer Square Roots by Jack W. Crenshaw could be useful as another reference.

借助Ç片段存档也的有<一个href=\"http://web.archive.org/web/20080303101624/http://c.snippets.org/snip_lister.php?fname=isqrt.c\">integer平方根实现。一个超越只是整数结果，并计算应答的额外分数（定点）位。 （更新：。不幸的是，将C代码片段存档现已解散的我已经更新的链接指向页面的Web归档）

The C Snippets Archive also has an integer square root implementation. That one goes beyond just the integer result, and calculates extra fractional (fixed-point) bits of the answer. (Update: unfortunately, the C snippets archive is now defunct. I have updated the link to point to the web archive of the page.)

我定居在以下code。它本质上是由<一个href=\"http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_.28base_2.29\">Wikipedia在平方根计算方法文章。但它已被更改为使用 stdint.h 类型 uint32_t的等严格地说，返回类型可以更改为 uint16_t 。

I settled on the following code. It's essentially from the Wikipedia article on square-root computing methods. But it has been changed to use stdint.h types uint32_t etc. Strictly speaking, the return type could be changed to uint16_t.

/**
 * \brief    Fast Square root algorithm
 *
 * Fractional parts of the answer are discarded. That is:
 *      - SquareRoot(3) --> 1
 *      - SquareRoot(4) --> 2
 *      - SquareRoot(5) --> 2
 *      - SquareRoot(8) --> 2
 *      - SquareRoot(9) --> 3
 *
 * \param[in] a_nInput - unsigned integer for which to find the square root
 *
 * \return Integer square root of the input value.
 */
uint32_t SquareRoot(uint32_t a_nInput)
{
    uint32_t op  = a_nInput;
    uint32_t res = 0;
    uint32_t one = 1uL << 30; // The second-to-top bit is set: use 1u << 14 for uint16_t type; use 1uL<<30 for uint32_t type


    // "one" starts at the highest power of four <= than the argument.
    while (one > op)
    {
        one >>= 2;
    }

    while (one != 0)
    {
        if (op >= res + one)
        {
            op = op - (res + one);
            res = res +  2 * one;
        }
        res >>= 1;
        one >>= 2;
    }
    return res;
}

的好处，我发现，这是一个相当简单的修改可以返回四舍五入的答案。我发现这个有用的在一定的应用更高的精度。请注意，在这种情况下，返回类型必须是 uint32_t的，因为2的圆角方形根 ³² - 1 2 ¹⁶ 。

The nice thing, I discovered, is that a fairly simple modification can return the "rounded" answer. I found this useful in a certain application for greater accuracy. Note that in this case, the return type must be uint32_t because the rounded square root of 2³² - 1 is 2¹⁶.

/**
 * \brief    Fast Square root algorithm, with rounding
 *
 * This does arithmetic rounding of the result. That is, if the real answer
 * would have a fractional part of 0.5 or greater, the result is rounded up to
 * the next integer.
 *      - SquareRootRounded(2) --> 1
 *      - SquareRootRounded(3) --> 2
 *      - SquareRootRounded(4) --> 2
 *      - SquareRootRounded(6) --> 2
 *      - SquareRootRounded(7) --> 3
 *      - SquareRootRounded(8) --> 3
 *      - SquareRootRounded(9) --> 3
 *
 * \param[in] a_nInput - unsigned integer for which to find the square root
 *
 * \return Integer square root of the input value.
 */
uint32_t SquareRootRounded(uint32_t a_nInput)
{
    uint32_t op  = a_nInput;
    uint32_t res = 0;
    uint32_t one = 1uL << 30; // The second-to-top bit is set: use 1u << 14 for uint16_t type; use 1uL<<30 for uint32_t type


    // "one" starts at the highest power of four <= than the argument.
    while (one > op)
    {
        one >>= 2;
    }

    while (one != 0)
    {
        if (op >= res + one)
        {
            op = op - (res + one);
            res = res +  2 * one;
        }
        res >>= 1;
        one >>= 2;
    }

    /* Do arithmetic rounding to nearest integer */
    if (op > res)
    {
        res++;
    }

    return res;
}

这篇关于寻找一个有效的整数平方根算法的ARM Thumb2的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！