From 99c4b2d9980dd14e8c43ffbf00660047335ada4b Mon Sep 17 00:00:00 2001 From: Adrien Hopkins 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/mtc.go | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'factors/mtc.go') 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