Skip to content

Instantly share code, notes, and snippets.

@PierceLBrooks

PierceLBrooks/the-speed-of-gcd.cpp

Last active February 19, 2024 14:17
Show Gist options
  • Save PierceLBrooks/eb1f5ac88ceecf4ade6024830c66e8ec to your computer and use it in GitHub Desktop.
Save PierceLBrooks/eb1f5ac88ceecf4ade6024830c66e8ec to your computer and use it in GitHub Desktop.
Download ZIP
Raw
the-speed-of-gcd.cpp
// https://hbfs.wordpress.com/2013/12/10/the-speed-of-gcd/
/*
g++ ./the-speed-of-gcd.cpp -static-libstdc++ -std=c++11 -pthread -O3 -o ./the-speed-of-gcd
./the-speed-of-gcd
1000 3.3428e-05 5.77788e-05 3.3541e-05 6.12842e-05 3.4811e-05
1000 1.90322e-05 3.82361e-05 1.8979e-05 4.174e-05 1.99548e-05
1000 1.83879e-05 3.77061e-05 1.85562e-05 4.1613e-05 1.97229e-05
1000 1.8762e-05 3.7532e-05 1.84731e-05 4.12971e-05 1.89309e-05
1000 1.88318e-05 3.774e-05 1.82791e-05 4.15129e-05 1.88972e-05
1000 1.85271e-05 3.7906e-05 1.85271e-05 4.14521e-05 1.93062e-05
1000 1.8447e-05 3.75959e-05 1.84568e-05 4.1281e-05 1.93689e-05
1000 1.87212e-05 3.73049e-05 1.84668e-05 4.11321e-05 1.9301e-05
1000 1.87581e-05 3.75081e-05 1.87761e-05 4.10339e-05 1.89219e-05
1000 1.8363e-05 3.7865e-05 1.875e-05 4.13711e-05 1.88579e-05
1000 1.84189e-05 3.81631e-05 1.81179e-05 4.12639e-05 1.96421e-05
1000 1.876e-05 3.75688e-05 1.85659e-05 4.07261e-05 1.96689e-05
1000 1.87449e-05 3.75698e-05 1.79709e-05 4.1333e-05 1.9634e-05
1000 1.87041e-05 3.752e-05 1.7967e-05 4.12832e-05 1.96919e-05
1000 1.84939e-05 3.74231e-05 1.85469e-05 4.11292e-05 1.96841e-05
1000 1.85928e-05 3.76479e-05 1.84719e-05 4.14321e-05 1.93789e-05
1000 1.87881e-05 3.73218e-05 1.82649e-05 4.13499e-05 1.9657e-05
1000 1.8751e-05 3.8218e-05 1.85391e-05 4.05e-05 1.95869e-05
1000 1.8728e-05 3.78208e-05 1.85371e-05 4.05439e-05 1.96389e-05
1000 1.89409e-05 3.82451e-05 1.77629e-05 4.1553e-05 1.9626e-05
1000 1.8738e-05 3.76589e-05 1.86069e-05 4.14639e-05 1.96509e-05
1000 1.8666e-05 3.75371e-05 1.8186e-05 4.15261e-05 1.9512e-05
1000 1.85452e-05 3.75291e-05 1.85662e-05 4.1551e-05 1.9446e-05
1000 1.84348e-05 3.77048e-05 1.8552e-05 4.1552e-05 1.96091e-05
1000 1.87888e-05 3.77349e-05 1.8498e-05 4.0906e-05 1.98359e-05
1000 1.87168e-05 3.7708e-05 1.849e-05 4.06799e-05 1.9752e-05
1000 1.87212e-05 3.82361e-05 1.84661e-05 4.06611e-05 1.98391e-05
1000 1.85359e-05 3.8084e-05 1.86921e-05 4.148e-05 1.89871e-05
1000 1.8761e-05 3.77141e-05 1.88311e-05 4.12942e-05 1.903e-05
1000 1.91221e-05 3.70281e-05 1.87771e-05 4.16001e-05 1.93201e-05
1000 1.84819e-05 3.75659e-05 1.87971e-05 4.17351e-05 1.9136e-05
1000 1.87549e-05 3.7762e-05 1.76521e-05 4.1354e-05 1.98271e-05
1000 1.8729e-05 3.77488e-05 1.82759e-05 4.1231e-05 1.93889e-05
1000 1.8751e-05 3.77148e-05 1.8519e-05 4.04719e-05 1.95999e-05
1000 1.8769e-05 3.77061e-05 1.85469e-05 4.05061e-05 1.96001e-05
1000 1.87458e-05 3.8219e-05 1.8594e-05 4.0553e-05 1.96541e-05
1000 1.87671e-05 3.772e-05 1.8533e-05 4.05139e-05 1.9626e-05
1000 1.87769e-05 3.8217e-05 1.87429e-05 4.1071e-05 1.87869e-05
1000 1.879e-05 3.8219e-05 1.85e-05 4.04971e-05 1.96318e-05
1000 1.8718e-05 3.8199e-05 1.87561e-05 4.02231e-05 1.96641e-05
1000 1.874e-05 3.82158e-05 1.84651e-05 4.15491e-05 1.8782e-05
1000 1.8689e-05 3.77041e-05 1.87791e-05 4.02529e-05 1.96392e-05
1000 1.8772e-05 3.7707e-05 1.85908e-05 4.105e-05 1.90959e-05
1000 1.8491e-05 3.79109e-05 1.8531e-05 4.13621e-05 1.96201e-05
1000 1.84312e-05 3.7416e-05 1.88411e-05 4.13389e-05 1.9083e-05
1000 1.83921e-05 3.74331e-05 1.85449e-05 4.10969e-05 1.9479e-05
1000 1.87781e-05 3.82839e-05 1.8002e-05 4.10381e-05 1.92559e-05
1000 1.79319e-05 3.774e-05 1.8719e-05 4.10979e-05 1.9623e-05
1000 1.84639e-05 3.75898e-05 1.85061e-05 4.1126e-05 1.95991e-05
1000 1.87439e-05 3.82312e-05 1.85271e-05 4.1469e-05 1.87869e-05
10000 0.00267911 0.00617881 0.00255532 0.00560676 0.00272441
10000 0.00267859 0.00616925 0.00262028 0.00554915 0.00274745
10000 0.00262353 0.00618804 0.0026217 0.00560122 0.00271482
10000 0.00268593 0.00617864 0.00267306 0.0056134 0.00264383
10000 0.00263372 0.00613604 0.0026884 0.00560966 0.00273471
10000 0.0026424 0.00613852 0.00266043 0.00558916 0.00273091
10000 0.00264829 0.00614599 0.0026714 0.00560919 0.00273106
10000 0.00265781 0.0061327 0.00268283 0.00558834 0.00272268
10000 0.00263224 0.00616742 0.0026876 0.00558007 0.00270862
10000 0.00259861 0.00618008 0.00264038 0.0056255 0.00271995
10000 0.00267586 0.00614387 0.00266357 0.00557207 0.00272092
10000 0.00264837 0.00616271 0.00259429 0.00559788 0.00274481
10000 0.00268689 0.00612862 0.00268621 0.0055727 0.00265983
10000 0.00259011 0.00614417 0.00268547 0.00559396 0.00273241
10000 0.00267232 0.00615742 0.00268281 0.00558308 0.00261994
10000 0.00257729 0.00617773 0.00268069 0.00560571 0.00272485
10000 0.00269906 0.00615764 0.00252826 0.00560543 0.00274697
10000 0.00266586 0.00615899 0.00255876 0.00559777 0.00274732
10000 0.00267083 0.00603524 0.00267941 0.00563073 0.00274804
10000 0.00269719 0.00616253 0.0026871 0.00557893 0.00263536
10000 0.00255101 0.00614336 0.00268543 0.00560313 0.0027454
10000 0.00268462 0.00617101 0.00267527 0.00559461 0.00268974
10000 0.00267613 0.00618151 0.0026254 0.00559696 0.00271662
10000 0.00265968 0.00614209 0.00266682 0.0055757 0.00274176
10000 0.00266184 0.00616857 0.00267023 0.00555938 0.00274775
10000 0.00265526 0.00615079 0.0026633 0.00559561 0.00268916
10000 0.00268634 0.00616053 0.00268022 0.0054919 0.00272096
10000 0.00263656 0.00614982 0.00265027 0.00560034 0.00271308
10000 0.00268016 0.006175 0.00264988 0.00560657 0.00269333
10000 0.00266312 0.00616814 0.0026291 0.00557206 0.00273156
10000 0.00266585 0.00610862 0.00266647 0.00558625 0.00271214
10000 0.00266066 0.00614823 0.00266016 0.00556282 0.00270534
10000 0.00265544 0.00613732 0.00264619 0.00559566 0.00271085
10000 0.00265176 0.00614112 0.00264756 0.00561435 0.00270929
10000 0.00267748 0.00607689 0.00266556 0.00559713 0.00274394
10000 0.00266066 0.00616807 0.00267086 0.00558519 0.00272228
10000 0.00264195 0.0061723 0.00267675 0.0055968 0.00270255
10000 0.00265906 0.00616262 0.00266334 0.00560267 0.00273154
10000 0.00266661 0.00615014 0.0026756 0.00560882 0.00271231
10000 0.00265973 0.00616788 0.00257697 0.00561523 0.0027451
10000 0.0026504 0.0061715 0.00262991 0.00560164 0.00273701
10000 0.0026848 0.00616929 0.00268959 0.00555404 0.00268295
10000 0.0026795 0.00615373 0.00265341 0.00560511 0.00272751
10000 0.00268296 0.00611425 0.00262615 0.00561701 0.00273145
10000 0.00270396 0.00618247 0.00266035 0.00562172 0.00272422
10000 0.0026894 0.00616655 0.00265448 0.0055709 0.00272546
10000 0.00267776 0.00617377 0.00267975 0.00562662 0.00273206
10000 0.00269726 0.00617064 0.00270193 0.00561931 0.00276625
10000 0.00266295 0.00611677 0.00264985 0.00561364 0.00273971
10000 0.00265799 0.00613568 0.00268677 0.00560049 0.00273765
100000 0.354074 0.918058 0.354527 0.700769 0.358472
100000 0.35456 0.918145 0.355421 0.699525 0.358023
100000 0.354107 0.915349 0.353291 0.698681 0.357455
100000 0.354666 0.923444 0.354138 0.700923 0.358289
100000 0.358604 0.93633 0.358705 0.709338 0.363717
100000 0.362175 0.941163 0.36226 0.719202 0.367154
100000 0.361903 0.944724 0.361745 0.715894 0.366915
100000 0.363647 0.934674 0.363549 0.713448 0.368662
100000 0.355813 0.928988 0.355975 0.707335 0.36079
100000 0.489328 1.40901 0.489221 0.959084 0.496276
100000 0.371257 0.94865 0.371341 0.724675 0.376195
100000 0.355197 0.932918 0.355237 0.708895 0.359982
100000 0.357066 0.935795 0.356891 0.711053 0.361912
100000 0.356852 0.935077 0.356743 0.710953 0.361732
100000 0.355557 0.934662 0.35554 0.709826 0.36044
100000 0.356836 0.937388 0.356674 0.711958 0.361689
100000 0.356348 0.937371 0.356277 0.711404 0.361234
100000 0.358489 0.939673 0.358607 0.713628 0.363548
100000 0.357394 0.938464 0.357468 0.712392 0.362272
100000 0.357973 0.93948 0.357895 0.713352 0.362903
100000 0.427046 0.99187 0.427776 0.77454 0.431368
100000 0.506036 1.06951 0.505912 0.852996 0.51034
100000 0.354016 0.917879 0.354444 0.701224 0.358104
100000 0.354059 0.915862 0.353747 0.699816 0.357877
100000 0.354168 0.917134 0.355011 0.700153 0.356496
100000 0.354388 0.917665 0.354655 0.701302 0.357635
100000 0.354662 0.919267 0.355428 0.697707 0.357574
100000 0.35322 0.914539 0.357588 0.698914 0.359092
100000 0.354318 0.918893 0.354573 0.701744 0.354097
100000 0.354944 0.917618 0.352882 0.701769 0.355267
100000 0.350725 0.918546 0.353772 0.702003 0.358307
100000 0.353877 0.91598 0.35366 0.70068 0.358028
100000 0.355793 0.911874 0.355662 0.699799 0.358744
100000 0.354421 0.911306 0.357166 0.700526 0.357797
100000 0.355651 0.914887 0.353856 0.696971 0.359068
100000 0.356105 0.916102 0.354004 0.700826 0.356044
100000 0.355486 0.918324 0.35285 0.698061 0.358009
100000 0.354867 0.916239 0.354358 0.69903 0.35804
100000 0.352602 0.91661 0.354764 0.701151 0.357097
100000 0.353511 0.912433 0.357243 0.70046 0.357553
100000 0.354972 0.915913 0.355655 0.697808 0.356462
100000 0.356389 0.913894 0.353907 0.69926 0.35671
100000 0.355439 0.916149 0.353358 0.697319 0.358012
100000 0.355418 0.915541 0.350424 0.699631 0.358958
100000 0.352152 0.915686 0.354793 0.699823 0.358437
100000 0.354246 0.917268 0.355509 0.695059 0.358666
100000 0.355818 0.91213 0.352985 0.699782 0.360281
100000 0.351637 0.915627 0.35598 0.702248 0.356807
100000 0.356193 0.917326 0.350968 0.700926 0.358107
100000 0.354642 0.91453 0.356683 0.697932 0.3579
*/
#include <functional>
#include <iostream>
#include <iomanip>
#include <thread>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
typedef std::function<unsigned(unsigned, unsigned)> gcd;
unsigned gcd_iterative_sub(unsigned a, unsigned b)
{
if (a==0) return b;
if (b==0) return a;
while (a!=b)
if (a>b)
a-=b;
else
b-=a;
return a;
}
unsigned gcd_recursive(unsigned a, unsigned b)
{
if (b)
return gcd_recursive(b, a % b);
else
return a;
}
unsigned gcd_iterative_mod(unsigned a, unsigned b)
{
while (b)
{
unsigned t=b;
b=a % b;
a=t;
}
return a;
}
unsigned gcd_binary(unsigned a, unsigned b)
{
if (a == 0) return b;
if (b == 0) return a;
int shift=0;
while (!((a | b) & 1))
{
a >>= 1;
b >>= 1;
shift++;
}
while (!(a & 1)) a >>= 1;
do
{
while (!(b & 1)) b >>= 1;
if (a>b) std::swap(a,b);
b-=a;
} while (b);
// rescale
return a << shift;
}
unsigned gcd_binary_mod(unsigned a, unsigned b)
{
if (a == 0) return b;
if (b == 0) return a;
int shift=0;
while (!((a | b) & 1))
{
a >>= 1;
b >>= 1;
shift++;
}
return gcd_iterative_mod(a,b) << shift;
}
class tester
{
private:
gcd f;
unsigned range;
double elapsed;
public:
double get_elapsed() const { return elapsed; }
void run()
{
struct timeval t1, t2;
gettimeofday(&t1,0);
for (unsigned a=0;a<range;a++)
for (unsigned b=0;b<range;b++)
f(a,b);
gettimeofday(&t2,0);
elapsed=(t2.tv_sec * 1000.0 + t2.tv_usec / 1000.0) - (t1.tv_sec * 1000.0 + t1.tv_usec / 1000.0);
}
void set_range(unsigned _range) { range=_range; }
unsigned get_range() const { return range; }
tester(gcd _f, unsigned _range):
f(_f),
range(_range),
elapsed(0.0)
{};
};
int main(int argc, char **argv)
{
const size_t nb_algorithms=5;
std::thread **threads=new std::thread *[nb_algorithms];
tester *testers[nb_algorithms]=
{
new tester(gcd_recursive,0),
new tester(gcd_iterative_sub,0),
new tester(gcd_iterative_mod,0),
new tester(gcd_binary,0),
new tester(gcd_binary_mod,0)
};
for (unsigned range=1000;range<=100000;range*=10)
for (int rep=0;rep<50;rep++)
{
std::cout << std::setw(12) << range;
for (int i=0;i<nb_algorithms;i++)
{
testers[i]->set_range(range);
threads[i]=
// this only keeps a pointer to the function and its argument is
// this so it points to the already existing object, while
// creating a new thread with something like
//
// new std::thread( std::function<void()>(*testers[i]) );
//
// (assuming and operator()) would make a thread-private copy of
// the object
//
new std::thread( &tester::run, testers[i]);
}
for (int i=0;i<nb_algorithms;i++)
threads[i]->join();
for (int i=0;i<nb_algorithms;i++)
std::cout << std::setw(12) << testers[i]->get_elapsed()/1000000.0;
std::cout << std::endl;
for (int i=0;i<nb_algorithms;i++)
delete threads[i];
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment