blob: db3e67023d85ba0159a1d5fb9dba3c77a9f10ea1 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
/* This script is part of radix_info.
Copyright (C) 2023 Adrien Hopkins
This program is free software: you can redistribute it and/or modify
it under the terms of version 3 of the GNU General Public License
as published by the Free Software Foundation.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
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.
//
// The MTC is a sum of each digit's row complexity,
// which is the length of the pattern of the product's last digit
// (equal to digit / gcd(digit, radix)).
// Digits 1 and radix - 1 are excluded because they have simpler patterns
// than the other digits.
//
// uint32 is used as the input type and uint64 as the output to prevent
// integer overflow (and because the MTC algorithm is slow).
//
// The MTC of 0 and 1 are both zero.
func MTC(radix uint32) uint64 {
mtc := uint64(0)
for digit := uint32(2); digit <= radix-2; digit++ {
mtc += uint64(radix / gcd(digit, radix))
}
return mtc
}
func gcd(a, b uint32) uint32 {
for b > 0 {
a, b = b, a%b
}
return a
}
|
