math - Fastest algorithm of getting precise answer (not approximated) when square-rooting -

sorry unclear title, don't know how state (feel free edit), give example:

sqrt(108) ~ 10.39... want sqrt(108)=6*sqrt(3) means expanding 2 numbers

so that's algorithm

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 =                            //in given example first 6     second = number / (i*i)              //in given example second 3     = 0   i-- 

maybe know better algorithm?

if matters use php , of course use appropriate syntax

there no fast algorithm this. requires find square factors. requires @ least factorizing.

but can speed approach quite bit. start, need find prime factors cube root of n, , test whether n perfect square using advice fastest way determine if integer's square root integer.

next speed up, work bottom factors up. every time find prime factor, divide n repeatedly, accumulating out squares. reduce size of n, reduce limit you'll go to. lets take advantage of fact numbers divisible small numbers, reduces size of number have left factor, , lets cut off search sooner.

next performance improvement, start become smarter numbers trial divisions by. instance special case 2, test odd numbers. you've doubled speed of algorithm again.

but aware that, of these speedups, you're getting more efficient brute force. still brute force, , still won't fast. (though much, faster current idea.)

here pseudocode make clear.

integer_sqrt = 1 remainder = 1  # first special case 2. while 0 == number % 4:     integer_sqrt *= 2     number /= 4  if 0 == number / 2:     number /= 2     remainder *= 2  # run through odd numbers cube root. # note beyond cube root there no way factor #    prime * prime * product_of_bigger_factors limit = floor(cube_root(number + 1)) = 3 while <= limit:     if 0 == number % i:         while 0 == number % (i*i):             integer_sqrt *=             number /= i*i         if 0 == number % (i*i):             number /=             remainder *=         limit = floor(cube_root(number + 1))     += 2  # , check whether landed on square of prime.  possible_sqrt = floor(sqrt(number + 1)) if number == possible_sqrt * possible_sqrt:     integer_sqrt *= possible_sqrt else:     remainder *= number  # , answer integer_sqrt * sqrt(remainder) 

note various +1s avoid problems imprecision of floating point numbers.

running through of steps of algorithm 2700, here happens:

number = 2700 integer_sqrt = 1 remainder = 1  enter while loop     number divisible 4         integer_sqrt *= 2 # 2         number /= 4 # 675      number not divisible 4         exit while loop  number not divisible 2  limit = floor(cube_root(number + 1)) # 8 = 3 enter while loop     < =limit # 3 < 8         enter while loop             number divisible i*i # 9 divides 675                 integer_sqrt *= 3 # 6                 number /= 9 # 75              number not divisible i*i # 9 not divide 75                 exit while loop          divides number # 3 divides 75             number /= 3 # 25             remainder *= 3 # 3          limit = floor(cube_root(number + 1)) # 2      += 2 # 5      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 # 30  # , answer integer_sqrt * sqrt(remainder) ie 30 * sqrt(3)