# Calculate the root of a number without useing the root function or decimal numbers

I'm trying to build a program in c# which will calculate prime numbers for me.
I'm using the BigInteger class to work with 'endless' numbers.
However, there is a big down side on this function, I can't use decimal numbers!

My method is to calculate the root of a number, round it up, and try to divide the number with all numbers between 3 and the root of the number.
The problem is, I cannot calculate the root of a number larger then 15 digits! The method I use transforms a number like 123719028390813 into 1.23719028390813E+15. As you can guess the digits after '813' are discarded and my function now thinks the root is 2.

So I started thinking about a method to get the root (rounded up) without using a root function or decimal numbers.

So these things aren't allowed:

1. X ^ 0.5.
2. root(x).

The functions this BigInteger class supports are:

• (any)Log
• multiply and diving
• power
• remainder
• Negative numbers

I tried a lot of things, but nothing was getting close...

So my questions:

• Is it possible to get the root of a number with conditions stated up here
• If yes, what is the way to do it???

Greetings,
Mixxiphoid

UPDATE:
I know this isn't the best or fastest method to calculate primes, I never said it should be...
I removed the prime-numbers tag, because I would also like to know whether it is a prime or not to calculate the root of a number with the tools named in my question.

• You can find the square root using binary search. If you're lazy you can use $\sqrt{x} = \exp(\log(x)/2)$. – Yuval Filmus Apr 24 '11 at 21:00
• @Yuval Filmus could you please give some good resources to help me with that? – Mixxiphoid Apr 24 '11 at 21:27

Yes it can be done.
Suppose that you are given $n$, you want to calculate $\lceil \sqrt{n} \rceil$, so you can apply a binary search algorithm with $k^2 \geq n \land (k-1)^2 < n$ as the stopping condition. $k$ here is the variable over which you are doing the binary search. The algorithm would be like this:

low = 0
top = n
while(true)
mid = (low+top)/2
if(mid*mid >= n and (mid-1)*(mid-1) < n)
return mid
else
if(mid*mid < n)
low = mid + 1
else
top = mid-1
end
end
end

• You're a genius! :). Thanks a lot, this saves me a lot of work! this method is quite fast too! – Mixxiphoid Apr 24 '11 at 21:40
• You are welcome :). If you you want a faster way, I think you can adapt newthon's method to work with integers (I'm not sure about this but a few examples on paper worked). The recurrence obtained with newthon's method is: $x_n = \frac{1}{2}(x_{n-1} + \frac{n}{x_{n-1}})$. You will start with $x_0 = n$ and recalculate until $x_{n-1} = x_n$. This will actually give you $\lfloor \sqrt{n} \rfloor$ but is easy to calculate $\lceil \sqrt{n} \rceil$ from that. – alejopelaez Apr 24 '11 at 21:54