145 lines
4.4 KiB
D
145 lines
4.4 KiB
D
import std.stdio, std.bigint, std.range, std.algorithm;
|
|
|
|
struct BalancedTernary {
|
|
// Represented as a list of 0, 1 or -1s,
|
|
// with least significant digit first.
|
|
enum Dig : byte { N=-1, Z=0, P=+1 } // Digit.
|
|
const Dig[] digits;
|
|
|
|
// This could also be a BalancedTernary template argument.
|
|
static immutable string dig2str = "-0+";
|
|
|
|
immutable static Dig[dchar] str2dig; // = ['+': Dig.P, ...];
|
|
nothrow static this() {
|
|
str2dig = ['+': Dig.P, '-': Dig.N, '0': Dig.Z];
|
|
}
|
|
|
|
immutable pure nothrow static Dig[2][] table =
|
|
[[Dig.Z, Dig.N], [Dig.P, Dig.N], [Dig.N, Dig.Z],
|
|
[Dig.Z, Dig.Z], [Dig.P, Dig.Z], [Dig.N, Dig.P],
|
|
[Dig.Z, Dig.P]];
|
|
|
|
this(in string inp) const pure {
|
|
this.digits = inp.retro.map!(c => str2dig[c]).array;
|
|
}
|
|
|
|
this(in long inp) const pure nothrow {
|
|
this.digits = _bint2ternary(inp.BigInt);
|
|
}
|
|
|
|
this(in BigInt inp) const pure nothrow {
|
|
this.digits = _bint2ternary(inp);
|
|
}
|
|
|
|
this(in BalancedTernary inp) const pure nothrow {
|
|
// No need to dup, they are virtually immutable.
|
|
this.digits = inp.digits;
|
|
}
|
|
|
|
private this(in Dig[] inp) pure nothrow {
|
|
this.digits = inp;
|
|
}
|
|
|
|
static Dig[] _bint2ternary(in BigInt n) pure nothrow {
|
|
static py_div(T1, T2)(in T1 a, in T2 b) pure nothrow {
|
|
if (a < 0) {
|
|
return (b < 0) ?
|
|
-a / -b :
|
|
-(-a / b) - (-a % b != 0 ? 1 : 0);
|
|
} else {
|
|
return (b < 0) ?
|
|
-(a / -b) - (a % -b != 0 ? 1 : 0) :
|
|
a / b;
|
|
}
|
|
}
|
|
|
|
if (n == 0) return [];
|
|
// This final switch in D v.2.064 is fake, not enforced.
|
|
final switch (((n % 3) + 3) % 3) { // (n % 3) is the remainder.
|
|
case 0: return Dig.Z ~ _bint2ternary(py_div(n, 3));
|
|
case 1: return Dig.P ~ _bint2ternary(py_div(n, 3));
|
|
case 2: return Dig.N ~ _bint2ternary(py_div(n + 1, 3));
|
|
}
|
|
}
|
|
|
|
@property BigInt toBint() const pure nothrow {
|
|
return reduce!((y, x) => x + 3 * y)(0.BigInt, digits.retro);
|
|
}
|
|
|
|
string toString() const pure nothrow {
|
|
if (digits.empty) return "0";
|
|
return digits.retro.map!(d => dig2str[d + 1]).array;
|
|
}
|
|
|
|
static const(Dig)[] neg_(in Dig[] digs) pure nothrow {
|
|
return digs.map!(a => -a).array;
|
|
}
|
|
|
|
BalancedTernary opUnary(string op:"-")() const pure nothrow {
|
|
return BalancedTernary(neg_(this.digits));
|
|
}
|
|
|
|
static const(Dig)[] add_(in Dig[] a, in Dig[] b, in Dig c=Dig.Z)
|
|
pure nothrow {
|
|
const a_or_b = a.length ? a : b;
|
|
if (a.empty || b.empty) {
|
|
if (c == Dig.Z)
|
|
return a_or_b;
|
|
else
|
|
return BalancedTernary.add_([c], a_or_b);
|
|
} else {
|
|
// (const d, c) = table[...];
|
|
const dc = table[3 + (a.length ? a[0] : 0) +
|
|
(b.length ? b[0] : 0) + c];
|
|
const res = add_(a[1 .. $], b[1 .. $], dc[1]);
|
|
// Trim leading zeros.
|
|
if (res.length || dc[0] != Dig.Z)
|
|
return [dc[0]] ~ res;
|
|
else
|
|
return res;
|
|
}
|
|
}
|
|
|
|
BalancedTernary opBinary(string op:"+")(in BalancedTernary b)
|
|
const pure nothrow {
|
|
return BalancedTernary(add_(this.digits, b.digits));
|
|
}
|
|
|
|
BalancedTernary opBinary(string op:"-")(in BalancedTernary b)
|
|
const pure nothrow {
|
|
return this + (-b);
|
|
}
|
|
|
|
static const(Dig)[] mul_(in Dig[] a, in Dig[] b) pure nothrow {
|
|
if (a.empty || b.empty) {
|
|
return [];
|
|
} else {
|
|
const y = Dig.Z ~ mul_(a[1 .. $], b);
|
|
final switch (a[0]) {
|
|
case Dig.N: return add_(neg_(b), y);
|
|
case Dig.Z: return add_([], y);
|
|
case Dig.P: return add_(b, y);
|
|
}
|
|
}
|
|
}
|
|
|
|
BalancedTernary opBinary(string op:"*")(in BalancedTernary b)
|
|
const pure nothrow {
|
|
return BalancedTernary(mul_(this.digits, b.digits));
|
|
}
|
|
}
|
|
|
|
void main() {
|
|
immutable a = BalancedTernary("+-0++0+");
|
|
writeln("a: ", a.toBint, ' ', a);
|
|
|
|
immutable b = BalancedTernary(-436);
|
|
writeln("b: ", b.toBint, ' ', b);
|
|
|
|
immutable c = BalancedTernary("+-++-");
|
|
writeln("c: ", c.toBint, ' ', c);
|
|
|
|
const /*immutable*/ r = a * (b - c);
|
|
writeln("a * (b - c): ", r.toBint, ' ', r);
|
|
}
|