Hamming numbers: Difference between revisions
→{{header|Wren}}: Added a second much faster version.
GordonBGood (talk | contribs) (→Fast version with no duplicates algorithm using arrays for memoization and logarithmic approximations: V lang - change to "ring buffer" version...) |
(→{{header|Wren}}: Added a second much faster version.) |
||
Line 12,493:
=={{header|Wren}}==
{{libheader|Wren-big}}
▲Simple but slow.
<syntaxhighlight lang="ecmascript">import "/big" for BigInt, BigInts
Line 12,537:
The 1,000,000th Hamming number is:
519312780448388736089589843750000000000000000000000000000000000000000000000000000000
</pre>
===Much faster logarithmic version===
{{trans|Go}}
{{libheader|Wren-dynamic}}
{{libheader|Wren-long}}
{{libheader|Wren-math}}
A translation of Go's 'extremely fast version inserting logarithms into the top error band'.
Not as fast as the statically typed languages but fast enough for me :)
<syntaxhighlight lang="ecmascript">import "./dynamic" for Struct
import "./long" for ULong
import "./big" for BigInt
import "./math" for Math
var Logrep = Struct.create("LogRep", ["lg", "x2", "x3", "x5"])
var nthHamming = Fn.new { |n|
if (n < 2) {
if (n < 1) Fiber.abort("nthHamming: argument is zero!")
return [0, 0, 0]
}
var lb3 = 1.5849625007211561814537389439478
var lb5 = 2.3219280948873623478703194294894
var fctr = 6 * lb3 * lb5
var crctn = 2.4534452978042592646620291867186
var lgest = (n.toNum * fctr).cbrt - crctn
var frctn = (n < 1000000000) ? 0.509 : 0.106
var lghi = ((n.toNum + lgest * frctn) * fctr).cbrt - crctn
var lglo = lgest * 2 - lghi
var count = ULong.zero
var bnd = []
var klmt = (lghi/lb5).truncate.abs + 1
for (k in 0...klmt) {
var p = k * lb5
var jlmt = ((lghi - p)/lb3).truncate.abs + 1
for (j in 0...jlmt) {
var q = p + j * lb3
var ir = lghi - q
var lg = q + ir.floor
count = count + ir.truncate.abs + 1
if (lg >= lglo) bnd.add(Logrep.new(lg, ir.truncate.abs, j, k))
}
}
if (n > count) Fiber.abort("nthHamming: band high estimate is too low!")
var ndx = (count - n).toSmall
if (ndx >= bnd.count) Fiber.abort("nthHamming: band low estimate is too high!")
bnd.sort { |a, b| b.lg < a.lg }
var rslt = bnd[ndx]
return [rslt.x2, rslt.x3, rslt.x5]
}
var convertTpl2BigInt = Fn.new { |tpl|
var result = BigInt.one
for (i in 0...tpl[0]) result = result * 2
for (i in 0...tpl[1]) result = result * 3
for (i in 0...tpl[2]) result = result * 5
return result
}
System.print("The first 20 Hamming numbers are:")
for (i in 1..20) {
System.write("%(convertTpl2BigInt.call(nthHamming.call(ULong.new(i)))) ")
}
System.print("\n\nThe 1,691st Hamming number is:")
System.print(convertTpl2BigInt.call(nthHamming.call(ULong.new(1691))))
var start = System.clock
var res = nthHamming.call(ULong.new(1e6))
var end = System.clock
System.print("\nThe 1,000,000 Hamming number is:")
System.print(convertTpl2BigInt.call(res))
var duration = ((end-start) * 1000).round
System.print("The last of these found in %(duration) milliseconds.")</syntaxhighlight>
{{out}}
<pre>
The first 20 Hamming numbers are:
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
The 1,691st Hamming number is:
2125764000
The 1,000,000 Hamming number is:
519312780448388736089589843750000000000000000000000000000000000000000000000000000000
The last of these found in 16 milliseconds.
</pre>
| |||