patterncppMinor
Multithreaded search for solutions to an inequality
Viewed 0 times
searchsolutionsforinequalitymultithreaded
Problem
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
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
Let me know how I can improve my use of multithreading in this program.
```
#include
//#include (already included from cpp_dec_float.hpp)
#include
#include
typedef boost::multiprecision::number> 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 futureThreeK = std::async(std::launch::async, calcThreeK, k);
std::future 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";
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
//#include (already included from cpp_dec_float.hpp)
#include
#include
typedef boost::multiprecision::number> 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 futureThreeK = std::async(std::launch::async, calcThreeK, k);
std::future 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";
Solution
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
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\$.Context
StackExchange Code Review Q#156669, answer score: 4
Revisions (0)
No revisions yet.