Super-d numbers: Difference between revisions
Content added Content deleted
m (→Procedural: Whoops) |
(Added C# version, C++ alternative GMPless version) |
||
Line 26: | Line 26: | ||
:* '''[http://mathworld.wolfram.com/Super-dNumber.html Wolfram MathWorld - Super-d Number]''' |
:* '''[http://mathworld.wolfram.com/Super-dNumber.html Wolfram MathWorld - Super-d Number]''' |
||
:* '''[http://oeis.org/A014569 OEIS: A014569 - Super-3 Numbers]''' |
:* '''[http://oeis.org/A014569 OEIS: A014569 - Super-3 Numbers]''' |
||
=={{header|C sharp|C#}}== |
|||
===With / Without BigInteger=== |
|||
{{libheader|System.Numerics}} |
|||
Done three ways, two with BigIntegers, and one with a UIint64 structure. More details on the "Mostly addition" method on the discussion page. |
|||
<lang csharp>using System; |
|||
using System.Collections.Generic; |
|||
using BI = System.Numerics.BigInteger; |
|||
using lbi = System.Collections.Generic.List<System.Numerics.BigInteger[]>; |
|||
using static System.Console; |
|||
class Program { |
|||
// provides 320 bits (90 decimal digits) |
|||
struct LI { public UInt64 lo, ml, mh, hi, tp; } |
|||
const UInt64 Lm = 1_000_000_000_000_000_000UL; |
|||
const string Fm = "D18"; |
|||
static void inc(ref LI d, LI s) { // d += s |
|||
d.lo += s.lo; while (d.lo >= Lm) { d.ml++; d.lo -= Lm; } |
|||
d.ml += s.ml; while (d.ml >= Lm) { d.mh++; d.ml -= Lm; } |
|||
d.mh += s.mh; while (d.mh >= Lm) { d.hi++; d.mh -= Lm; } |
|||
d.hi += s.hi; while (d.hi >= Lm) { d.tp++; d.hi -= Lm; } |
|||
d.tp += s.tp; |
|||
} |
|||
static void set(ref LI d, UInt64 s) { // d = s |
|||
d.lo = s; d.ml = d.mh = d.hi = d.tp = 0; |
|||
} |
|||
const int ls = 10; |
|||
static lbi co = new lbi { new BI[] { 0 } }; // for BigInteger addition |
|||
static List<LI[]> Co = new List<LI[]> { new LI[1] }; // for UInt64 addition |
|||
static Int64 ipow(Int64 bas, Int64 exp) { // Math.Pow() |
|||
Int64 res = 1; while (exp != 0) { |
|||
if ((exp & 1) != 0) res *= bas; exp >>= 1; bas *= bas; |
|||
} |
|||
return res; |
|||
} |
|||
// finishes up, shows performance value |
|||
static void fin() { WriteLine("{0}s", (DateTime.Now - st).TotalSeconds.ToString().Substring(0, 5)); } |
|||
static void funM(int d) { // straightforward BigInteger method, medium performance |
|||
string s = new string(d.ToString()[0], d); Write("{0}: ", d); |
|||
for (int i = 0, c = 0; c < ls; i++) |
|||
if ((BI.Pow((BI)i, d) * d).ToString().Contains(s)) |
|||
Write("{0} ", i, ++c); |
|||
fin(); |
|||
} |
|||
static void funS(int d) { // BigInteger "mostly adding" method, low performance |
|||
BI[] m = co[d]; |
|||
string s = new string(d.ToString()[0], d); Write("{0}: ", d); |
|||
for (int i = 0, c = 0; c < ls; i++) { |
|||
if ((d * m[0]).ToString().Contains(s)) |
|||
Write("{0} ", i, ++c); |
|||
for (int j = d, k = d - 1; j > 0; j = k--) m[k] += m[j]; |
|||
} |
|||
fin(); |
|||
} |
|||
static string scale(uint s, ref LI x) { // performs a small multiply and returns a string value |
|||
ulong Lo = x.lo * s, Ml = x.ml * s, Mh = x.mh * s, Hi = x.hi * s, Tp = x.tp * s; |
|||
while (Lo >= Lm) { Lo -= Lm; Ml++; } |
|||
while (Ml >= Lm) { Ml -= Lm; Mh++; } |
|||
while (Mh >= Lm) { Mh -= Lm; Hi++; } |
|||
while (Hi >= Lm) { Hi -= Lm; Tp++; } |
|||
if (Tp > 0) return Tp.ToString() + Hi.ToString(Fm) + Mh.ToString(Fm) + Ml.ToString(Fm) + Lo.ToString(Fm); |
|||
if (Hi > 0) return Hi.ToString() + Mh.ToString(Fm) + Ml.ToString(Fm) + Lo.ToString(Fm); |
|||
if (Mh > 0) return Mh.ToString() + Ml.ToString(Fm) + Lo.ToString(Fm); |
|||
if (Ml > 0) return Ml.ToString() + Lo.ToString(Fm); |
|||
return Lo.ToString(); |
|||
} |
|||
static void funF(int d) { // structure of UInt64 method, high performance |
|||
LI[] m = Co[d]; |
|||
string s = new string(d.ToString()[0], d); Write("{0}: ", d); |
|||
for (int i = d, c = 0; c < ls; i++) { |
|||
if (scale((uint)d, ref m[0]).Contains(s)) |
|||
Write("{0} ", i, ++c); |
|||
for (int j = d, k = d - 1; j > 0; j = k--) |
|||
inc(ref m[k], m[j]); |
|||
} |
|||
fin(); |
|||
} |
|||
static void init() { // initializes co and Co |
|||
for (int v = 1; v < 10; v++) { |
|||
BI[] res = new BI[v + 1]; |
|||
long[] f = new long[v + 1], l = new long[v + 1]; |
|||
for (int j = 0; j <= v; j++) { |
|||
if (j == v) { |
|||
LI[] t = new LI[v + 1]; |
|||
for (int y = 0; y <= v; y++) set(ref t[y], (UInt64)f[y]); |
|||
Co.Add(t); |
|||
} |
|||
res[j] = f[j]; |
|||
l[0] = f[0]; f[0] = ipow(j + 1, v); |
|||
for (int a = 0, b = 1; b <= v; a = b++) { |
|||
l[b] = f[b]; f[b] = f[a] - l[a]; |
|||
} |
|||
} |
|||
for (int z = res.Length - 2; z > 0; z -= 2) res[z] *= -1; |
|||
co.Add(res); |
|||
} |
|||
} |
|||
static DateTime st; |
|||
static void doOne(string title, int top, Action<int> func) { |
|||
WriteLine('\n' + title); st = DateTime.Now; |
|||
for (int i = 2; i <= top; i++) func(i); |
|||
} |
|||
static void Main(string[] args) |
|||
{ |
|||
init(); const int top = 9; |
|||
doOne("BigInteger mostly addition:", top, funS); |
|||
doOne("BigInteger.Pow():", top, funM); |
|||
doOne("UInt64 structure mostly addition:", top, funF); |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre>BigInteger mostly addition: |
|||
2: 19 31 69 81 105 106 107 119 127 131 0.007s |
|||
3: 261 462 471 481 558 753 1036 1046 1471 1645 0.008s |
|||
4: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 0.014s |
|||
5: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 0.033s |
|||
6: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 0.584s |
|||
7: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 2.891s |
|||
8: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 20.47s |
|||
9: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 226.7s |
|||
BigInteger.Pow(): |
|||
2: 19 31 69 81 105 106 107 119 127 131 0.002s |
|||
3: 261 462 471 481 558 753 1036 1046 1471 1645 0.003s |
|||
4: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 0.008s |
|||
5: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 0.025s |
|||
6: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 0.450s |
|||
7: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 2.092s |
|||
8: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 14.80s |
|||
9: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 170.8s |
|||
UInt64 structure mostly addition: |
|||
2: 19 31 69 81 105 106 107 119 127 131 0.004s |
|||
3: 261 462 471 481 558 753 1036 1046 1471 1645 0.004s |
|||
4: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 0.006s |
|||
5: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 0.013s |
|||
6: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 0.188s |
|||
7: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 1.153s |
|||
8: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 9.783s |
|||
9: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 121.3s</pre> |
|||
Results from a core i7-7700 @ 3.6Ghz. The UInt64 structure method is quicker, but it's likely because the BigInteger.ToString() implementation in '''C#''' is so sluggish. I've ported this (UInt64 structure) algorithm to '''C++''', however it's quite a bit slower than the '''C++ GMP''' version. |
|||
Regarding the term "mostly addition", for this task there is some multiplication by a small integer (2 thru 9 in ''scale()''), but the powers of "n" are calculated by only addition. The initial tables are calculated with multiplication and a power function (''ipow()''). |
|||
=={{header|C}}== |
=={{header|C}}== |
||
Line 180: | Line 341: | ||
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 |
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 |
||
</pre> |
</pre> |
||
===Alternative ''not'' using GMP=== |
|||
{{trans|C#}} |
|||
<lang cpp>#include <cstdio> |
|||
#include <sstream> |
|||
#include <chrono> |
|||
using namespace std; |
|||
using namespace chrono; |
|||
struct LI { uint64_t a, b, c, d, e; }; const uint64_t Lm = 1e18; |
|||
auto st = steady_clock::now(); LI k[10][10]; |
|||
string padZ(uint64_t x, int n = 18) { string r = to_string(x); |
|||
return string(max((int)(n - r.length()), 0), '0') + r; } |
|||
uint64_t ipow(uint64_t b, uint64_t e) { uint64_t r = 1; |
|||
while (e) { if (e & 1) r *= b; e >>= 1; b *= b; } return r; } |
|||
uint64_t fa(uint64_t x) { // factorial |
|||
uint64_t r = 1; while (x > 1) r *= x--; return r; } |
|||
void set(LI &d, uint64_t s) { // d = s |
|||
d.a = s; d.b = d.c = d.d = d.e = 0; } |
|||
void inc(LI &d, LI s) { // d += s |
|||
d.a += s.a; while (d.a >= Lm) { d.a -= Lm; d.b++; } |
|||
d.b += s.b; while (d.b >= Lm) { d.b -= Lm; d.c++; } |
|||
d.c += s.c; while (d.c >= Lm) { d.c -= Lm; d.d++; } |
|||
d.d += s.d; while (d.d >= Lm) { d.d -= Lm; d.e++; } |
|||
d.e += s.e; |
|||
} |
|||
string scale(uint32_t s, LI &x) { // multiplies x by s, converts to string |
|||
uint64_t A = x.a * s, B = x.b * s, C = x.c * s, D = x.d * s, E = x.e * s; |
|||
while (A >= Lm) { A -= Lm; B++; } |
|||
while (B >= Lm) { B -= Lm; C++; } |
|||
while (C >= Lm) { C -= Lm; D++; } |
|||
while (D >= Lm) { D -= Lm; E++; } |
|||
if (E > 0) return to_string(E) + padZ(D) + padZ(C) + padZ(B) + padZ(A); |
|||
if (D > 0) return to_string(D) + padZ(C) + padZ(B) + padZ(A); |
|||
if (C > 0) return to_string(C) + padZ(B) + padZ(A); |
|||
if (B > 0) return to_string(B) + padZ(A); |
|||
return to_string(A); |
|||
} |
|||
void fun(int d) { |
|||
auto m = k[d]; string s = string(d, '0' + d); printf("%d: ", d); |
|||
for (int i = d, c = 0; c < 10; i++) { |
|||
if (scale((uint32_t)d, m[0]).find(s) != string::npos) { |
|||
printf("%d ", i); ++c; } |
|||
for (int j = d, k = d - 1; j > 0; j = k--) inc(m[k], m[j]); |
|||
} printf("%ss\n", to_string(duration<double>(steady_clock::now() - st).count()).substr(0,5).c_str()); |
|||
} |
|||
static void init() { |
|||
for (int v = 1; v < 10; v++) { |
|||
uint64_t f[v + 1], l[v + 1]; |
|||
for (int j = 0; j <= v; j++) { |
|||
if (j == v) for (int y = 0; y <= v; y++) |
|||
set(k[v][y], v != y ? (uint64_t)f[y] : fa(v)); |
|||
l[0] = f[0]; f[0] = ipow(j + 1, v); |
|||
for (int a = 0, b = 1; b <= v; a = b++) { |
|||
l[b] = f[b]; f[b] = f[a] - l[a]; |
|||
} |
|||
} |
|||
} |
|||
} |
|||
int main() { |
|||
init(); |
|||
for (int i = 2; i <= 9; i++) fun(i); |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre>2: 19 31 69 81 105 106 107 119 127 131 0.002s |
|||
3: 261 462 471 481 558 753 1036 1046 1471 1645 0.004s |
|||
4: 1168 4972 7423 7752 8431 10267 11317 11487 11549 11680 0.009s |
|||
5: 4602 5517 7539 12955 14555 20137 20379 26629 32767 35689 0.026s |
|||
6: 27257 272570 302693 323576 364509 502785 513675 537771 676657 678146 0.399s |
|||
7: 140997 490996 1184321 1259609 1409970 1783166 1886654 1977538 2457756 2714763 2.523s |
|||
8: 185423 641519 1551728 1854230 6415190 12043464 12147605 15517280 16561735 18542300 22.32s |
|||
9: 17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181 275.4s</pre> |
|||
Slower than '''GMP''' on the core i7-7700 @ 3.6Ghz, over twice as slow. This one is 275 seconds, vs. 102 seconds for '''GMP'''. |
|||
=={{header|D}}== |
=={{header|D}}== |