source code
/* The Computer Language Benchmarks Game
* https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
*
* contributed by Basit Ayantunde
*/
#include <cinttypes>
#include <iostream>
#include "gmp.h"
struct Mpz {
Mpz() noexcept { __gmpz_init_set_ui(&mpz_, 0); }
~Mpz() noexcept { __gmpz_clear(&mpz_); }
explicit Mpz(ulong value) noexcept { __gmpz_init_set_ui(&mpz_, value); }
void set_value(ulong value) noexcept { __gmpz_init_set_ui(&mpz_, value); }
// *this = a * b
void mul(Mpz const& a, ulong b) noexcept { __gmpz_mul_ui(&mpz_, &a.mpz_, b); }
// *this *= a
void mul(ulong b) noexcept { __gmpz_mul_ui(&mpz_, &mpz_, b); }
// *this -= a * b
void submul(Mpz const& a, ulong b) noexcept {
__gmpz_submul_ui(&mpz_, &a.mpz_, b);
}
// *this = a + b
void add(Mpz const& a, Mpz const& b) noexcept {
__gmpz_add(&mpz_, &a.mpz_, &b.mpz_);
}
// *this += a
void add(Mpz const& a) noexcept { __gmpz_add(&mpz_, &mpz_, &a.mpz_); }
// *this += a
void add(ulong a) noexcept { __gmpz_add_ui(&mpz_, &mpz_, a); }
// *this += a * b
void addmul(Mpz const& a, ulong b) noexcept {
__gmpz_addmul_ui(&mpz_, &a.mpz_, b);
}
// *this = a / b
void tdiv_q(Mpz const& a, Mpz const& b) noexcept {
__gmpz_tdiv_q(&mpz_, &a.mpz_, &b.mpz_);
}
ulong as_ui() const noexcept { return __gmpz_get_ui(&mpz_); }
bool operator>(Mpz const& other) const noexcept {
return mpz_cmp(&mpz_, &other.mpz_) > 0;
}
private:
__mpz_struct mpz_;
};
struct Context {
Mpz tmp1, tmp2;
};
class LFT {
public:
Mpz q;
Mpz r;
Mpz t;
ulong k;
public:
LFT() noexcept : q(1), r(0), t(1), k(0) {}
void next() noexcept {
++k;
r.addmul(q, 2);
r.mul(2 * k + 1);
t.mul(2 * k + 1);
q.mul(k);
}
ulong extract(Context& ctx, ulong x) const noexcept { // NOLINT
ctx.tmp1.mul(q, x);
ctx.tmp1.add(r);
ctx.tmp2.tdiv_q(ctx.tmp1, t);
return ctx.tmp2.as_ui();
}
void produce(ulong n) noexcept {
q.mul(10);
r.submul(t, n);
r.mul(10);
}
};
int main(int, char** argv) {
std::ios_base::sync_with_stdio(false);
size_t const total_digits = std::atol(argv[1]);
auto context = Context();
LFT lft;
size_t n_digits = 0;
while (n_digits < total_digits) {
size_t i = 0;
while (i < 10 && n_digits < total_digits) {
lft.next();
if (lft.q > lft.r) continue;
auto digit = lft.extract(context, 3);
if (digit == lft.extract(context, 4)) {
std::cout << digit;
lft.produce(digit);
++i;
++n_digits;
}
}
// Pad digits with extra spaces if total_digits was not a
// multiple of 10.
for (; i < 10; ++i) std::cout << ' ';
std::cout << "\t:" << n_digits << '\n';
}
}
notes, command-line, and program output
NOTES:
64-bit Ubuntu quad core
g++ (Ubuntu 14.2.0-4ubuntu2) 14.2.0
Tue, 22 Oct 2024 20:29:06 GMT
MAKE:
/usr/bin/g++ -c -pipe -O3 -fomit-frame-pointer -march=ivybridge -std=c++14 pidigits.gpp-5.c++ -o pidigits.gpp-5.c++.o && \
/usr/bin/g++ pidigits.gpp-5.c++.o -o pidigits.gpp-5.gpp_run -lgmp
rm pidigits.gpp-5.c++
3.57s to complete and log all make actions
COMMAND LINE:
./pidigits.gpp-5.gpp_run 10000
(TRUNCATED) PROGRAM OUTPUT:
3141592653 :10
5897932384 :20
6264338327 :30
9502884197 :40
1693993751 :50
0582097494 :60
4592307816 :70
4062862089 :80
9862803482 :90
5342117067 :100
9821480865 :110
1328230664 :120
7093844609 :130
5505822317 :140
2535940812 :150
8481117450 :160
2841027019 :170
3852110555 :180
9644622948 :190
9549303819 :200
6442881097 :210
5665933446 :220
1284756482 :230
3378678316 :240
5271201909 :250
1456485669 :260
2346034861 :270
0454326648 :280
2133936072 :290
6024914127 :300
3724587006 :310
6063155881 :320
7488152092 :330
0962829254 :340
0917153643 :350
6789259036 :360
0011330530 :370
5488204665 :380
2138414695 :390
1941511609 :400
4330572703 :410
6575959195 :420
3092186117 :430
3819326117 :440
9310511854 :450
8074462379 :460
9627495673 :470
5188575272 :480
4891227938 :490
1830119491 :500
2983367336 :510
2440656643 :520
0860213949 :530
4639522473 :540
7190702179 :550
8609437027 :560
7053921717 :570
6293176752 :580
3846748184 :590
6766940513 :600
2000568127 :610
1452635608 :620
2778577134 :630
2757789609 :640
1736371787 :650
2146844090 :660
1224953430 :670
1465495853 :680
7105079227 :690
9689258923 :700
5420199561 :710
1212902196 :720
0864034418 :730
1598136297 :740
7477130996 :750
0518707211 :760
3499999983 :770
7297804995 :780
1059731732 :790
8160963185 :800
9502445945 :810
5346908302 :820
6425223082 :830
5334468503 :840
5261931188 :850
1710100031 :860
3783875288 :870
6587533208 :880
3814206171 :890
7766914730 :900
3598253490 :910
4287554687 :920
3115956286 :930
3882353787 :940
5937519577 :950
8185778053 :960
2171226806 :970
6130019278 :980
7661119590 :990
9216420198 :1000
9380952572 :1010
0106548586 :1020
3278865936 :1030
1533818279 :1040
6823030195 :1050
2035301852 :1060
9689957736 :1070
2259941389 :1080
1249721775 :1090
2834791315 :1100
1557485724 :1110
2454150695 :1120
9508295331 :1130
1686172785 :1140
5889075098 :1150
3817546374 :1160
6493931925 :1170
5060400927 :1180
7016711390 :1190
0984882401 :1200
2858361603 :1210
5637076601 :1220
0471018194 :1230
2955596198 :1240
9467678374 :1250
4944825537 :1260
9774726847 :1270
1040475346 :1280
4620804668 :1290
4259069491 :1300
2933136770 :1310
2898915210 :1320
4752162056 :1330
9660240580 :1340
3815019351 :1350
1253382430 :1360
0355876402 :1370
4749647326 :1380
3914199272 :1390
6042699227 :1400
9678235478 :1410
1636009341 :1420
7216412199 :1430
2458631503 :1440
0286182974 :1450
5557067498 :1460
3850549458 :1470
8586926995 :1480
6909272107 :1490
9750930295 :1500
5321165344 :1510
9872027559 :1520
6023648066 :1530
5499119881 :1540
8347977535 :1550
6636980742 :1560
6542527862 :1570
5518184175 :1580
7467289097 :1590
7772793800 :1600
0816470600 :1610
1614524919 :1620
2173217214 :1630
7723501414 :1640
4197356854 :1650
8161361157 :1660
3525521334 :1670
7574184946 :1680
8438523323 :1690
9073941433 :1700
3454776241 :1710
6862518983 :1720
5694855620 :1730
9921922218 :1740
4272550254 :1750
2568876717 :1760
9049460165 :1770
3466804988 :1780
6272327917 :1790
8608578438 :1800
3827967976 :1810
6814541009 :1820
5388378636 :1830
0950680064 :1840
2251252051 :1850
1739298489 :1860
6084128488 :1870
6269456042 :1880
4196528502 :1890
2210661186 :1900
3067442786 :1910
2203919494 :1920
5047123713 :1930
7869609563 :1940
6437191728 :1950
7467764657 :1960
5739624138 :1970
9086583264 :1980
5995813390 :1990
4780275900 :2000
9946576407 :2010
8951269468 :2020
3983525957 :2030
0982582262 :2040
0522489407 :2050
7267194782 :2060
6848260147 :2070
6990902640 :2080
1363944374 :2090
5530506820 :2100
3496252451 :2110
7493996514 :2120
3142980919 :2130
0659250937 :2140
2216964615 :2150
1570985838 :2160
7410597885 :2170
9597729754 :2180
9893016175 :2190
3928468138 :2200
2686838689 :2210
4277415599 :2220
1855925245 :2230
9539594310 :2240
4997252468 :2250
0845987273 :2260
6446958486 :2270
5383673622 :2280
2626099124 :2290
6080512438 :2300
8439045124 :2310
4136549762 :2320
7807977156 :2330
9143599770 :2340
0129616089 :2350
4416948685 :2360
5584840635 :2370
3422072225 :2380
8284886481 :2390
5845602850 :2400
6016842739 :2410
4522674676 :2420
7889525213 :2430
8522549954 :2440
6667278239 :2450
8645659611 :2460
6354886230 :2470
5774564980 :2480
3559363456 :2490
8174324112 :2500
5150760694 :2510
7945109659 :2520
6094025228 :2530
8797108931 :2540
4566913686 :2550
7228748940 :2560
5601015033 :2570
0861792868 :2580
0920874760 :2590
9178249385 :2600
8900971490 :2610
9675985261 :2620
3655497818 :2630
9312978482 :2640
1682998948 :2650
7226588048 :2660
5756401427 :2670
0477555132 :2680
3796414515 :2690
2374623436 :2700
4542858444 :2710
7952658678 :2720
2105114135 :2730
4735739523 :2740
1134271661 :2750
0213596953 :2760
6231442952 :2770
4849371871 :2780
1014576540 :2790
3590279934 :2800
4037420073 :2810
1057853906 :2820
2198387447 :2830
8084784896 :2840
8332144571 :2850
3868751943 :2860
5064302184 :2870
5319104848 :2880
1005370614 :2890
6806749192 :2900
7819119793 :2910
9952061419 :2920
6634287544 :2930
4064374512 :2940
3718192179 :2950
9983910159 :2960
1956181467 :2970
5142691239 :2980
7489409071 :2990
8649423196 :3000
1567945208 :3010
0951465502 :3020
2523160388 :3030
1930142093 :3040
7621378559 :3050
5663893778 :3060
7083039069 :3070
7920773467 :3080
2218256259 :3090
9661501421 :3100
5030680384 :3110
4773454920 :3120
2605414665 :3130
9252014974 :3140
4285073251 :3150
8666002132 :3160
4340881907 :3170
1048633173 :3180
4649651453 :3190
9057962685 :3200
6100550810 :3210
6658796998 :3220
1635747363 :3230
8405257145 :3240
9102897064 :3250
1401109712 :3260
0628043903 :3270
9759515677 :3280
1577004203 :3290
3786993600 :3300
7230558763 :3310
1763594218 :3320
7312514712 :3330
0532928191 :3340
8261861258 :3350
6732157919 :3360
8414848829 :3370
1644706095 :3380
7527069572 :3390
2091756711 :3400
6722910981 :3410
6909152801 :3420
7350671274 :3430
8583222871 :3440
8352093539 :3450
6572512108 :3460
3579151369 :3470
8820914442 :3480
1006751033 :3490
4671103141 :3500
2671113699 :3510
0865851639 :3520
8315019701 :3530
6515116851 :3540
7143765761 :3550
8351556508 :3560
8490998985 :3570
9982387345 :3580
5283316355 :3590
0764791853 :3600
5893226185 :3610
4896321329 :3620
3308985706 :3630
4204675259 :3640
0709154814 :3650
1654985946 :3660
1637180270 :3670
9819943099 :3680
2448895757 :3690
1282890592 :3700
3233260972 :3710
9971208443 :3720
3573265489 :3730
3823911932 :3740
5974636673 :3750
0583604142 :3760
8138830320 :3770
3824903758 :3780
9852437441 :3790
7029132765 :3800
6180937734 :3810
4403070746 :3820
9211201913 :3830
0203303801 :3840
9762110110 :3850
0449293215 :3860
1608424448 :3870
5963766983 :3880
8952286847 :3890
8312355265 :3900
8213144957 :3910
6857262433 :3920
4418930396 :3930
8642624341 :3940
0773226978 :3950
0280731891 :3960
5441101044 :3970
6823252716 :3980
2010526522 :3990
7211166039 :4000
6665573092 :4010
5471105578 :4020
5376346682 :4030
0653109896 :4040
5269186205 :4050
6476931257 :4060
0586356620 :4070
1855810072 :4080
9360659876 :4090
4861179104 :4100
5334885034 :4110
6113657686 :4120
7532494416 :4130
6803962657 :4140
9787718556 :4150
0845529654 :4160
1266540853 :4170
0614344431 :4180
8586769751 :4190
4566140680 :4200
0700237877 :4210
6591344017 :4220
1274947042 :4230
0562230538 :4240
9945613140 :4250
7112700040 :4260
7854733269 :4270
9390814546 :4280
6464588079 :4290
7270826683 :4300
0634328587 :4310
8569830523 :4320
5808933065 :4330
7574067954 :4340
5716377525 :4350
4202114955 :4360
7615814002 :4370
5012622859 :4380
4130216471 :4390
5509792592 :4400
3099079654 :4410
7376125517 :4420
6567513575 :4430
1782966645 :4440
4779174501 :4450
1299614890 :4460
3046399471 :4470
3296210734 :4480
0437518957 :4490
3596145890 :4500
1938971311 :4510
1790429782 :4520
8564750320 :4530
3198691514 :4540
0287080859 :4550
9048010941 :4560
2147221317 :4570
9476477726 :4580
2241425485 :4590
4540332157 :4600
1853061422 :4610
8813758504 :4620
3063321751 :4630
8297986622 :4640
3717215916 :4650
0771669254 :4660
7487389866 :4670
5494945011 :4680
4654062843 :4690
3663937900 :4700
3976926567 :4710
2146385306 :4720
7360965712 :4730
0918076383 :4740
2716641627 :4750
4888800786 :4760
9256029022 :4770
8472104031 :4780
7211860820 :4790
4190004229 :4800
6617119637 :4810
7921337575 :4820
1149595015 :4830
6604963186 :4840
2947265473 :4850
6425230817 :4860
7036751590 :4870
6735023507 :4880
2835405670 :4890
4038674351 :4900
3622224771 :4910
5891504953 :4920
0984448933 :4930
3096340878 :4940
0769325993 :4950
9780541934 :4960
1447377441 :4970
8426312986 :4980
0809988868 :4990
7413260472 :5000
1569516239 :5010
6586457302 :5020
1631598193 :5030
1951673538 :5040
1297416772 :5050
9478672422 :5060
9246543668 :5070
0098067692 :5080
8238280689 :5090
9640048243 :5100
5403701416 :5110
3149658979 :5120
4092432378 :5130
9690706977 :5140
9422362508 :5150
2216889573 :5160
8379862300 :5170
1593776471 :5180
6512289357 :5190
8601588161 :5200
7557829735 :5210
2334460428 :5220
1512627203 :5230
7343146531 :5240
9777741603 :5250
1990665541 :5260
8763979293 :5270
3441952154 :5280
1341899485 :5290
4447345673 :5300
8316249934 :5310
1913181480 :5320
9277771038 :5330
6387734317 :5340
7207545654 :5350
5322077709 :5360
2120190516 :5370
6096280490 :5380
9263601975 :5390
9882816133 :5400
2316663652 :5410
8619326686 :5420
3360627356 :5430
7630354477 :5440
6280350450 :5450
7772355471 :5460
0585954870 :5470
2790814356 :5480
2401451718 :5490
0624643626 :5500
7945612753 :5510
1813407833 :5520
0336254232 :5530
7839449753 :5540
8243720583 :5550
5311477119 :5560
9260638133 :5570
4677687969 :5580
5970309833 :5590
9130771098 :5600
7040859133 :5610
7464144282 :5620
2772634659 :5630
4704745878 :5640
4778720192 :5650
7715280731 :5660
7679077071 :5670
5721344473 :5680
0605700733 :5690
4924369311 :5700
3835049316 :5710
3128404251 :5720
2192565179 :5730
8069411352 :5740
8013147013 :5750
0478164378 :5760
8518529092 :5770
8545201165 :5780
8393419656 :5790
2134914341 :5800
5956258658 :5810
6557055269 :5820
0496520985 :5830
8033850722 :5840
4264829397 :5850
2858478316 :5860
3057777560 :5870
6888764462 :5880
4824685792 :5890
6039535277 :5900
3480304802 :5910
9005876075 :5920
8251047470 :5930
9164396136 :5940
2676044925 :5950
6274204208 :5960
3208566119 :5970
0625454337 :5980
2131535958 :5990
4506877246 :6000
0290161876 :6010
6795240616 :6020
3425225771 :6030
9542916299 :6040
1930645537 :6050
7991403734 :6060
0432875262 :6070
8889639958 :6080
7947572917 :