Finding the maximum GCD of all pairs

Question

The code below is for Hackerrank competition. Seems that it works correctly but performs very slowly and because of it can't pass some tests.

The task is to find the maximum GCD of all possible pairs of two positive integers \$x, (1 \leq x \leq 10^6)\$ and \$y, (1 \leq y \leq 10^6)\$, where \$x\$ belongs to array \$A\$ and \$y\$ belongs to array \$B\$. Both arrays have the same size, \$(1 \leq \text{size} \leq 10^5)\$. If there is more than one pair with the same GCD, then use the GCD with the maximum sum of its numbers i.e. \$(x + y)\$. Print the sum of elements of this maximum-sum pair.

Input is given in the following way

• first line - size of the arrays

• second line - elements for the first array

• third line - elements for the second array

e.g

5
3 1 4 2 8
5 2 12 8 3 

---

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

inline size_t countGcd( size_t n1, size_t n2 ) {
   return ( n2 != 0 ) ? countGcd( n2, n1 % n2 ) : n1;
}

int main() {

size_t num = 0;
std::cin >> num;
size_t elem = 0;
std::vector< size_t > arr;
for ( size_t i = 0; i < num; ++i ) {
    std::cin >> elem;
    arr.push_back( elem );
}
size_t max_sum = 0;
size_t max_gcd = 0;
for ( size_t i = 0; i < num; ++i ) {
    std::cin >> elem;

    for ( size_t j = 0; j < arr.size(); ++j ) {
        size_t gcd = ( ( elem >= arr.at( j ) ) ? ( elem % arr.at( j ) == 0 ? arr.at( j ) : countGcd( elem, arr.at( j ) ) ) : ( arr.at( j ) % elem == 0 ? elem : countGcd( elem, arr.at( j ) ) ) );
        if ( gcd > max_gcd ) {

            max_sum = elem + arr.at( j );
            max_gcd = gcd;
        } else if ( gcd == max_gcd ) {
            size_t sum = elem + arr.at( j );
            if ( sum > max_sum )
                max_sum = sum;
        }    
    }
}
std::cout << max_sum << std::endl;

return 0;
}

I tried different GCD implementations ( Euclidean algorithm ( both recursive and iterative ), Binary GCD algorithm ( both recursive and iterative ) ) but without success. Seems that I have to change something inside main function, maybe rid off the if-else inside the for-loops but actually have no idea how to do this.

Answer 1

My explorations on GCD and performance

Aside: you might find My blog post interesting, where I found bottlenecks in GCD including branch prediction, lack of instruction parallelism, and the DIV instruction. Even things like Modulo is significantly slower for signed types compared to unsigned types of the same size! Since the values being used are all positive, that is another speedup.

For some operations, the opcode is faster for 32-bit than 64-bit; so switching to a smaller version once the numbers get small enough will speed it up.

I found that an algorithm written for computers in 1961 that does no division runs slower than the modern expression when coded naively, but once the bottlenecks in that are found and eliminated, it runs much faster. The CPU can burn through lots of primitive instructions so the increased length is not significant; it’s the traffic jams inside the CPU that kill the performance.

---

Your code review

Don’t write using namespace std;.

You can, however, in a CPP file (not H file) or inside a function put individual using std::string; etc. (See SF.7.)

---

You should break up the monolithic main into smaller functions. It is clear that first you read the input, then you do the actual work.

Write the function that does the real work isolated from any real I/O. It takes parameters and returns values. You can call that from test cases that means you don’t have to type the input yourself every time! And you can have a function to read the input in the manner needed, for the final deliverable.

Meanwhile, the functions you write to load arrays from a file like that can be reused for the next problem. You can be sure it has no code tangled up with the old program — it is just for getting input.

Your code seems complex since GCD itself is just a few lines. Is that what countGcd is? The name is odd if it returns GCD, not the count of something. No, that’s just one step as there is no while loop. Point is, I have no idea from the names and complete lack of comments just what this code does or how it works.

---

    for ( size_t j = 0; j < arr.size(); ++j ) {

It appears that this could be a range-based for loop. I see you refer to arr.at( j ) eight times! And you are wondering about performance?

for (auto current : array) {

and then I think the long line is the actual GCD calculation because of its name:

    auto GCD= compute_GCD (current, elem);

put that in a separate (readable) function. It will also make it easy to change the implementation of the GCD algorithm itself without messing with the rest of the program!

        if ( gcd > max_gcd ) {

            max_sum = elem + arr.at( j );
            max_gcd = gcd;
        } else if ( gcd == max_gcd ) {
            size_t sum = elem + arr.at( j );
            if ( sum > max_sum )
                max_sum = sum;
        }    

You want to accumulate the maximum incrementally. It’s probably not worth using an stl algorithm for that since you are giving it the input incrementally rather than having a prepared list. It can, however, but split into a separate function or accumulator class.

The complex part here is the tie-breaking. Understand that the description is simply that of a compound key! Think of sorting names: if the last name matches, then sort by the first.

Now std::pair already does this for comparison operators. So make a pair{GCD,sum} of the current trial, and have the max variable of the same type. Now you just need a straightforward remember the largest accumulator.

using respair = std::pair<size_t, size_t>;

static respair best { };

void check_for_best (const respair& x)
{
    best = std::max (best,x);
}

basically, it reduces to one line.

max.second will be the max sum.

---