Rare numbers: Difference between revisions
→{{header|C++}}
Line 576:
=={{header|C++}}==
===Calculate L and H independently===
<lang cpp>
// Rare Numbers : Nigel Galloway - December 20th., 2019;
// Nigel Galloway/Enter your username - January 4th., 2021 (see discussion page.
#include <functional>
#include <bitset>
#include <cmath>
#include <chrono>▼
using namespace std;
using Z2 = optional<long long>; using Z1 = function<Z2()>;▼
▲using Z2 = optional<long long>;
using VU = vector<unsigned long long>;▼
// powers of 10 array
constexpr auto pow10 = [] { array <long long, 19> n {1}; for (int j{0}, i{1}; i < 19; j = i++) n[i] = n[j] * 10; return n; } ();
Line 606 ⟶ 603:
const double fac = 3.94;
const int mbs = (int)sqrt(fac * pow10[9]), mbt = (int)sqrt(fac * fac * pow10[9]) >> 3;
const bitset<100000>bs {[]{bitset<100000>n{false}; for(int g{3};g<mbs;
// reports one block of digits▼
void doOne(int n, nLH L, nLH H) {▼
VS lines = dump(n, L.even, H.even); lines += dump(n, L.odd , H.odd); sort(lines.begin(), lines.end());▼
duration<double> tet = (tmp = steady_clock::now()) - st; int ls = lines.size();▼
if (ls-- > 0)▼
for (int i = 0; i <= ls; ++i)▼
printf("%3d %s%s", ++c, lines[i].c_str(), i == ls ? "" : "\n");▼
else printf("%s", string(47, ' ').c_str());▼
printf(" %2d: %s %s\n", n, dFmt(tmp - st0, 8).c_str(), dFmt(tet, 8).c_str()); st0 = tmp;▼
}▼
constexpr array<const int, 7>li{1,3,0,0,1,1,1},lin{0,-7,0,0,-8,-3,-9},lig{0,9,0,0,8,7,9},lil{0,2,0,0,2,10,2};
const nLH makeL(const int n){
Line 626 ⟶ 613:
return q ? nLH(g,w,0) : nLH(g,{0},0);
}
const bitset<100000>bt {[]{bitset<100000>n{false}; for(int g{11};g<mbt;++g) n[(g*g)%100000]=true; return n;}()};
constexpr array<const int, 17>lu{0,0,0,0,2,0,4,0,0,0,1,4,0,0,0,1,1},lun{0,0,0,0,0,0,1,0,0,0,9,1,0,0,0,1,0},lug{0,0,0,0,18,0,17,0,0,0,9,17,0,0,0,11,18},lul{0,0,0,0,2,0,2,0,0,0,0,2,0,0,0,10,2};
const nLH makeH(const int n){
Line 632 ⟶ 620:
if (n & 1){l=pow10[n>>1]<<1; g=fG(g,0,9,0,l,acc+=l);}
if(q){long long g0{4}, g1{0}, g2{0}, g3{0}, g4{0},l3{pow10[n-5]}; while (g0<17){const long long g{g4*10000+g3*1000+g2*100+g1*10+g0};
if (
if (g4<18) ++g4; else{g4=0; if(g3<18) ++g3; else{g3=0; if(g2<18) ++g2; else{g2=0; if(g1<lug[g0]) g1+=lul[g0]; else{g0+=lu[g0];g1=lun[g0];}}}}}}
return q ? nLH(g,w,0) : nLH(g,{0},pow10[n-1]<<2);
}
▲#include <chrono>
▲using namespace chrono; using VU = vector<unsigned long long>; using VS = vector<string>;
template <typename T> // concatenates vectors
vector<T>& operator +=(vector<T>& v, const vector<T>& w) { v.insert(v.end(), w.begin(), w.end()); return v; }
int
auto st
// formats elasped time
string dFmt(duration<double> et, int digs) {
string res
if (dt > 60.0) { int m = (int)(dt / 60.0); dt -= m * 60.0; res = to_string(m) + "m"; }
res += to_string(dt); return res.substr(0, digs - 1) + 's';
Line 655 ⟶ 644:
char buf[99]; sprintf(buf, "%20llu %11lu %10lu", z, (long long)sqrt(h), (long long)sqrt(l));
res.push_back(buf); } } return res;
▲}
▲// reports one block of digits
▲void doOne(int n, nLH L, nLH H) {
▲ VS lines = dump(n, L.even, H.even); lines += dump(n, L.odd , H.odd); sort(lines.begin(), lines.end());
▲ duration<double> tet = (tmp = steady_clock::now()) - st; int ls = lines.size();
▲ if (ls-- > 0)
▲ printf("%3d %s%s", ++c, lines[i].c_str(), i == ls ? "" : "\n");
▲ else printf("%s", string(47, ' ').c_str());
▲ printf(" %2d: %s %s\n", n, dFmt(tmp - st0, 8).c_str(), dFmt(tet, 8).c_str()); st0 = tmp;
}
void Rare(int n) { doOne(n, makeL(n), makeH(n)); }
int main(int argc, char *argv[]) {
int max
printf("%4s %19s %11s %10s %5s %11s %9s\n", "nth", "forward", "rt.sum", "rt.diff", "digs", "block.et", "total.et");
for (int nd
}
</lang>
Line 667 ⟶ 666:
<pre>
nth forward rt.sum rt.diff digs block.et total.et
1 65 11 3 2: 0.
3: 0.
4: 0.00001s 0.
5: 0.
2 621770 836 738 6: 0.
7: 0.
8: 0.
3 281089082 23708 330 9: 0.
4 2022652202 63602 300
5 2042832002 63602 6360 10: 0.
11: 0.
6 868591084757 1275175 333333
7 872546974178 1320616 32670
8 872568754178 1320616 33330 12: 0.
9 6979302951885 3586209 1047717 13: 0.
10 20313693904202 6368252 269730
11 20313839704202 6368252 270270
Line 688 ⟶ 687:
14 20333875702202 6368252 336330
15 40313893704200 6368252 6330336
16 40351893720200 6368252 6336336 14: 0.
17 200142385731002 20006998 69300
18 204238494066002 20122102 1891560
Line 697 ⟶ 696:
23 403058392434500 20211202 19940514
24 441054594034340 22011022 19940514
25 816984566129618 40421606 250800 15: 0.
26 2078311262161202 64030648 7529850
27 2133786945766212 65272218 2666730
Line 712 ⟶ 711:
38 8191376864400818 127950856 3366330
39 8650327689541457 127246955 33299667
40 8650349867341457 127246955 33300333 16: 2.
41 22542040692914522 212329862 333300
42 67725910561765640 269040196 251135808
43 86965750494756968 417050956 33000 17: 13.
44 225342456863243522 671330638 297000
45 225342458663243522 671330638 303000
Line 735 ⟶ 734:
61 865721270017296468 1315452006 32071170
62 871975098681469178 1320582934 3303300
63 898907259301737498 1339270086 64576740 18:
64 2042401829204402402 2021001202 18915600
65 2060303819041450202 2020110202 199405140
Line 747 ⟶ 746:
73 8197906905009010818 4046976144 133408770
74 8200756128308135597 4019461925 495417087
75 8320411466598809138 4079154376 36366330 19:
</pre>
===20+ digits===
| |||