Rosetta Code

Hamming numbers: Difference between revisions

Page Discussion

Hamming numbers (view source)

Revision as of 04:50, 4 September 2022

183 bytes added ,  1 year ago
→‎Infinite generator, avoiding duplicates, using logarithms for faster processing: Julia: improved algorithm, tweaked performance...
(→‎Fast enumerating logarithmic version: C# - imperative log improved algorithm...)
Line 6,358:
===Infinite generator, avoiding duplicates, using logarithms for faster processing===
 
The above code is slow for several reasons, partly because it is doing many multi-precision integer multiplications requiring much memory allocation and garbage collection for which the current Julia version 1.0.2 is quite slow, but also because there are many repeated calculations (3 timetimes 2 equals 2 times three, etc.). The following code is about 3060 times faster by using floating point logarithms for multiplication and comparison; it also is an infinite generator (an iterator), which means that memory consumption can be greatly reduced by eliminating values which are no longer of any use:
{{trans|Nim}}
<syntaxhighlight lang="julia">functionstruct trival((twos, threes, fives))LogRep
BigInt(2)^twos * BigInt(3)^threes * BigInt(5)^fives▼
lg :: Float64
x2 :: UInt32
x3 :: UInt32
x5 :: UInt32
end▼
const ONE = LogRep(0.0, 0, 0, 0)
const LB2_2 = 1.0
const LB2_3 = log(2,3)
const LB2_5 = log(2,5)
function mult2(lr :: LogRep) # :: LogRep
LogRep(lr.lg + LB2_2, lr.x2 + 1, lr.x3, lr.x5)
end▼
function mult3(lr :: LogRep) # :: LogRep
LogRep(lr.lg + LB2_3, lr.x2, lr.x3 + 1, lr.x5)
end
function mult5(lr :: LogRep) # :: LogRep
LogRep(lr.lg + LB2_5, lr.x2, lr.x3, lr.x5 + 1)
end
function lr2BigInt(lr :: LogRep) # :: BigInt
▲ BigInt(2)^twoslr.x2 * BigInt(3)^threeslr.x3 * BigInt(5)^fiveslr.x5
end
 
mutable struct HammingsHammingsLog
ham532s2 :: Vector{Tuple{Float64,Tuple{Int,Int,Int}}LogRep}
ham53s3 :: Vector{Tuple{Float64,Tuple{Int,Int,Int}}LogRep}
ndx532s5 :: IntLogRep
ndx53mrg :: IntLogRep
next2s2hdi :: Tuple{Float64,Tuple{Int,Int,Int}}
next3s3hdi :: Tuple{Float64,Tuple{Int,Int,Int}}
HammingsLog() = new(
next5 :: Tuple{Float64,Tuple{Int,Int,Int}}
[ONE],
next53 :: Tuple{Float64,Tuple{Int,Int,Int}}
Hammings() = new [mult3(ONE)],
mult5(ONE),
Vector{Tuple{Float64,Tuple{Int,Int,Int}}}(),
mult3(ONE),
Vector{Tuple{Float64,Tuple{Int,Int,Int}}}(),
1, 1,
(1.0, (1, 0, 0)), (log(2, 3), (0, 1, 0)),
(log(2, 5), (0, 0, 1)), (0.0, (0, 0, 0))
)
end
Base.eltype(::Type{HammingsHammingsLog}) = Tuple{Int,Int,Int}LogRep
function Base.iterate(HM::HammingsHammingsLog, st = HM) # :: Union{Nothing,Tuple{Tuple{Float64,Tuple{Int,Int,Int}}LogRep,HammingsHammingsLog}}
len53s2sz = length(st.ham53s2)▼
log2of2, log2of3, log2of5 = 1.0, log(2,3), log(2,5)
if st.next2[1]s2hdi <+ st.next53[1]s2hdi - 2 >= s2sz
push!(st.ham532,ns2sz st.next2);= s2sz - st.ndx532s2hdi += 1
last, copyto!(twosst.s2, threes1, fives) = st.ham532[s2, st.ndx532]s2hdi, ns2sz)
resize!(st.next2s2, =ns2sz); (log2of2st.s2hdi + last, (twos += 1, threes, fives))
end
rslt = @inbounds(st.s2[st.s2hdi])
if rslt.lg < st.mrg.lg
st.s2hdi += 1
else
push!s3sz = length(st.ham532, st.next53s3)
if st.next3[1]s3hdi <+ st.next5[1]s3hdi - 2 >= s3sz
st.next53ns3sz = st.next3;s3sz - push!(st.ham53,s3hdi st.next3)+ 1
last, copyto!(_st.s3, threes1, fives) = st.ham53[st.ndx53];s3, st.ndx53s3hdi, += 1ns3sz)
resize!(st.next3 = (log2of3 + lasts3, (0,ns3sz); threesst.s3hdi += 1, fives))
end
rslt = st.mrg; push!(st.s3, mult3(rslt))
st.s3hdi += 1; chkv = @inbounds(st.s3[st.s3hdi])
if chkv.lg < st.s5.lg
nlen53 = len53 - st.ndx53mrg += 1chkv▼
else
st.next53mrg = st.next5s5; push!(st.ham53,s5 = mult5(st.next5s5); st.s3hdi -= 1
last, (_, _, fives) = st.next5
st.next5 = (log2of5 + last, (0, 0, fives + 1))
end
end
push!(st.s2, mult2(rslt)); rslt, st
▲ len53 = length(st.ham53)
end
if st.ndx53 > (len53 >>> 1)
 
▲ nlen53 = len53 - st.ndx53 + 1
function test(n :: Int) :: Tuple{LogRep, Float64}
copyto!(st.ham53, 1, st.ham53, st.ndx53, nlen53)
start = resize!time(st.ham53, nlen53); st.ndx53rslt :: LogRep = 1ONE
let count = 1000000n; for t in HammingsHammingsLog() count <= 1 && (println(trival(rslt = t)); break); count -= 1 end end</syntaxhighlight>▼
▲ end
elpsd = (time() - start) * 1000
len532 = length(st.ham532)
rslt, elpsd
if st.ndx532 > (len532 >>> 1)
nlen532 = len532 - st.ndx532 + 1
copyto!(st.ham532, 1, st.ham532, st.ndx532, nlen532)
resize!(st.ham532, nlen532); st.ndx532 = 1
▲ end
_, tri = st.ham532[end]
tri, st
# convert(Union{Nothing,Tuple{Tuple{Float64,Tuple{Int,Int,Int}},Hammings}},(st.ham532[end], st))
# (length(st.ham532), length(st.ham53)), st
end
 
foreach(x -> print(trivallr2BigInt(x)," "), (Iterators.take(HammingsHammingsLog(), 20))); println()
let count = 1691; for t in HammingsHammingsLog() count <= 1 && (println(trivallr2BigInt(t)); break); count -= 1 end end
rslt, elpsd = test(1000000)
▲let count = 1000000; for t in Hammings() count <= 1 && (println(trival(t)); break); count -= 1 end end</syntaxhighlight>
println(lr2BigInt(rslt))
println("This last took $elpsd milliseconds.")</syntaxhighlight>
{{out}}
<pre>1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
2125764000
519312780448388736089589843750000000000000000000000000000000000000000000000000000000
This last took 16.8759822845459 milliseconds.</pre>
The above execution time is as run on an Intel i5-6500 at 3.6 GHz (single threaded boost), and the program can find the billionth Hamming number in about 17 seconds.
 
===Determination of the nth Hamming number by processing of error band===
GordonBGood
474

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/329608"