From 7fa8cf9666cd3427dd078bb4a5fdb9fa30c94b09 Mon Sep 17 00:00:00 2001 From: Adrien Hopkins Date: Thu, 7 Sep 2023 11:38:32 -0500 Subject: Calculate type of all radices without -l MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit factors.Type now supports all numbers; I have used lookup arrays instead of determining whether a number is SAN or not. There are only 117 elements to store, and this makes the algorithm Θ(1), so it's an improvement. Also, I have changed the size of some integer values to correspond to this change - they now indicate the size of numbers they can accept. The only outputs that are hidden for large radices are: - The digit map, which goes up to 36 because I don't have any more digits beyond that point - The multiplication table complexity, which is estimated above 2^16 (for performance), and can optionally be extended to 2^32 (above this, the output could overflow a uint64). --- 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 655124c..024391e 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 uint64) uint64 { +func MTC(n uint32) uint64 { mtc := uint64(0) - for i := uint64(2); i <= n-2; i++ { - mtc += n / gcd(i, n) + for i := uint32(2); i <= n-2; i++ { + mtc += uint64(n / gcd(i, n)) } return mtc } -func gcd(a, b uint64) uint64 { +func gcd(a, b uint32) uint32 { for b > 0 { a, b = b, a%b } -- cgit v1.2.3