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.

Let $\;\;\displaystyle x=\left \lfloor\frac{\sqrt{4N+(2a+1)^2}-1}{4}\right\rfloor\bmod10^8 \;\;\text{ where}\; N,a \text{ are integers.}$

When $N$ and $a$ are sufficiently large, this expression overflows in languages like C++. However, seeing as I only need the result modulo 10^8, I am wondering if there is some manipulation I can apply here to avoid overflow.

Mainly, $(2a+1)^2$ overflows when $a$ is large. However I can't just apply the modulus to each part and then go about my day because the overall answer is wrong.

share|improve this question
    
Is it even possible? –  KaliMa Nov 27 '12 at 20:35
1  
I'm not sure that it is possible, I'm just sure that there's a spare parenthesis in your expression ;) –  tohecz Nov 27 '12 at 20:42
    
@tohecz Not anymore! :D I am wondering if there is a way to simplify sqrt(4N+(2a+1)^2) in some way (completing the square?) so that I don't have to ultimately figure out the square of a (which overflows). –  KaliMa Nov 27 '12 at 20:44
    
do $a$ and $N$ themselves fit into the C++ limitations on integers? –  Dan Shved Nov 27 '12 at 20:48
    
@DanShved Long longs I believe. At their maximum value, $a$ and $N$ are both equal to exactly 10^12 –  KaliMa Nov 27 '12 at 20:55

1 Answer 1

up vote 4 down vote accepted

OK, if both $a$ and $N$ don't exceed $10^{12}$, then $x$ also doesn't exceed $10^{12}$. Therefore, there's a high chance that you'll be able to get the exact value just by doing calculations in double (which produces relative errors of about $10^{-17}$ since it has 51 binary digits) and then casting to long long in the end.

If you don't want to take that chance, there is a way to find the result more reliably, but for some cost in execution time, because this way involves binary search.

Basically, you need to find $y_0 = \left\lfloor \sqrt{4N + (2a+1)^2}\right\rfloor$, which is the maximal $y \in \mathbb{Z}$ such that $$ y^2 \leqslant 4N + (2a+1)^2. $$ Clearly, $y_0 \geqslant (2a+1)$. Our main idea is that in fact when $(2a+1)$ is as large as $N$, $(2a+1)^2$ is much larger than $4N$, therefore $y_0$ doesn't differ that much from $(2a+1)$. To make this more precise, let's intruduce the new variable $t_0 = y_0 - (2a+1)$. $t_0$ is the maximal integer $t$ such that $$ (2a+1+t)^2 \leqslant 4N + (2a+1)^2. $$ We can rewrite it like this: $$ t(4a+2+t) \leqslant 4N. $$ The function on the left is monotone, therefore we can use binary search to find $t_0$. All we need to do now is pick some reasonable boundaries $t_1$, $t_2$ such that $t_0$ is guaranteed to be between them. Let's pick $t_1=0$ and $t_2 = \left\lceil \sqrt{4N}\right\rceil$. It is quite easy to see that $t_1 \leqslant t_0 \leqslant t_2$. It is also easy to see that for every $t$ such that $t_1 \leqslant t \leqslant t_2$ the value $t (4a+2+t)$ is small enough to fit into long long. Therefore, you can perform a binary search to find the correct value for $t$, and in this binary search you'll be able to do all the calculations in long long.

UPDATE: By request, I'm adding an example for $a=N=10^{12}$. We need to find $t_0$, which is the largest integer $t$ such that $$ t(4 \cdot 10^{12} + 2 + t) \leqslant 4 \cdot 10^{12}. $$ Let's try substituting some values for $t$ and see if this inequality (which I will just call the inequality) holds. If we set $t=0$, we get $0 \leqslant 4 \cdot 10^{12}$, which is true. Therefore $0 \leqslant t_0$.

OK, now let's try setting $t=\left\lceil \sqrt{4N}\right\rceil = 2 \cdot 10^6$. We get $2 \cdot 10^6 (4 \cdot 10^{12} + 2 + 2 \cdot 10^6) \leqslant 4 \cdot 10^{12}$. Wow, this is clearly wrong, i.e. our $t$ is way too big. So we know that $0 \leqslant t_0 < 2\cdot10^6$.

Well, let's keep on guessing. Since we're doing binary search, we'll always split our "window of possibilities" into two equal parts. So our next candidate is $t = 10^6$. Again, it's easy to see that the inequality doesn't hold, so $0 \leqslant t_0 < 10^6$.

So let's try $5 \cdot 10^5$. Actually, this could go on for a while, so I'll skip a few steps. In this particular case, we'll pick smaller and smaller values of $t$, and they will all be too large. In the end, we'll come to something like this: $0 \leqslant t_0 < 2$. So, again, we will split our interval in two and check the value $t=1$. For $t=1$ the inequality says: $4 \cdot 10^{12} + 3 \leqslant 4 \cdot 10^{12}$. Hm. Even $t=1$ is too large! So $0 \leqslant t_0 < 1$, which means that $t_0=0$, which in turn means that $y_0 = \left\lfloor \sqrt{4N + (2a+1)^2}\right\rfloor = 2a+1+t_0 = 2 \cdot 10^{12} + 1$. This is it.

Actually, this example with $N=a=10^{12}$ is not very good, because this way $N$ is way smaller than $(2a+1)^2$, so adding $4N$ cannot change the value of our square root even by $1$. That's why we started with boundaries $0 \leqslant t_0 < 2 \cdot 10^{12}$ and then the right boundary kept on decreasing until we got $0 \leqslant t_0 < 1$. If we picked different numbers, for example $N=10^{12}$ and $a=10^6$, then the situation would be more interesting: your interval of possible $t_0$ values would shrink from both sides and finally zero in on the correct value of $t_0$.

share|improve this answer
    
I am having a tough time following this. Can you give a concrete example? Say using a=10^12 and N=10^12 –  KaliMa Nov 27 '12 at 21:28
    
OK, I'll add an example to my answer. But I don't know if you are well acquainted with binary search. If not - then you should probably read something about it, e.g. this wikipedia article. –  Dan Shved Nov 27 '12 at 21:32
    
@KaliMa I've updated my answer. –  Dan Shved Nov 27 '12 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.