3
\$\begingroup\$

This question is related to my previous question on the brute-force search for a solution to an unsolved mathematical inequality:

$$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$$

The following code, tested on Ubuntu 16.04, compiles with no warnings or errors using the flags -Wall -std=c++14 -pthread -Ofast using the g++ compiler. I'm using -Ofast because I am trying to squeeze every ounce of performance out of this code (more info here).

I am not 100% sure if this is the proper, fastest, implementation of multithreading. Since I'm new to multithreading, I used this SO question, this page, and this page for learning how to multithread.

For questions about other parts of the code, I explain it way more on my previous question (like why I have a completely separate if-else check).

Let me know how I can improve my use of multithreading in this program.

#include <boost/multiprecision/cpp_dec_float.hpp>
//#include <cmath> (already included from cpp_dec_float.hpp)
#include <iostream>
#include <future>

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

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

arbFloat calcThreeK(const arbFloat & k){
    return pow(3, k);
}

arbFloat calcTwoK(const arbFloat & k){
    return pow(2, k);
}

int main(){
    arbFloat k, threeK, twoK;
    bool isSolution = false;

    for(k = 6; !isSolution; ++k){
        std::future<arbFloat> futureThreeK = std::async(std::launch::async, calcThreeK, k);
        std::future<arbFloat> futureTwoK = std::async(std::launch::async, calcTwoK, k);

        threeK = futureThreeK.get();
        twoK = futureTwoK.get();

        isSolution = threeK - twoK * floor(threeK / twoK) > twoK - floor(threeK / twoK) - 2;
    }

    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;
    }
}
\$\endgroup\$
4
\$\begingroup\$

You are asynchronously calculating intermediate results that are not worth parallelizing. Instead of calculating \$2^k\$ and \$3^k\$ sequentially, you do those calculations in parallel. But then you have to wait for both of them to complete before proceeding. I would expect that the overhead of setting up the async calls would negate any performance benefit.

Suppose you had a dozen friends helping you. Would you ask one of them to go off and calculate \$2^6\$, the second friend to calculate \$3^6\$, and report the results back to you so that you can check whether 6 is a solution? No, that would be crazy. You would be better off asking the first friend to check whether 6 is a solution, the second friend to check 7, the third friend to try 8, etc. Then each of them has a chance to do some substantial work independently instead of waiting for each other's results.

Moreover, calculating \$3^k\$ would be a trivial multiplication if you already knew \$3^{k-1}\$. You should be able to avoid calling pow() altogether if you are trying increasing \$k\$.

\$\endgroup\$
  • \$\begingroup\$ Good point on the sequential calls to 3^k! \$\endgroup\$ – user1118321 Mar 2 '17 at 6:23
  • \$\begingroup\$ I guess multithreading really wasn't really worth it in this use-case. I compared the run times for my program with and without multithreading and it was about the same (I suppose the time saved by multithreading was canceled out by the time it takes to create those threads / switch tasks from threads). However, I was able to vastly improve my program by taking your advice not to use pow(). By just doing *= my program runs much faster. SO question on pow() vs *=. \$\endgroup\$ – esote Mar 2 '17 at 21:32
3
\$\begingroup\$

Naming

I would suggest improving your naming a bit. Names like calcTwoK() and calcThreeK() don't really tell reader what they do. I suggest renaming them to powTwoK() or twoToTheK(), as calcTwoK() sounds like it multiplies k by 2.

And in fact, it's odd that you have a function that does nothing but call a single other function. It seems like any call sites could just call the pow(2, k) themselves.

Threading

While what you've written seems like it will work correctly, those functions are far too small to be calling in a thread. They don't do nearly enough work to make it worth your time to put them in a separate thread. The overhead of switching tasks to the other thread will likely far outweigh the amount of time it takes to do the calculation in question.

Performance

One small way to improve performance would be to calculate values and reuse them when possible. For example, in the final if statement you use pow(2, k) and floor(pow(1.5, k)) twice. Rather than calculate each twice, you should calculate them once and use the results of the calculations twice.

\$\endgroup\$

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.