balbit's blog

By balbit, history, 12 months ago, In English

Here is a normal implementation of Pollard's Rho algorithm.

ll c = 1;
ll g(ll x, ll n){
    return (x*x+c)%n;
}

ll po(ll n){
    ll x = 2, y = 2, d = 1;
    while (d==1){
        x = g(x,n); y = g(g(y,n),n);
        d = __gcd(llabs(x-y),n);
    }
    if (d==n) return -1;
    return d;
}

However, the product x*x will overflow if n is too big (outside of int range). Is there a way to do the multiplication quickly (without using bigint or adding another log factor), or replacing the polynomial with some other function?

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

»
12 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Try using __int128 if compiler supports it.

»
12 months ago, # |
  Vote: I like it +56 Vote: I do not like it

$$$ab \mod n = ab - \lfloor ab/n \rfloor n$$$. Calculate $$$ab/n$$$ in long double, then cast it to long long, it will differ from the real value of $$$\lfloor ab/n \rfloor$$$ by $$$\pm 1$$$. Let the value you got be $$$d$$$. Then calculate $$$ab - dn$$$ in long long. You will get the answer $$$\pm n$$$. Of course, technically long long overflow is undefined behavior, but in most cases it behaves just like multiplying modulo $$$2^{64}$$$ so it's not a big deal. You can always use unsigned long long to be extra sure, but then you need to be careful with negative values.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why can't it differ by 2? Can you prove that the difference is not bigger than 1?

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it +28 Vote: I do not like it

      Assumes $$$a<n$$$ and $$$b<n$$$, $$$\lfloor ab/n \rfloor <n$$$, and long double has 64 bits for mantissa, so it would be (almost) enough precision.

      Proof sketch: ($$$c_1$$$ and $$$c_2$$$ are some "small enough" constants)

      Assumes the computer will always round to the nearest representable long double value. Note that conversion from long long to long double does not lose information (because long double mantissa is 64 bits long).

      Therefore the relative error of $$$ab$$$ does not exceed $$$2^{-64} \times c_1$$$, and the relative error of $$$ab/n$$$ doesn't exceed $$$2^{-64} \times c_2$$$, and (because $$$ab/n < n$$$) the absolute error doesn't exceed $$$n \times 2^{-64} \times c_2 < 1$$$. (QED)

»
12 months ago, # |
  Vote: I like it +18 Vote: I do not like it

You can compute this function modulo n in O(log x) using something like binary powering. You need to use that x * a = (x * (a — 1) + x) % n if a is odd and x * a = (2 * (x * (a / 2)) % n if a is even.

»
9 months ago, # |
  Vote: I like it -15 Vote: I do not like it

without using bigint

That's a mistake. Bigint is less bug-prone than obscure tricks in this case.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    If you can use prepared template, then both are not bug-prone. If you can't, big int may be more bug prone because it's more complex. (In this case you need to implement modulus)

    Still, the tricks described here are pretty simple, and in the unlikely case you can't get it correct in about 5 minutes, you can switch to big int without too much time wasted...

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it -14 Vote: I do not like it

      You won't always have a prepared template for a specific thing, or you can be in a situation where you need to modify your template a bit. If you don't know how, you're screwed.

      You should know how to code a simple bigint — bruteforce sum, difference, product — by hand quickly, always without exception. If your problem can be solved by using five 64-bit ints to store a 128-bit number, that's what you should do because it wastes as little time as possible.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what this algo should do? on n=21, 22 and 25 (and others examples) it returns -1

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Try checking out the source code for function "multiplyHigh" in java.lang.Math

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Even if you have the 128-bit representation of the product, it's not trivial to compute that value modulo mod.

»
9 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

Another method: In case the modulus is fixed and a perfect square (such as $$$10^{18}$$$), it's possible to be reasonably fast using integer arithmetic only. (It's easy to derive the function yourself. See function splitdigit in code below)


About performance:

Some notes about Pollard Rho being slow: https://codeforces.com/blog/entry/62287#comment-462676

Benchmark:

code
Benchmark code

Result: (best to worst)

  • Locally, with fast-math: subquotient4,subquotient1,subquotient2,splitdigit,subquotient5,subquotient3,useint128
  • Locally, without fast-math: splitdigit,subquotient4,subquotient1,subquotient2,subquotient5,useint128,subquotient3
  • Codeforces, with fast-math: subquotient4,subquotient1,subquotient2,subquotient3,splitdigit,subquotient5,
  • Codeforces, without fast-math: subquotient4,subquotient1,subquotient2,splitdigit,subquotient5,subquotient3