optimize calculations

It seems to me that the main problem is that you call the log10 function many times. Let's write the sum of logarithms as the logarithm of the product:

If the numbers are few, so that their product does not cause overflow, then you can count.

Another problem is the use of fractional numbers, they are not multiplied as quickly as integers. I want to offer an approximate solution in integers. Note that if, for example, a[i][1] xor a[j][1] non-zero, then a[i][3] xor a[j][3] and a[i][4] xor a[j][4] can not be considered, since their addition to xor will be very small. Consider the following algorithm:

1. For each pair (i, j) , we approximately estimate A_i xor A_j as x * 2^k , where x, k some integers, and 0 <= x < 2^32 .
2. Multiply the obtained values ​​as follows: (x1 * 2^k1) * (x2 * 2^k2) = (x1 * x2) * 2^(k1+k2) = x * 2^(k1+k2) , with 0 <= x <= 2^64 . We represent x as x=y * 2^m' , with 0 <= y < 2^32 . So, (x1 * 2^k1) * (x2 * 2^k2) = y * 2^(k1+k2+m)
3. In fact, we calculated not the decimal logarithm, but the binary one, in order to get the decimal logarithm, we need to multiply by log_10 (2).

Actually, the code:

 #include <iostream> #include <vector> #include <cassert> #include <cmath> #include "/home/dima/C++/debug.h" using namespace std; double compute(const vector<uint64_t[2]> &a) { static const uint64_t two_power_32 = 1ull << 32; int n = a.size(); // текущий накопленный результат равен value * 2^power_index uint64_t value = 1; int power_index = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { uint64_t xor1 = a[i][0] ^a[j][0]; uint64_t xor2 = a[i][1] ^a[j][1]; uint64_t value_current; if (xor1 == 0) { value_current = xor2; } else if (xor1 >= two_power_32) { value_current = xor1; power_index += 64; } else { assert(0 <= xor1 && xor1 < two_power_32); value_current = (xor1 << 32) + (xor2 >> 32); power_index += 32; } while (value_current >= two_power_32) { value_current /= 2; ++power_index; } assert(0 <= value_current && value_current < two_power_32); assert(0 <= value && value < two_power_32); value *= value_current; while (value >= two_power_32) { value /= 2; ++power_index; } } } // result = log10(value * 2^power_index) // result = log10(value) + log10(2^power_index) // result = log10(value) + power_index * log10(2) double result = log10(value) + power_index * log10(2); return result * 2; } int main() { freopen("input.txt", "r", stdin); int n; cin >> n; vector<uint64_t[2]> a(n); for (int i = 0; i < n; ++i) { for (int j = 0; j < 2; ++j) { uint32_t ai1, ai2; cin >> ai1 >> ai2; a[i][j] = (uint64_t(ai1) << 32) + ai2; } } cout << compute(a) << endl; return 0; } 

Unfortunately, I didn’t compare performance, but I truly believe that it works faster than n^2 times to calculate log10 .

Update: I tested it here, with n=5000 my implementation is slightly slower than your original one. It's all about these cycles:

 while (value >= two_power_32) { value /= 2; ++power_index; } 

They can be rewritten in different ways, here’s an option for GCC:

 static const uint64_t two_power_32 = 1ull << 32; inline void divide_until_less_then_two_power_32(uint64_t &value, int &power_index) { // Эта функция эквивалентна этим строчкам: // while (value >= two_power_32) { // value /= 2; // ++power_index; // } if (value < two_power_32) { return; } int power_index_delta = 32 - __builtin_clzll(value); power_index += power_index_delta; value >>= power_index_delta; assert(0 <= value && value < two_power_32); } 

Full code:

 #include <iostream> #include <vector> #include <cassert> #include <cmath> using namespace std; #include "/home/dima/C++/debug.h" static const uint64_t two_power_32 = 1ull << 32; inline void divide_until_less_then_two_power_32(uint64_t &value, int &power_index) { // Эта функция эквивалентна этим строчкам: // while (value >= two_power_32) { // value /= 2; // ++power_index; // } if (value < two_power_32) { return; } int power_index_delta = 32 - __builtin_clzll(value); power_index += power_index_delta; value >>= power_index_delta; assert(0 <= value && value < two_power_32); } double compute(const vector<uint64_t[2]> &a) { int n = a.size(); // текущий накопленный результат равен value * 2^power_index uint64_t value = 1; int power_index = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { uint64_t xor1 = a[i][0] ^a[j][0]; uint64_t xor2 = a[i][1] ^a[j][1]; uint64_t value_current; if (xor1 == 0) { value_current = xor2; } else if (xor1 >= two_power_32) { value_current = xor1; power_index += 64; } else { assert(0 <= xor1 && xor1 < two_power_32); value_current = (xor1 << 32) + (xor2 >> 32); power_index += 32; } divide_until_less_then_two_power_32(value_current, power_index); assert(0 <= value_current && value_current < two_power_32); assert(0 <= value && value < two_power_32); value *= value_current; divide_until_less_then_two_power_32(value, power_index); } } // result = log10(value * 2^power_index) // result = log10(value) + log10(2^power_index) // result = log10(value) + power_index * log10(2) double result = log10(value) + power_index * log10(2); return result * 2; } int main() { freopen("input.txt", "r", stdin); int n; cin >> n; vector<uint64_t[2]> a(n); for (int i = 0; i < n; ++i) { for (int j = 0; j < 2; ++j) { uint32_t ai1, ai2; cin >> ai1 >> ai2; a[i][j] = (uint64_t(ai1) << 32) + ai2; } } cout << compute(a) << endl; return 0; } 

If I correctly counted everything, then this version works twice as fast.

Update 2: fixed the error (added power_index += 32; )