121 lines
4.4 KiB
C#
121 lines
4.4 KiB
C#
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);
|
|
}
|
|
}
|