Finding the aproximate integer Sqrt of a large prime

[Facet]

I am trying to understand how I can find the square root of a large prime number in the form of an integer value, the portion after the decimal is irelevant.

The numbers I wish to compute range around 188 multiplied by 3 to the power of 6548 plus 1, as an example. so let's say in excess of 3000 digits.

My problem with this is, using my quad-core machine, I'm finding my petty division through subtraction routine fairly slow, and (x+a/x)/2 as a solution is failing badly.

Can someone please find time to discuss with me a way of doing this?

Can a prime have a GCD with a smaller number(like the sqrt), I somehow just don't see it...

So if there is an easy solution, please let me know it =)

 

[AlephZero]

You don't need to do any division at all.

Just use (x+k)^2 = x^2 + 2kx + k^2

Call your prime p. Start with x = the largest value of 2^m where x^2 < p, and k = x/2

Find (x+k)^2. If it is less than p, let x = x+k.
Divide k by 2 and repeat, until k = 1.

If your big arithmetic routines work in decimal not binary, you can use the same sort of algorithm to pick off one decimal digit of the answer at a time.

You don't need to spend time calculatiing the right-hand digits of the numbers that you know are zero, of course.

 

[Facet]

Thankyou for the quick reply, much appreciated... =)
I really need to touch up on my maths =(
I'm sure what you posted will help me out...
I can straight away see how much faster that would be ;)
one quick question - what is m
Edit: nvm - I think I see what you say =)