Rare numbers: Difference between revisions
Content deleted Content added
→Version 1: Replaced with much faster version. |
→Version 2: Replaced with version which has relatively low memory requirement. |
||
| Line 363: | Line 363: | ||
===Version 2=== |
===Version 2=== |
||
To deal with the high memory overhead of the first version, this version delivers the Cartesian products 100 at a time rather than ''en masse''. Not surprisingly, this version is slower than the first and its now taking about 43 seconds to get to 15 digits. However, the pay-off is that 16 and 17 digit numbers can now be processed in a reasonable time without running out of memory. |
|||
This is based on Nigel Galloway's approach (see Talk page) of working from (n-r) and deducing the Rare numbers with various numbers of digits from there. |
|||
It is more than 500 times faster than Version 1, taking 1.3, 2.3, 28.5 and 42.1 seconds to process all 12, 13, 14 and 15 digit numbers respectively. However, it uses a lot of memory for the Cartesian products. |
|||
<lang go>package main |
<lang go>package main |
||
| Line 380: | Line 378: | ||
} |
} |
||
const |
const ( |
||
maxDigits = 17 |
|||
chanBufSize = 100 |
|||
) |
|||
func toInt64(digits []int8, reverse bool) int64 { |
func toInt64(digits []int8, reverse bool) int64 { |
||
| Line 397: | Line 398: | ||
func isSquare(n int64) bool { |
func isSquare(n int64) bool { |
||
if 0x202021202030213&(1<<(n&63)) != 0 { |
|||
root := int64(math.Sqrt(float64(n))) |
|||
root := int64(math.Sqrt(float64(n))) |
|||
return root*root == n |
|||
} |
|||
return false |
|||
} |
} |
||
// From the Cartesian product of two or more lists task - Extra credit 1. |
// From the Cartesian product of two or more lists task - Extra credit 1. |
||
// Changed to yield results 'chanBufSize' at a time rather than en masse. |
|||
func cp(a ...[]int8) [][]int8 { |
|||
func cp(ch chan<- []int8, a ...[]int8) { |
|||
c := 1 |
c := 1 |
||
for _, a := range a { |
for _, a := range a { |
||
| Line 408: | Line 413: | ||
} |
} |
||
if c == 0 { |
if c == 0 { |
||
close(ch) |
|||
return |
|||
} |
} |
||
p := make([][]int8, c) |
|||
b := make([]int8, c*len(a)) |
b := make([]int8, c*len(a)) |
||
n := make([]int8, len(a)) |
n := make([]int8, len(a)) |
||
s := 0 |
s := 0 |
||
for i := |
for i := 0; i < c; i++ { |
||
e := s + len(a) |
e := s + len(a) |
||
pi := b[s:e] |
pi := b[s:e] |
||
p[i] = pi |
|||
s = e |
|||
for j, n := range n { |
for j, n := range n { |
||
pi[j] = a[j][n] |
pi[j] = a[j][n] |
||
| Line 429: | Line 432: | ||
n[j] = 0 |
n[j] = 0 |
||
} |
} |
||
ch <- pi |
|||
s = e |
|||
} |
} |
||
close(ch) |
|||
} |
} |
||
func seq(from, to int8) []int8 { |
func seq(from, to, step int8) []int8 { |
||
var res []int8 |
var res []int8 |
||
for i := from; i <= to; i+ |
for i := from; i <= to; i += step { |
||
res = append(res, i) |
res = append(res, i) |
||
} |
} |
||
| Line 455: | Line 460: | ||
// terms of (n-r) expression for number of digits from 2 to maxDigits |
// terms of (n-r) expression for number of digits from 2 to maxDigits |
||
allTerms := make([][]term, maxDigits-1) |
allTerms := make([][]term, maxDigits-1) |
||
fmt.Println("Aggregate timings to process all numbers up to:") |
|||
for r := 2; r <= maxDigits; r++ { |
for r := 2; r <= maxDigits; r++ { |
||
var terms []term |
var terms []term |
||
| Line 466: | Line 472: | ||
allTerms[r-2] = terms |
allTerms[r-2] = terms |
||
} |
} |
||
// |
// map of first minus last digits for 'n' to pairs giving this value |
||
fml := map[int8][][]int8{ |
fml := map[int8][][]int8{ |
||
0: {{2, 2}, {8, 8}}, |
0: {{2, 2}, {8, 8}}, |
||
1: {{6, 5}, {8, 7}}, |
1: {{6, 5}, {8, 7}}, |
||
4: {{4, 0}}, |
4: {{4, 0}}, |
||
5: {{8, 3}}, |
|||
6: {{6, 0}, {8, 2}}, |
6: {{6, 0}, {8, 2}}, |
||
} |
} |
||
| Line 481: | Line 486: | ||
dmd[d] = append(dmd[d], a) |
dmd[d] = append(dmd[d], a) |
||
} |
} |
||
fl := []int8{0, 1, 4 |
fl := []int8{0, 1, 4, 6} |
||
dl := seq(-9, 9) |
dl := seq(-9, 9, 1) // all differences |
||
zl := []int8{0} // zero differences only |
|||
el := seq(-8, 8, 2) // even differences only |
|||
ol := seq(-9, 9, 2) // odd differences only |
|||
il := seq(0, 9, 1) |
|||
var rares []int64 |
var rares []int64 |
||
lists := [][]int8 |
lists := make([][][]int8, 4) |
||
for i, f := range fl { |
|||
fmt.Printf("The rare numbers with up to %d digits are:\n", maxDigits) |
|||
lists[i] = [][]int8{{f}} |
|||
} |
|||
for nd := 2; nd <= maxDigits; nd++ { |
for nd := 2; nd <= maxDigits; nd++ { |
||
digits := make([]int8, nd) |
digits := make([]int8, nd) |
||
if |
if nd == 4 { |
||
lists = append(lists, |
lists[0] = append(lists[0], zl) |
||
lists[1] = append(lists[1], ol) |
|||
lists[2] = append(lists[2], el) |
|||
lists[3] = append(lists[3], ol) |
|||
} else if len(allTerms[nd-2]) > len(lists[0]) { |
|||
for i := 0; i < 4; i++ { |
|||
lists[i] = append(lists[i], dl) |
|||
} |
|||
} |
} |
||
var indices [][2]int8 |
var indices [][2]int8 |
||
| Line 496: | Line 513: | ||
indices = append(indices, [2]int8{t.ix1, t.ix2}) |
indices = append(indices, [2]int8{t.ix1, t.ix2}) |
||
} |
} |
||
cands := cp(lists...) |
|||
for _, |
for _, list := range lists { |
||
ch := make(chan []int8, chanBufSize) |
|||
go cp(ch, list...) |
|||
for cand := range ch { |
|||
nmr := int64(0) |
|||
for i, t := range allTerms[nd-2] { |
|||
nmr += t.coeff * int64(cand[i]) |
|||
} |
|||
var dis [][]int8 |
|||
dis = append(dis, seq(0, int8(len(fml[cand[0]]))-1)) |
|||
for i := 1; i < len(cand); i++ { |
|||
dis = append(dis, seq(0, int8(len(dmd[cand[i]]))-1)) |
|||
} |
|||
if nd%2 == 1 { |
|||
dis = append(dis, il) |
|||
} |
|||
dis = cp(dis...) |
|||
for _, di := range dis { |
|||
digits[indices[0][0]] = fml[cand[0]][di[0]][0] |
|||
digits[indices[0][1]] = fml[cand[0]][di[0]][1] |
|||
le := len(di) |
|||
if nd%2 == 1 { |
|||
le-- |
|||
digits[nd/2] = di[le] |
|||
} |
|||
for i, d := range di[1:le] { |
|||
digits[indices[i+1][0]] = dmd[cand[i+1]][d][0] |
|||
digits[indices[i+1][1]] = dmd[cand[i+1]][d][1] |
|||
} |
} |
||
if nmr <= 0 || !isSquare(nmr) { |
|||
npr := nmr + 2*r |
|||
if !isSquare(npr) { |
|||
continue |
continue |
||
} |
} |
||
var dis [][]int8 |
|||
dis = append(dis, seq(0, int8(len(fml[cand[0]]))-1, 1)) |
|||
for i := 1; i < len(cand); i++ { |
|||
dis = append(dis, seq(0, int8(len(dmd[cand[i]]))-1, 1)) |
|||
} |
|||
if nd%2 == 1 { |
|||
dis = append(dis, il) |
|||
} |
|||
ch2 := make(chan []int8, chanBufSize) |
|||
go cp(ch2, dis...) |
|||
for di := range ch2 { |
|||
digits[indices[0][0]] = fml[cand[0]][di[0]][0] |
|||
digits[indices[0][1]] = fml[cand[0]][di[0]][1] |
|||
le := len(di) |
|||
if nd%2 == 1 { |
|||
le-- |
|||
digits[nd/2] = di[le] |
|||
} |
|||
for i, d := range di[1:le] { |
|||
digits[indices[i+1][0]] = dmd[cand[i+1]][d][0] |
|||
digits[indices[i+1][1]] = dmd[cand[i+1]][d][1] |
|||
} |
|||
r := toInt64(digits, true) |
|||
npr := nmr + 2*r |
|||
if !isSquare(npr) { |
|||
continue |
|||
} |
|||
rares = append(rares, toInt64(digits, false)) |
|||
} |
|||
} |
} |
||
} |
} |
||
fmt.Printf(" %2d digits: %9s ms\n", nd, commatize(time.Since(start).Milliseconds())) |
|||
} |
} |
||
sort.Slice(rares, func(i, j int) bool { return rares[i] < rares[j] }) |
sort.Slice(rares, func(i, j int) bool { return rares[i] < rares[j] }) |
||
fmt.Printf("\nThe rare numbers with up to %d digits are:\n", maxDigits) |
|||
for i, rare := range rares { |
for i, rare := range rares { |
||
fmt.Printf(" %2d: % |
fmt.Printf(" %2d: %22s\n", i+1, commatize(rare)) |
||
} |
} |
||
fmt.Printf("\nUp to %d digits processed in %s\n", maxDigits, time.Since(start)) |
|||
}</lang> |
}</lang> |
||
{{output}} |
{{output}} |
||
<pre> |
<pre> |
||
Aggregate timings to process all numbers up to: |
|||
The rare numbers with up to 15 digits are: |
|||
2 digits: 0 ms |
|||
3 digits: 0 ms |
|||
4 digits: 0 ms |
|||
5 digits: 0 ms |
|||
6 digits: 0 ms |
|||
7 digits: 1 ms |
|||
8 digits: 6 ms |
|||
9 digits: 9 ms |
|||
10 digits: 118 ms |
|||
11 digits: 180 ms |
|||
10: 20,313,693,904,202 |
|||
12 digits: 1,363 ms |
|||
11: 20,313,839,704,202 |
|||
13 digits: 2,323 ms |
|||
12: 20,331,657,922,202 |
|||
14 digits: 26,586 ms |
|||
13: 20,331,875,722,202 |
|||
15 digits: 43,034 ms |
|||
14: 20,333,875,702,202 |
|||
16 digits: 405,029 ms |
|||
15: 40,313,893,704,200 |
|||
17 digits: 678,839 ms |
|||
16: 40,351,893,720,200 |
|||
17: 200,142,385,731,002 |
|||
18: 204,238,494,066,002 |
|||
19: 221,462,345,754,122 |
|||
20: 244,062,891,224,042 |
|||
21: 245,518,996,076,442 |
|||
22: 248,359,494,187,442 |
|||
23: 403,058,392,434,500 |
|||
24: 441,054,594,034,340 |
|||
25: 816,984,566,129,618 |
|||
The rare numbers with up to 17 digits are: |
|||
Up to 15 digits processed in 42.075636626s |
|||
1: 65 |
|||
2: 621,770 |
|||
3: 281,089,082 |
|||
4: 2,022,652,202 |
|||
5: 2,042,832,002 |
|||
6: 868,591,084,757 |
|||
7: 872,546,974,178 |
|||
8: 872,568,754,178 |
|||
9: 6,979,302,951,885 |
|||
10: 20,313,693,904,202 |
|||
11: 20,313,839,704,202 |
|||
12: 20,331,657,922,202 |
|||
13: 20,331,875,722,202 |
|||
14: 20,333,875,702,202 |
|||
15: 40,313,893,704,200 |
|||
16: 40,351,893,720,200 |
|||
17: 200,142,385,731,002 |
|||
18: 204,238,494,066,002 |
|||
19: 221,462,345,754,122 |
|||
20: 244,062,891,224,042 |
|||
21: 245,518,996,076,442 |
|||
22: 248,359,494,187,442 |
|||
23: 403,058,392,434,500 |
|||
24: 441,054,594,034,340 |
|||
25: 816,984,566,129,618 |
|||
26: 2,078,311,262,161,202 |
|||
27: 2,133,786,945,766,212 |
|||
28: 2,135,568,943,984,212 |
|||
29: 2,135,764,587,964,212 |
|||
30: 2,135,786,765,764,212 |
|||
31: 4,135,786,945,764,210 |
|||
32: 6,157,577,986,646,405 |
|||
33: 6,889,765,708,183,410 |
|||
34: 8,052,956,026,592,517 |
|||
35: 8,052,956,206,592,517 |
|||
36: 8,191,154,686,620,818 |
|||
37: 8,191,156,864,620,818 |
|||
38: 8,191,376,864,400,818 |
|||
39: 8,650,327,689,541,457 |
|||
40: 8,650,349,867,341,457 |
|||
41: 22,542,040,692,914,522 |
|||
42: 67,725,910,561,765,640 |
|||
43: 86,965,750,494,756,968 |
|||
</pre> |
</pre> |
||