diff options
| -rw-r--r-- | factor_info.go | 31 | ||||
| -rw-r--r-- | factors/regular_complexity.go | 16 | ||||
| -rw-r--r-- | factors/table_test.go | 45 |
3 files changed, 91 insertions, 1 deletions
diff --git a/factor_info.go b/factor_info.go index 637bde2..638e333 100644 --- a/factor_info.go +++ b/factor_info.go @@ -63,6 +63,11 @@ type factorInfo struct { // reciprocoal has and what patterns are in its row of the multiplication // table. DigitMap []factors.DigitType + // The complexity of each prime factor. + // The amount of numbers to memorize for testing p^e is around RC(p)^e. + // The memorization for the product of prime powers + // is less than the memorization of worst part of the product. + PrimeRegularComplexities map[uint]float64 } const ( @@ -108,10 +113,12 @@ func getFactorInfo(a args) *factorInfo { totativeCount := factors.Totient(radix) totativeRatio := float64(totativeCount) / float64(radix) + var prcs = factors.PrimeRegularComplexities(radix) + return &factorInfo{radix, factors.PrimeFactorize(radix), r_factors, factors.Score(radix), totativeCount, totativeRatio, totativeDigits, factors.BasicRank(radix), factors.Type(radix), - mtc_ptr, math.Log2(float64(radix)), digitMap} + mtc_ptr, math.Log2(float64(radix)), digitMap, prcs} } func (fi *factorInfo) writeTo(w io.Writer) { @@ -141,6 +148,9 @@ func (fi *factorInfo) writeTo(w io.Writer) { fmt.Fprintf(w, "Base-2 Logarithm: %.3f\n", fi.Log2) fmt.Fprintf(w, "Number Length: %.4f×Decimal\n", 1/math.Log10(float64(fi.Radix))) + fmt.Fprint(w, "Prime Regular Complexities: ") + writePRCMap(w, fi.PrimeRegularComplexities) + fmt.Fprintln(w) if len(fi.DigitMap) > 0 { writeDigitMap(w, fi.DigitMap) } @@ -193,3 +203,22 @@ func typeAbbrev(t factors.CompositenessType) string { panic("Should not be possible to get here.") } } + +func writePRCMap(w io.Writer, prcs map[uint]float64) { + var first = true + var primeFactors = make([]uint, 0, len(prcs)) + for p := range prcs { + primeFactors = append(primeFactors, p) + } + sort.Slice(primeFactors, func(i, j int) bool { + return primeFactors[i] < primeFactors[j] + }) + + for _, p := range primeFactors { + if !first { + fmt.Fprintf(w, ", ") + } + first = false + fmt.Fprintf(w, "%d: %.4f", p, prcs[p]) + } +} diff --git a/factors/regular_complexity.go b/factors/regular_complexity.go new file mode 100644 index 0000000..763bcd7 --- /dev/null +++ b/factors/regular_complexity.go @@ -0,0 +1,16 @@ +package factors + +import ( + "math" +) + +func PrimeRegularComplexities(radix uint) map[uint]float64 { + var factorization = PrimeFactorize(radix) + var complexities = make(map[uint]float64, len(factorization.exponents)) + for p, e := range factorization.exponents { + var part = float64(uintpow(p, e)) + var complexity = math.Pow(float64(radix)/part, 1/float64(e)) + complexities[p] = complexity + } + return complexities +} diff --git a/factors/table_test.go b/factors/table_test.go index c7eeb24..1ff795c 100644 --- a/factors/table_test.go +++ b/factors/table_test.go @@ -18,6 +18,7 @@ package factors import ( "fmt" + "math" "testing" ) @@ -402,6 +403,30 @@ func TestSplit(t *testing.T) { tableTest(t, splitTest, splitCases, stdEquals[uintPair], "Split") } +var primeRegularComplexityCases = map[uint]map[uint]float64{ + 2: {2: 1}, + 3: {3: 1}, + 4: {2: 1}, + 6: {2: 3, 3: 2}, + 10: {2: 5, 5: 2}, + 12: {2: math.Sqrt(3), 3: 4}, + 20: {2: math.Sqrt(5), 5: 4}, + 24: {2: math.Cbrt(3), 3: 8}, + 36: {2: 3, 3: 2}, + 40: {2: math.Cbrt(5), 5: 8}, + 60: {2: math.Sqrt(15), 3: 20, 5: 12}, + 120: {2: math.Cbrt(15), 3: 40, 5: 24}, + 360: {2: math.Cbrt(45), 3: math.Sqrt(40), 5: 72}, +} + +func TestPrimeRegularComplexity(t *testing.T) { + // Use approxEquals instead of == due to differences between + // math.Sqrt/math.Cbrt and math.Pow. + // The different digits are never shown to the user, so no big deal. + tableTest(t, PrimeRegularComplexities, primeRegularComplexityCases, + mapApproxEquals[uint], "PrimeRegularComplexities") +} + // to be used as the equal paramater for tableTest func stdEquals[T comparable](a, b T) bool { return a == b } @@ -421,6 +446,26 @@ func mapEquals[K, V comparable](a, b map[K]V) bool { return true } +func approxEquals(a, b, epsilon float64) bool { + return math.Abs(a-b) <= epsilon*math.Max(math.Abs(a), math.Abs(b)) +} + +func mapApproxEquals[K comparable](a, b map[K]float64) bool { + for k, av := range a { + bv, ok := b[k] + if !ok || !approxEquals(av, bv, 1e-15) { + return false + } + } + for k, bv := range b { + av, ok := a[k] + if !ok || !approxEquals(av, bv, 1e-15) { + return false + } + } + return true +} + func setEquals[E comparable](a, b []E) bool { // use maps to simulate sets // aSet[a] == true means set contains a, false means not |