Rare numbers: Difference between revisions
Content deleted Content added
Thundergnat (talk | contribs) alphabetize, minor clean-up |
→{{header|Go}}: Added a third 'turbo' version. |
||
Line 2,357:
74 8200756128308135597 4019461925 495417087
75 8320411466598809138 4079154376 36366330 19: 00:45:42.006 00:54:39.816
</pre>
<br>
===Turbo===
{{trans|C++}}
A small turbo anyway :)
The following, which is a translation of the C++ 10 to 19 digits program, completes in just over 21 minutes which is about 2.5 times faster than the 'quicker' version above.
Curiously, the C++ program itself when compiled with g++ 7.5.0 (-std=c++17 -O3) on the same machine completes in just over 30 minutes though I understand that when using other C++ compilers (clang, mingw) it's much faster than this.
<lang go>package main
import (
"fmt"
"math"
"sort"
"time"
)
type (
z1 func() z2
z2 struct {
value int64
hasValue bool
}
)
var pow10 [19]int64
func init() {
pow10[0] = 1
for i := 1; i < 19; i++ {
pow10[i] = 10 * pow10[i-1]
}
}
func izRev(n int, i, g uint64) bool {
if i/uint64(pow10[n-1]) != g%10 {
return false
}
if n < 2 {
return true
}
return izRev(n-1, i%uint64(pow10[n-1]), g/10)
}
func fG(n z1, start, end, reset int, step int64, l *int64) z1 {
i, g, e := step*int64(start), step*int64(end), step*int64(reset)
return func() z2 {
for i < g {
*l += step
i += step
return z2{*l, true}
}
i = e
*l -= (g - e)
return n()
}
}
type nLH struct{ even, odd []uint64 }
type zp struct {
n z1
g [][2]int64
}
func newNLH(e zp) nLH {
var even, odd []uint64
n, g := e.n, e.g
for i := n(); i.hasValue; i = n() {
for _, p := range g {
ng, gg := p[0], p[1]
if (ng > 0) || (i.value > 0) {
w := uint64(ng*pow10[4] + gg + i.value)
ws := uint64(math.Sqrt(float64(w)))
if ws*ws == w {
if w%2 == 0 {
even = append(even, w)
} else {
odd = append(odd, w)
}
}
}
}
}
return nLH{even, odd}
}
func makeL(n int) zp {
g := make([]z1, n/2-3)
g[0] = func() z2 { return z2{} }
for i := 1; i < n/2-3; i++ {
s := -9
if i == n/2-4 {
s = -10
}
l := pow10[n-i-4] - pow10[i+3]
acc += l * int64(s)
g[i] = fG(g[i-1], s, 9, -9, l, &acc)
}
var g0, g1, g2, g3 int64
l0, l1, l2, l3 := pow10[n-5], pow10[n-6], pow10[n-7], pow10[n-8]
f := func() [][2]int64 {
var w [][2]int64
for g0 < 10 {
nn := g3*l3 + g2*l2 + g1*l1 + g0*l0
gg := -1000*g3 - 100*g2 - 10*g1 - g0
if g3 < 9 {
g3++
} else {
g3 = -9
if g2 < 9 {
g2++
} else {
g2 = -9
if g1 < 9 {
g1++
} else {
g1 = -9
g0++
}
}
}
if bs[(pow10[10]+gg)%10000] {
w = append(w, [2]int64{nn, gg})
}
}
return w
}
return zp{g[n/2-4], f()}
}
func makeH(n int) zp {
acc = -(pow10[n/2] + pow10[(n-1)/2])
g := make([]z1, (n+1)/2-3)
g[0] = func() z2 { return z2{} }
for i := 1; i < n/2-3; i++ {
j := 0
if i == (n+1)/2-3 {
j = -1
}
g[i] = fG(g[i-1], j, 18, 0, pow10[n-i-4]+pow10[i+3], &acc)
if n%2 == 1 {
g[(n+1)/2-4] = fG(g[n/2-4], -1, 9, 0, 2*pow10[n/2], &acc)
}
}
g0 := int64(1)
var g1, g2, g3 int64
l0, l1, l2, l3 := pow10[n-5], pow10[n-6], pow10[n-7], pow10[n-8]
f := func() [][2]int64 {
var w [][2]int64
for g0 < 17 {
nn := g3*l3 + g2*l2 + g1*l1 + g0*l0
gg := 1000*g3 + 100*g2 + 10*g1 + g0
if g3 < 18 {
g3++
} else {
g3 = 0
if g2 < 18 {
g2++
} else {
g2 = 0
if g1 < 18 {
g1++
} else {
g1 = 0
g0++
}
}
}
if bs[gg%10000] {
w = append(w, [2]int64{nn, gg})
}
}
return w
}
return zp{g[(n+1)/2-4], f()}
}
var (
acc int64
bs = make([]bool, 10000)
L, H nLH
)
func rare(n int) []uint64 {
acc = 0
for g := 0; g < 10000; g++ {
bs[(g*g)%10000] = true
}
L = newNLH(makeL(n))
H = newNLH(makeH(n))
var rares []uint64
for _, l := range L.even {
for _, h := range H.even {
r := (h - l) / 2
z := h - r
if izRev(n, r, z) {
rares = append(rares, z)
}
}
}
for _, l := range L.odd {
for _, h := range H.odd {
r := (h - l) / 2
z := h - r
if izRev(n, r, z) {
rares = append(rares, z)
}
}
}
if len(rares) > 0 {
sort.Slice(rares, func(i, j int) bool {
return rares[i] < rares[j]
})
}
return rares
}
// Formats time in form hh:mm:ss.fff (i.e. millisecond precision).
func formatTime(d time.Duration) string {
f := d.Milliseconds()
s := f / 1000
f %= 1000
m := s / 60
s %= 60
h := m / 60
m %= 60
return fmt.Sprintf("%02d:%02d:%02d.%03d", h, m, s, f)
}
func commatize(n uint64) string {
s := fmt.Sprintf("%d", n)
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
return s
}
func main() {
bStart := time.Now() // block time
tStart := bStart // total time
nth := 3 // i.e. count of rare numbers < 10 digits
fmt.Println("nth rare number digs block time total time")
for nd := 10; nd < 20; nd++ {
rares := rare(nd)
if len(rares) > 0 {
for i, r := range rares {
nth++
t := ""
if i < len(rares)-1 {
t = "\n"
}
fmt.Printf("%2d %25s%s", nth, commatize(r), t)
}
} else {
fmt.Printf("%29s", "")
}
fbTime := formatTime(time.Since(bStart))
ftTime := formatTime(time.Since(tStart))
fmt.Printf(" %2d: %s %s\n", nd, fbTime, ftTime)
bStart = time.Now() // restart block timing
}
}</lang>
{{out}}
<pre style="height:126ex;overflow:scroll">
nth rare number digs block time total time
4 2,022,652,202
5 2,042,832,002 10: 00:00:00.002 00:00:00.002
11: 00:00:00.008 00:00:00.010
6 868,591,084,757
7 872,546,974,178
8 872,568,754,178 12: 00:00:00.022 00:00:00.032
9 6,979,302,951,885 13: 00:00:00.144 00:00:00.177
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 14: 00:00:00.378 00:00:00.555
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 15: 00:00:02.423 00:00:02.979
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 16: 00:00:06.862 00:00:09.841
41 22,542,040,692,914,522
42 67,725,910,561,765,640
43 86,965,750,494,756,968 17: 00:00:45.868 00:00:55.709
44 225,342,456,863,243,522
45 225,342,458,663,243,522
46 225,342,478,643,243,522
47 284,684,666,566,486,482
48 284,684,868,364,486,482
49 297,128,548,234,950,692
50 297,128,722,852,950,692
51 297,148,324,656,930,692
52 297,148,546,434,930,692
53 497,168,548,234,910,690
54 619,431,353,040,136,925
55 619,631,153,042,134,925
56 631,688,638,047,992,345
57 633,288,858,025,996,145
58 633,488,632,647,994,145
59 653,488,856,225,994,125
60 811,865,096,390,477,018
61 865,721,270,017,296,468
62 871,975,098,681,469,178
63 898,907,259,301,737,498 18: 00:02:11.861 00:03:07.571
64 2,042,401,829,204,402,402
65 2,060,303,819,041,450,202
66 2,420,424,089,100,600,242
67 2,551,755,006,254,571,552
68 2,702,373,360,882,732,072
69 2,825,378,427,312,735,282
70 6,531,727,101,458,000,045
71 6,988,066,446,726,832,640
72 8,066,308,349,502,036,608
73 8,197,906,905,009,010,818
74 8,200,756,128,308,135,597
75 8,320,411,466,598,809,138 19: 00:17:59.503 00:21:07.075
</pre>
| |||