在Python中仅使用整数数学计算平方根

我正在开发一个不支持浮点数学运算的微控制器.仅整数数学.因此,没有sqrt()函数,并且我无法导入任何数学模块. MCU运行的是Python数据类型:无,整数,布尔值,字符串,函数,元组,字节列表和迭代器.而且,MCU无法执行楼层分割(//).

我的问题是我需要计算3个有符号整数的大小.

mag = sqrt(x**2+y**2+z**2)

FWIW,值只能在/ -1024范围内,我只需要一个近似值即可.有没有人有解决这个问题的模式?

最佳答案

请注意,最大可能的总和是3 * 1024 ** 2,因此最大可能的平方根是1773(底数-或1774舍入).

因此,您可以简单地将0作为开始猜测,并重复加1直到平方超过总和.最多只能进行1770次迭代.

当然那可能太慢了.一个简单的二进制搜索可以将其减少到11次迭代,并且不需要除法(我假设MCU可以右移1位,这与下限除以2相同).

编辑

以下是一些代码,用于二进制搜索返回真实平方根的底数:

def isqrt(n):
    if n <= 1:
        return n
    lo = 0
    hi = n >> 1
    while lo <= hi:
        mid = (lo + hi) >> 1
        sq = mid * mid
        if sq == n:
            return mid
        elif sq < n:
            lo = mid + 1
            result = mid
        else:
            hi = mid - 1
    return result

要检查,请运行:

from math import sqrt
assert all(isqrt(i) == int(sqrt(i)) for i in range(3*1024**2 + 1))

根据您所说的内容,这将检查所有可能的输入-而且众所周知,二进制搜索在所有情况下都很难正确执行,因此检查每种情况都很好!在“真正的”机器上不需要很长时间;-)

可能重要

为防止可能的溢出并显着加快溢出速度,请将lo和hi的初始化更改为:

    hi = 1
    while hi * hi <= n:
        hi <<= 1
    lo = hi >> 1

然后,运行时间与结果中的位数成正比,大大加快了较小结果的速度.确实,对于“关闭”的草率定义,您可以就此停下来.

出于可怜;-)

看起来OP实际上根本不需要平方根.但是对于可能负担不起分割的人来说,这是代码的简化版本,还消除了初始化中的乘法.注意:我没有使用.bit_length(),因为许多已部署的Python版本不支持.

def isqrt(n):
    if n <= 1:
        return n
    hi, hisq = 2, 4
    while hisq <= n:
        hi <<= 1
        hisq <<= 2
    lo = hi >> 1
    while hi - lo > 1:
        mid = (lo + hi) >> 1
        if mid * mid <= n:
            lo = mid
        else:
            hi = mid
    assert lo + 1 == hi
    assert lo**2 <= n < hi**2
    return lo

from math import sqrt
assert all(isqrt(i) == int(sqrt(i)) for i in range(3*1024**2 + 1))