algorithm - 平方根时获得精确答案(不是近似值)的最快算法

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 的立方根的质因数，然后使用来自 Fastest way to determine if an integer's square root is an integer 的建议测试 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 是为了避免 float 不精确的问题。

运行 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)