From 99c4b2d9980dd14e8c43ffbf00660047335ada4b Mon Sep 17 00:00:00 2001
From: Adrien Hopkins <adrien.p.hopkins@gmail.com>
Date: Fri, 25 Aug 2023 08:55:30 -0500
Subject: Limit MTC calculation to < 2^32

This ensures the output can fit into a uint64.  Also, calculating it at
this stage is slow, and not calculating it can make the program nearly
instant even for very large numbers!
---
 factors/factors_test.go | 6 +++---
 factors/mtc.go          | 8 ++++----
 2 files changed, 7 insertions(+), 7 deletions(-)

(limited to 'factors')

diff --git a/factors/factors_test.go b/factors/factors_test.go
index 12d4384..33727c0 100644
--- a/factors/factors_test.go
+++ b/factors/factors_test.go
@@ -100,7 +100,7 @@ func TestBasicRank(t *testing.T) {
 	tableTest(t, BasicRank, basicRankCases, stdEquals, "BasicRank")
 }
 
-var gcdCases = map[struct{ a, b uint }]uint{
+var gcdCases = map[struct{ a, b uint64 }]uint64{
 	{0, 0}: 0, {1, 1}: 1,
 	{6, 10}: 2, {10, 6}: 2,
 	{12, 20}: 4, {20, 12}: 4,
@@ -109,7 +109,7 @@ var gcdCases = map[struct{ a, b uint }]uint{
 }
 
 // a version of gcd() for testing purposes
-func gcdTest(c struct{ a, b uint }) uint {
+func gcdTest(c struct{ a, b uint64 }) uint64 {
 	return gcd(c.a, c.b)
 }
 
@@ -117,7 +117,7 @@ func TestGCD(t *testing.T) {
 	tableTest(t, gcdTest, gcdCases, stdEquals, "gcd")
 }
 
-var mtcCases = map[uint]uint{
+var mtcCases = map[uint64]uint64{
 	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,
diff --git a/factors/mtc.go b/factors/mtc.go
index d008ca3..522a35c 100644
--- a/factors/mtc.go
+++ b/factors/mtc.go
@@ -3,15 +3,15 @@ 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++ {
+func MTC(n uint64) uint64 {
+	mtc := uint64(0)
+	for i := uint64(2); i <= n - 2; i++ {
 		mtc += n / gcd(i, n)
 	}
 	return mtc
 }
 
-func gcd(a, b uint) uint {
+func gcd(a, b uint64) uint64 {
 	for b > 0 {
 		a, b = b, a % b
 	}
-- 
cgit v1.2.3