求平方根时获得精确答案（非近似）的最快算法

Question

抱歉标题不清楚，但我不知道如何正确表述（请随意编辑），所以我将给出示例：

sqrt(108) ~ 10.39...但我希望它像这样 sqrt(108) =6*sqrt(3) 所以这意味着扩展到两个数字

这就是我的算法

i = floor(sqrt(number))                  //just in case, floor returns lowest integer value :)
while (i > 0)                            //in given example number 108
  if (number mod (i*i) == 0)
    first = i                            //in given example first is 6
    second = number / (i*i)              //in given example second is 3
    i = 0
  i--

也许你知道更好的算法？

如果重要的话我会使用 PHP，当然我会使用适当的语法

Answer 1

对此没有快速算法。它要求您找到所有平方因子。这至少需要一些因式分解。

但你可以大大加快你的接近速度。首先，您只需要找到 n 的立方根以内的质因数，然后使用 确定整数的平方根是否是整数的最快方法。

接下来加快速度，从底层开始工作。每次找到质因数时，重复将 n 除以它，累加平方。当你减少 n 的大小时，就会减少你将达到的限制。这可以让您利用大多数数字可以被一些小数字整除的事实，从而快速减少剩余要分解的数字的大小，并让您更快地停止搜索。

接下来的性能改进，开始变得更聪明地知道你用哪些数字来进行试除。例如特殊情况2，则只测试奇数。您刚刚再次将算法的速度提高了一倍。

但请注意，即使有了所有这些加速，您也只是获得了更高效的强力。它仍然是蛮力，并且仍然不会很快。 （尽管它通常比您当前的想法快得多。）

这里有一些伪代码可以清楚地说明这一点。

integer_sqrt = 1
remainder = 1

# First we special case 2.
while 0 == number % 4:
    integer_sqrt *= 2
    number /= 4

if 0 == number / 2:
    number /= 2
    remainder *= 2

# Now we run through the odd numbers up to the cube root.
# Note that beyond the cube root there is no way to factor this into
#    prime * prime * product_of_bigger_factors
limit = floor(cube_root(number + 1))
i = 3
while i <= limit:
    if 0 == number % i:
        while 0 == number % (i*i):
            integer_sqrt *= i
            number /= i*i
        if 0 == number % (i*i):
            number /= i
            remainder *= i
        limit = floor(cube_root(number + 1))
    i += 2

# And finally check whether we landed on the square of a prime.

possible_sqrt = floor(sqrt(number + 1))
if number == possible_sqrt * possible_sqrt:
    integer_sqrt *= possible_sqrt
else:
    remainder *= number

# And the answer is now integer_sqrt * sqrt(remainder)

请注意，各种+1是为了避免浮点数不精确的问题。

运行 2700 的算法的所有步骤，会发生以下情况：

number = 2700
integer_sqrt = 1
remainder = 1

enter while loop
    number is divisible by 4
        integer_sqrt *= 2 # now 2
        number /= 4 # now 675

    number is not divisible by 4
        exit while loop

number is not divisible by 2

limit = floor(cube_root(number + 1)) # now 8
i = 3
enter while loop
    i < =limit # 3 < 8
        enter while loop
            number is divisible by i*i # 9 divides 675
                integer_sqrt *= 3 # now 6
                number /= 9 # now 75

            number is not divisible by i*i # 9 does not divide 75
                exit while loop

        i divides number # 3 divides 75
            number /= 3 # now 25
            remainder *= 3 # now 3

        limit = floor(cube_root(number + 1)) # now 2

    i += 2 # now 5

    i is not <= limit # 5 > 2
        exit while loop

possible_sqrt = floor(sqrt(number + 1)) # 5

number == possible_sqrt * possible_sqrt # 25 = 5 * 5
    integer_sqrt *= possible_sqrt # now 30

# and now answer is integer_sqrt * sqrt(remainder) ie 30 * sqrt(3)

Answer 2

不太可能有快速的算法来解决这个问题。请参阅https://mathoverflow.net/questions/16098/complexity-of-testing-integer -square-freeness 特别是https://mathoverflow.net /questions/16098/测试复杂性-整数平方-自由度/16100#16100

Answer 3

1. 按升序列出所有素因数，例如 2700 = 2*2*3*3*3*5*5。这是最慢的步骤，需要 sqrt(N) 运算。
2. 创建一个累加器（从 1 开始）。扫描此列表。对于每对数字，将累加器乘以它们（其中之一）。所以扫描完上面的列表后，你会得到 2*3*5。
3. 累加器是您的乘数。其余的仍保留在平方根下。