请教迭代法计算平方根的整形算法

陶新成

如下是牛顿迭代法求平方根的一般算法，这种算法是浮点运算，但不适合单片机等底端CPU，所以希望有程序达人能提供一种定点求平方根的方法，谢了！
  double my_sqrt(double data){//牛顿迭代算法
    double x0,x1;
    x0 = data / 2;
    do{
       x1 = x0;
       x0 = (x1 + data /x1) / 2;
    }while(fabs(x0-x1)>= 1e-6 );
    return x0;
}

bg6agf

我觉得。全部放大若干倍就行了吧？

bg6agf

比如 要平方的数字放大10000倍。结果放大100倍。就是两位小数点了。

eye

如果不需要精度。。。
http://stackoverflow.com/questio ... ithm-for-arm-thumb2

陶新成

bg6agf 发表于 2015-11-12 23:02
比如 要平方的数字放大10000倍。结果放大100倍。就是两位小数点了。

这种方法不行的，3的平方根和30的平方根不成比例关系！

what007

陶新成 发表于 2015-11-13 09:19
这种方法不行的，3的平方根和30的平方根不成比例关系！

应该说用3和300或者30000

陶新成

eye 发表于 2015-11-12 23:40
如果不需要精度。。。
http://stackoverflow.com/questions/1100090/looking-for-an-efficient-integer-squ ...

这段代码是很不错的，至于精度它能满足一般的要求
/**
* \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;
}

bg6agf

陶新成 发表于 2015-11-13 09:19
这种方法不行的，3的平方根和30的平方根不成比例关系！

放大倍数必须按特定的倍数。我说的是10和10的平方。
3要和9配合。你完全没懂我的意思。

bg6agf

陶新成 发表于 2015-11-13 09:19
这种方法不行的，3的平方根和30的平方根不成比例关系！

在单片机上。可能用2的N次方和2的2N次方比较好。