148 lines
3.6 KiB
Go
148 lines
3.6 KiB
Go
package main
|
|
|
|
import (
|
|
"fmt"
|
|
"math/big"
|
|
"time"
|
|
)
|
|
|
|
// constants as expanded integers to minimize round-off errors, and
|
|
// reduce execution time using integer operations not float...
|
|
const cLAA2 uint64 = 35184372088832 // 2.0f64.ln() * 2.0f64.powi(45)).round() as u64;
|
|
const cLBA2 uint64 = 55765910372219 // 3.0f64.ln() / 2.0f64.ln() * 2.0f64.powi(45)).round() as u64;
|
|
const cLCA2 uint64 = 81695582054030 // 5.0f64.ln() / 2.0f64.ln() * 2.0f64.powi(45)).round() as u64;
|
|
|
|
type logelm struct { // log representation of an element with only allowable powers
|
|
exp2 uint16
|
|
exp3 uint16
|
|
exp5 uint16
|
|
logr uint64 // log representation used for comparison only - not exact
|
|
}
|
|
|
|
func (self *logelm) lte(othr *logelm) bool {
|
|
if self.logr <= othr.logr {
|
|
return true
|
|
} else {
|
|
return false
|
|
}
|
|
}
|
|
func (self *logelm) mul2() logelm {
|
|
return logelm{
|
|
exp2: self.exp2 + 1,
|
|
exp3: self.exp3,
|
|
exp5: self.exp5,
|
|
logr: self.logr + cLAA2,
|
|
}
|
|
}
|
|
func (self *logelm) mul3() logelm {
|
|
return logelm{
|
|
exp2: self.exp2,
|
|
exp3: self.exp3 + 1,
|
|
exp5: self.exp5,
|
|
logr: self.logr + cLBA2,
|
|
}
|
|
}
|
|
func (self *logelm) mul5() logelm {
|
|
return logelm{
|
|
exp2: self.exp2,
|
|
exp3: self.exp3,
|
|
exp5: self.exp5 + 1,
|
|
logr: self.logr + cLCA2,
|
|
}
|
|
}
|
|
|
|
func log_nodups_hamming(n uint) *big.Int {
|
|
if n < 1 {
|
|
panic("log_nodups_hamming: argument < 1!")
|
|
}
|
|
if n < 2 { // trivial case of first in sequence
|
|
return big.NewInt(1)
|
|
}
|
|
if n > 1.2e15 {
|
|
panic("log_nodups_hamming: argument too large!")
|
|
}
|
|
|
|
one := logelm{}
|
|
next5, merge := one.mul5(), one.mul3()
|
|
next53, next532 := merge.mul3(), one.mul2()
|
|
|
|
g := make([]logelm, 1, 65536)
|
|
g[0] = one // never used, just so append works
|
|
h := make([]logelm, 1, 65536)
|
|
h[0] = one // never used, just so append works
|
|
|
|
i, j := 1, 1
|
|
for m := uint(1); m < n; m++ {
|
|
cph := cap(h)
|
|
if i >= cph/2 {
|
|
nm := copy(h[0:i], h[i:])
|
|
h = h[0:nm:cph]
|
|
i = 0
|
|
}
|
|
if next532.lte(&merge) {
|
|
h = append(h, next532)
|
|
next532 = h[i].mul2()
|
|
i++
|
|
} else {
|
|
h = append(h, merge)
|
|
if next53.lte(&next5) {
|
|
merge = next53
|
|
next53 = g[j].mul3()
|
|
j++
|
|
} else {
|
|
merge = next5
|
|
next5 = next5.mul5()
|
|
}
|
|
cpg := cap(g)
|
|
if j >= cpg/2 {
|
|
nm := copy(g[0:j], g[j:])
|
|
g = g[0:nm:cpg]
|
|
j = 0
|
|
}
|
|
g = append(g, merge)
|
|
}
|
|
}
|
|
|
|
two, three, five := big.NewInt(2), big.NewInt(3), big.NewInt(5)
|
|
o := h[len(h)-1] // convert last element to big integer...
|
|
ob := big.NewInt(1)
|
|
for i := uint16(0); i < o.exp2; i++ {
|
|
ob.Mul(two, ob)
|
|
}
|
|
for i := uint16(0); i < o.exp3; i++ {
|
|
ob.Mul(three, ob)
|
|
}
|
|
for i := uint16(0); i < o.exp5; i++ {
|
|
ob.Mul(five, ob)
|
|
}
|
|
return ob
|
|
}
|
|
|
|
func main() {
|
|
n := uint(1e6)
|
|
|
|
rarr := make([]*big.Int, 20)
|
|
for i, _ := range rarr {
|
|
rarr[i] = log_nodumps_hamming(i)
|
|
}
|
|
fmt.Println(rarr)
|
|
|
|
fmt.Println(log_nodups_hamming(1691))
|
|
|
|
strt := time.Now()
|
|
|
|
rslt := log_nodups_hamming(n)
|
|
|
|
end := time.Now()
|
|
|
|
rs := rslt.String()
|
|
lrs := len(rs)
|
|
fmt.Printf("%v digits:\r\n", lrs)
|
|
ndx := 0
|
|
for ; ndx < lrs-100; ndx += 100 {
|
|
fmt.Println(rs[ndx : ndx+100])
|
|
}
|
|
fmt.Println(rs[ndx:])
|
|
|
|
fmt.Printf("This last found the %vth hamming number in %v.\r\n", n, end.Sub(strt))
|
|
}
|