Rare numbers: Difference between revisions
→Version 2: Replaced with version which has relatively low memory requirement.
(→Version 1: Replaced with much faster version.) |
(→Version 2: Replaced with version which has relatively low memory requirement.) |
||
Line 363:
===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.
<lang go>package main
Line 380 ⟶ 378:
}
const
maxDigits = 17
chanBufSize = 100
)
func toInt64(digits []int8, reverse bool) int64 {
Line 397 ⟶ 398:
func isSquare(n int64) bool {
if 0x202021202030213&(1<<(n&63)) != 0 {
return root*root == n
}
return false
}
// 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(ch chan<- []int8, a ...[]int8) {
c := 1
for _, a := range a {
Line 408 ⟶ 413:
}
if c == 0 {
return
}
b := make([]int8, c*len(a))
n := make([]int8, len(a))
s := 0
for i :=
e := s + len(a)
pi := b[s:e]
for j, n := range n {
pi[j] = a[j][n]
Line 429 ⟶ 432:
n[j] = 0
}
ch <- pi
s = e
}
}
func seq(from, to, step int8) []int8 {
var res []int8
for i := from; i <= to; i +
res = append(res, i)
}
Line 455 ⟶ 460:
// terms of (n-r) expression for number of digits from 2 to maxDigits
allTerms := make([][]term, maxDigits-1)
fmt.Println("Aggregate timings to process all numbers up to:")
for r := 2; r <= maxDigits; r++ {
var terms []term
Line 466 ⟶ 472:
allTerms[r-2] = terms
}
//
fml := map[int8][][]int8{
0: {{2, 2}, {8, 8}},
1: {{6, 5}, {8, 7}},
4: {{4, 0}},
6: {{6, 0}, {8, 2}},
}
Line 481 ⟶ 486:
dmd[d] = append(dmd[d], a)
}
fl := []int8{0, 1, 4
dl := seq(-9, 9, 1) // all differences
el := seq(-8, 8, 2) // even differences only
ol := seq(-9, 9, 2) // odd differences only
il := seq(0, 9, 1)
var rares []int64
lists := make([][][]int8
for i, f := range fl {
lists[i] = [][]int8{{f}}
}
for nd := 2; nd <= maxDigits; nd++ {
digits := make([]int8, nd)
if
lists[0] = append(lists[0],
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
Line 496 ⟶ 513:
indices = append(indices, [2]int8{t.ix1, t.ix2})
}
for _,
for cand := range ch {
}
continue
}
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] })
fmt.Printf("\nThe rare numbers with up to %d digits are:\n", maxDigits)
for i, rare := range rares {
fmt.Printf(" %2d: %
}
}</lang>
{{output}}
<pre>
Aggregate timings to process all numbers up to:
10
11 digits: 180 ms
12 digits: 1,363 ms
13 digits: 2,323 ms
14 digits: 26,586 ms
15 digits: 43,034 ms
16 digits: 405,029 ms
17 digits: 678,839 ms
The rare numbers with up to 17 digits are:
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>
| |||