Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
  • addition and subtraction
  • 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.

share|improve this question
5  
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

1 Answer 1

up vote 5 down vote accepted

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
share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.