4
\$\begingroup\$

From this Wikipedia article, the following unsolved problem is presented as a result of Waring's problem:

{\displaystyle 3^{k}-2^{k}\left\lfloor \left({\tfrac {3}{2}}\right)^{k}\right\rfloor >2^{k}-\left\lfloor \left({\tfrac {3}{2}}\right)^{k}\right\rfloor -2}

It has been proven that a finite number of k exist, and so far none are known. The follow code is meant to brute-force search for a solution:

#include <boost/multiprecision/cpp_dec_float.hpp>
//#include <cmath>
#include <iostream>

typedef boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>> arbFloat;

enum returnID {success = 0, precisionExceeded = 1};

int main(){
    arbFloat k;

    for(k = 6; pow(3, k) - (pow(2, k) * floor(pow(1.5, k))) <= pow(2, k) - floor(pow(1.5, k)) - 2; ++k);

    if(pow(3, k) - (pow(2, k) * floor(pow(1.5, k))) <= pow(2, k) - floor(pow(1.5, k)) - 2){
        std::cout << "Solution at k = " << k << ".\n";
        return returnID::success;
    } else {
        std::cout << "Error: Precision exceeded at k = " << k << ".\n";
        return returnID::precisionExceeded;
    }
}

I am using the Boost multiprecision library cpp_dec_float, which works for large integers and decimals. The data type needs to be able to work with integers, because the solution for k needs to be a positive integer. The data type needs to work with decimals because (3/2)^k (equivalently 1.5^k) returns a decimal.

In the code I have commented out the cmath library, because it appears to be included in boost/multiprecision/cpp_dec_float.

In the for-loop, I use <= to be equivalent to the pseudocode !>.

After the for-loop, I re-check if it is a solution because currently if the precision is exceeded, it breaks the for-loop. The if-else checks if it is has either exceeded precision or is an actual solution.

The precision in this example code is 1000 (line 5), but this is changed manually as I search for larger and larger numbers that may be a solution.

I am trying to squeeze every ounce of speed out of this code, so any optimizations that make it quicker will be of great help!

I am running this code on Ubuntu 16.04, and I compile it using g++ with the -Ofast flag for the highest possible optimization during compilation.

Thanks!

\$\endgroup\$
  • 3
    \$\begingroup\$ The wikipedia article says "there can only be a finite number of such k", not that there exist a finite number of k. Therefore I would think that it is likely for no such k to exist at all. Additionally, according to this wikipedia page, it is proven that if k exists, it must be > 471,600,000. So you should start from there instead of 6. \$\endgroup\$ – JS1 Feb 26 '17 at 0:34
  • \$\begingroup\$ You may consider openmp/mpi to parallel the computation. \$\endgroup\$ – cqdjyy01234 Feb 26 '17 at 3:01
  • \$\begingroup\$ @JS1 It is conjectured, but not proven, that no k exist. While I understand that in practical use I would start from k≈471600000, I set k=6 for simplicity, which I thought would result in the best answers regarding my code. \$\endgroup\$ – esote Feb 26 '17 at 7:16
5
\$\begingroup\$

A first step in optimizing would be to avoid computing the same values multiple times.

Secondly, I would drop the floating point arithmetic altogether. You have integer bases with integer exponents, so use integers. \$(\frac{3}{2})^k\$ = \$\frac{3^k}{2^k}\$ and applying floor also results in an integer.

I'm not familiar with the problem at hand, but the mention that none are known leads me to think that the values might be quite higher than 1000, otherwise a solution would have been trivial to find.

\$\endgroup\$
  • \$\begingroup\$ Yes, indeed it is quite higher than 1000. So far, with the code that I have in my question, I have reached 17073 with no solution after two hours of computation (likely because 3^17073 is such a frightfully large number with over 8000 digits). This is with 3000 decimal places as well! \$\endgroup\$ – esote Feb 25 '17 at 23:10
  • 1
    \$\begingroup\$ After improving my code with your suggestions in mind, it runs far quicker! I simply defined two variables, inside of the for loop, to be equal to 3^k and 2^k, and supplemented them in the equality check. Now, instead of taking hours it just took twenty seconds to reach the same point as I said in my previous comment! \$\endgroup\$ – esote Feb 25 '17 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.