diff options
| -rw-r--r-- | factors/factors_test.go | 6 | ||||
| -rw-r--r-- | factors/mtc.go | 8 | ||||
| -rw-r--r-- | radix_info.go | 7 |
3 files changed, 13 insertions, 8 deletions
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 } diff --git a/radix_info.go b/radix_info.go index f3aecce..daf62df 100644 --- a/radix_info.go +++ b/radix_info.go @@ -24,8 +24,13 @@ func main() { fmt.Println("2345 Rank:", factors.BasicRank(n)) if n < 1<<32 { printTypeMessage(factors.Type(uint32(n))) + // MTC(n) < n^2, so n < 2^32 ensures it fits in a uint64 + fmt.Println("Multiplication Table Complexity:", + factors.MTC(uint64(n))) + } else { + fmt.Printf("Multiplication Table Complexity ≤ %.4g\n", + float32(n) * float32(n - 2)) } - fmt.Println("Multiplication Table Complexity:", factors.MTC(n)) fmt.Printf("Natural Logarithm: %.2f\n", math.Log(float64(n))) } else { fmt.Println("Argument must be an integer above 1.") |