Super-d numbers: Difference between revisions
Added C# version, C++ alternative GMPless version
m (→Procedural: Whoops) |
(Added C# version, C++ alternative GMPless version) |
||
Line 26:
:* '''[http://mathworld.wolfram.com/Super-dNumber.html Wolfram MathWorld - Super-d Number]'''
:* '''[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}}==
Line 180 ⟶ 341:
17546133 32613656 93568867 107225764 109255734 113315082 121251742 175461330 180917907 182557181
</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}}==
| |||