MathLimitExceeded's blog

Checking For Perfect Squares Without Overflows
By MathLimitExceeded, history, 10 years ago, In English

Hi

I am solving a problem that is conceptually simple.

Given an integer x, such that 1 ≤ x ≤ 1017, check if v = 5x2 + 2x + 1 is a perfect square. I have solved this using Big Integers and long doubles in C++ (with a binary search to find the root) and used PyPy to get it accepted in Python but I did not receive satisfaction in solving it this way.

Also, __int128 do not work on SPOJ for some reason :/

I think Big Integer may be an overkill for such a problem and the uncertainty with floating point precision is never re-assuring. Hence, my question is, is there any way to solve this problem without Big Integers or long doubles in C++?

Thanks

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

, i.e. x + 1, 2x and y should form a Pythagorean triple. Then use the fact that the Pythagorean triple is always expressible as (2ab, a2 - b2, a2 + b2) for some integers a and b, and this will allow you to write the solution that uses only 64-bit data types.

→ Reply
  • »
    »
    10 years ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it 0 Vote: I do not like it

    So then we iterate over the divisors of 2x, say 2x = d1 × d2 and check if a = d1 and b = d2 gives us a Pythagorean triplet? Won't this take upto 108.5 operations?

    What if we have to answer multiple queries, say upto 100000 of them?

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it -8 Vote: I do not like it

      As far as I know you can approximate the number of divisors with for numbers  ≤ 1018, so this solution will work if you factorize x + 1 and 2x in time.

      Thought it doesn't fit your new limit of 105 queries

      → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
      ← Rev. 6  
      Vote: I like it 0 Vote: I do not like it

      Maybe you can try to solve further, (I didn't do that, not sure if it may be finished),

      ab = x, a2 - b2 = x + 1 = ab + 1, so we can find function a(b) as solution of quadratic and may be we can do something clever.

      UPD: a2 - (x / a)2 = x + 1 is biquadratic but numbers may get big again:(

      UPD2: It seems that it's equivalent to find square root you need to find:(

      → Reply
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it +8 Vote: I do not like it

Try this.
Maybe for large numbers there exists a counterexample, and you must use a random prime numbers that's still less than 109.

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Isn't this a randomized algorithm? Also, did you generate this sequence of primes similar to how primes are chosen for the Miller Rabin test or was this just trial and error till it worked?

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I think so. Because for prime p there are half of residues modulo p is square residues and isPerfectSquare give you false positive error with probability 1 / 2. But may be product of all prime numbers should be greater than v.

      → Reply
»
10 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

FWIW I'd go with long doubles for this — it's not hard to prove that the precision is enough. If we compute "y = sqrt(5*x*x + 2*x + 1)" as a long double, we get a ~57-bit number, and the error should be low (at most a 1-ulp error resulting from the large multiplication, 1 from the addition, and 1 from the sqrt, and addition and sqrt both give additive errors). The mantissa of long doubles is 64 bits, so we'll always be within 2^(57 — 64) * 3 = ~0.02 of the right answer. So if v is a perfect square, "z = (long long)round(y)" will be correct.

Then just check that "z*z == 5*x*x + 2*x + 1" modulo distinct primes with large enough product, per CRT.

→ Reply