How to convert this Python to C++ without overflow?

Question

I have the following Python snippet

v=(2*(a/2)+1)**2
U=int(((4*N+v)**.5-1)/4)

N is on the order of 10^12, and the variable "a" takes on many values but is also of 10^12 magnitude at its largest.

However I can't seem to write this in C++ without overflowing something somewhere and I am a little stuck.

edit: And yes, the 2*(a/2) is intentional because in Python, division is the same as floor division. Sometimes a is odd so I need to halve it, floor it, then remultiply it by 2, which is what that code does.

@DavidSchwartz That is my code -- it is what I am trying to translate to C++. Unless you mean my C++ code, in which case I just tried using long longs and it wasn't able to hold everything. — KaliMa
– KaliMa, Commented Nov 27, 2012 at 3:22
I tried installing GMP a long time ago but I found it notoriously difficult to get working on Windows, and even then it was really cumbersome to work with. The resulting values I am after are integers (in the mathematical sense) as opposed to decimal/floating point. The U=int() part just cuts off any decimal chunk as it isn't needed for my program. — KaliMa
– KaliMa, Commented Nov 27, 2012 at 3:27
For instance, for a=10^12, v is 4000004000001 and U is 707106 — KaliMa
– KaliMa, Commented Nov 27, 2012 at 3:29
@KaliMa: Whether you like it or not, the with such numbers if you want a precise answer you will need a big integer library, or you can use double and loose precission. The value of v is in the range of 10^24, which is way higher than any integer that common platforms have — David Rodríguez - dribeas
– David Rodríguez - dribeas, Commented Nov 27, 2012 at 3:39

Mark Ransom · Accepted Answer · 2012-11-27 03:32:58Z

3

>>> a=10**12
>>> v=(2*(a/2)+1)**2
>>> log(v,2)
79.72627427729958

The value you're calculating needs 80 bits, and a long long is only 64. You'll need an extended arithmetic package to handle it.

answered Nov 27, 2012 at 3:32

Mark Ransom

310k44 gold badges423 silver badges660 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

KaliMa Over a year ago

Aaauuuughh. GMP is such a pain to work with. Can't get anything working 85% of the time. Thanks though.

David Schwartz Over a year ago

It's actually pretty easy from C++.

Matt K Over a year ago

How do you know you aren't losing precision in the Python version already? (4*N+v)**.5 returns a float, even for N = 1 and v = 0.

KaliMa Over a year ago

@mkb it is not so imprecise that the integer value of the result will be off. My value of N would need to be much, much larger for that to happen

KaliMa Over a year ago

Also, how do I set a GMP variable to multiply from two vars? I am trying mpz_mul(v, ha, ha); where ha is the (2*(a/2)+1)^2 result as a long long, v being a mpz_class

Collectives™ on Stack Overflow

How to convert this Python to C++ without overflow?

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related