最快得到確切的答案的算法（不近似）當平方根

對不起，我不清楚頭銜，但我不知道如何陳述得當（隨意編輯），所以我會給例如：最快得到確切的答案的算法（不近似）當平方根

開方（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，當然我會用適當的語法

來源

2011-02-18 Templar

任何整數分解算法會做什麼，但他們難以實現。是什麼讓你覺得上述不會足夠快達到你的目的？在現實世界中，速度最快！=如果對於手頭的問題來說太難了，並且沒有必要，那麼最好。 – mellamokb 2011-02-18 16:12:39

這個算法似乎並不適用於更有趣的情況，比如2700. – 2011-02-18 16:38:31

是的我的意思是最實際的 – Templar 2011-02-18 16:47:28

對此沒有快速算法。它要求你找到所有的方形因素。這至少需要一些分解。

但是你可以加快你的方法很多。首先，你只需要找到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是爲了避免浮點數的不精確性問題。

通過所有的算法的步驟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)

來源

2011-02-18 16:57:00 btilly