Add MTC to output

(MTC = Multiplication Table Complexity)

2 files changed, 49 insertions, 0 deletions

diff --git a/factors/factors_test.go b/factors/factors_test.go
index 77c5f4a..db6e098 100644
--- a/factors/factors_test.go
+++ b/factors/factors_test.go
@@ -100,6 +100,36 @@ func TestBasicRank(t *testing.T) {
 	tableTest(t, BasicRank, basicRankCases, stdEquals[string], "BasicRank")
 }
 
+var gcdCases = map[struct{ a, b uint }]uint{
+	{0, 0}: 0, {1, 1}: 1,
+	{6, 10}: 2, {10, 6}: 2,
+	{12, 20}: 4, {20, 12}: 4,
+	{20, 55}: 5, {55, 20}: 5,
+	{60, 120}: 60, {120, 60}: 60,
+}
+
+// a version of gcd() for testing purposes
+func gcdTest(c struct{ a, b uint }) uint {
+	return gcd(c.a, c.b)
+}
+
+func TestGCD(t *testing.T) {
+	tableTest(t, gcdTest, gcdCases, stdEquals[uint], "gcd")
+}
+
+var mtcCases = map[uint]uint{
+	2: 0, 3: 0, 4: 2, 5: 10, 6: 8,
+	7: 28, 8: 26, 9: 42, 10: 42, 11: 88, 12: 52,
+	13: 130, 14: 100, 15: 116, 16: 138, 18: 146,
+	20: 190, 24: 252, 28: 416, 30: 380, 32: 618, 36: 598,
+	48: 1100, 60: 1496, 64: 2602, 90: 3662, 120: 6080,
+	210: 18542, 360: 54362, 840: 270122, 2520: 2363528, 5040: 9409112,
+}
+
+func TestMTC(t *testing.T) {
+	tableTest(t, MTC, mtcCases, stdEquals[uint], "MTC")
+}
+
 // to be used as the equal paramater for tableTest
 func stdEquals[T comparable](a, b T) bool { return a == b }
 
diff --git a/factors/mtc.go b/factors/mtc.go
new file mode 100644
index 0000000..d008ca3
--- /dev/null
+++ b/factors/mtc.go
@@ -0,0 +1,19 @@
+package factors
+
+// MTC returns the multiplication table complexity of a radix n.
+// This is an estimate of how difficult it is to learn a radix's
+// multiplication table.
+func MTC(n uint) uint {
+	mtc := uint(0)
+	for i := uint(2); i <= n - 2; i++ {
+		mtc += n / gcd(i, n)
+	}
+	return mtc
+}
+
+func gcd(a, b uint) uint {
+	for b > 0 {
+		a, b = b, a % b
+	}
+	return a
+}