Hamming numbers: Difference between revisions
Added Easylang
GordonBGood (talk | contribs) (→Much faster iterating version using logarithmic calculations: Nim - added code using a ring buffer...) |
(Added Easylang) |
||
| (23 intermediate revisions by 13 users not shown) | |||
Line 846:
2125764000
519312780448388736089589843750000000000000000000000000000000000000000000000000000000</pre>
=={{header|Bruijn}}==
{{trans|Haskell}}
<code>n1000000</code> takes a very long time but eventually reduces to the correct result.
<syntaxhighlight lang="bruijn">
:import std/Combinator .
:import std/Number .
:import std/List .
merge y [[[∅?1 0 (1 [[2 [[go]]]])]]]
go 3 <? 1 (3 : (6 2 4)) (1 : (6 5 0))
# classic version while avoiding duplicate generation
hammings-classic (+1) : (foldr u empty ((+2) : ((+3) : {}(+5))))
u [[y [merge 1 ((mul 2) <$> ((+1) : 0))]]]
:test ((hammings-classic !! (+42)) =? (+162)) ([[1]])
# enumeration by a chain of folded merges (faster)
hammings-folded ([(0 ∘ a) ∘ (0 ∘ b)] (foldr merge1 empty)) $ c
merge1 [[1 [[1 : (merge 0 2)]]]]
a iterate (map (mul (+5)))
b iterate (map (mul (+3)))
c iterate (mul (+2)) (+1)
:test ((hammings-folded !! (+42)) =? (+162)) ([[1]])
# --- output ---
main [first-twenty : (n1691 : {}n1000000)]
first-twenty take (+20) hammings-folded
n1691 hammings-folded !! (+1690)
n1000000 hammings-folded !! (+999999)
</syntaxhighlight>
=={{header|C}}==
Line 3,614 ⟶ 3,648:
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Hamming_numbers#Pascal Pascal].
=={{header|EasyLang}}==
{{trans|11l}}
<syntaxhighlight>
func hamming lim .
len h[] lim
h[1] = 1
x2 = 2 ; x3 = 3 ; x5 = 5
i = 1 ; j = 1 ; k = 1
for n = 2 to lim
h[n] = lower x2 lower x3 x5
if x2 = h[n]
i += 1
x2 = 2 * h[i]
.
if x3 = h[n]
j += 1
x3 = 3 * h[j]
.
if x5 = h[n]
k += 1
x5 = 5 * h[k]
.
.
return h[lim]
.
for nr = 1 to 20
write hamming nr & " "
.
print ""
print hamming 1691
</syntaxhighlight>
{{out}}
<pre>
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
2125764000
</pre>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
Line 3,746 ⟶ 3,817:
=={{header|Elm}}==
The Elm language has many restrictions that make the implementation of the Hamming Number sequence algorithms difficult, as the classic Edsger Dijkstra algorithm as written in Haskell [[Hamming_numbers#The_classic_version]] cannot be written in Elm as current Elm forbids cyclic value references (the value "hamming" is back referenced three times), and the implementation wouldn't be efficient even if it could as the current Elm version 0.19.x has removed the "Lazy" package the would defer the memoization of the result of a computation as necessary in implementing Haskell's lazy lists. Thus, one has to implement memoization using a different data structure than a lazy list; however, all current Elm data structures are persistent/forbid mutation and can only implement some sort of Copy On Write (COW), thus there is no implementation of a linear array and the "Array" module is a tree based structure (with some concessions to data blocks for slightly better performance) that will have a logarithmic execution complexity when the size increases above a minimum. In fact, all Elm data structures that could be used for this also have a logarithmic response (Dict, Set, Array). The implementation of List is not lazy so new elements can't be added to the "tail" but need to be added to the "head" for efficiency, which means if one wants to add higher elements to a list in increasing order, one needs to (COW) reverse the List (twice) in order to do it!
The solution here uses a pure functional implementation of a Min Heap (Binary Heap) Priority Queue so that the minimum element can be viewed in O(1) time although inserting new elements/replacing elements still takes O(log n) time where "n" is the number of elements in the queue. As written, no queue needs to be maintained for the multiples of five, but two
To express the sequence, a Co-Inductive Stream (CIS) is used as a deferred execution (lazy) stream; it does not memoize computations (as discussed above) but that isn't necessary for this application where the sequence is only traversed once and consumed as being traversed.
In addition, in order to reduce the "BigInt" computation time, the calculations are done on the basis of a "Float" logarithmic
<syntaxhighlight lang="elm">module Main exposing ( main )
Line 3,759 ⟶ 3,830:
import BigInt
import Task exposing ( Task, succeed, perform, andThen )
import Html exposing (
import Browser exposing ( element )
import Time exposing ( now, posixToMillis )
Line 3,865 ⟶ 3,936:
let omin = case peekMinPQ bpq of
Just (lr, trv) -> LogRep lr trv
nm235 = multLR2 omin
nbpq = replaceMinPQ m235.lr m235.trv bpq
Line 3,874 ⟶ 3,945:
let omin = case peekMinPQ mpq of
Just (lr, trv) -> LogRep lr trv
nm35 = multLR3 omin
nmrg = if ltLogRep nm35 m5 then nm35 else m5
Line 3,890 ⟶ 3,961:
in CIS (0, 0, 0) <| \ () ->
next emptyPQ emptyPQ im235 imrg im35 im5
timemillis : () -> Task Never Int -- a side effect function
Line 3,903 ⟶ 3,967:
test : Int -> Cmd Msg -- side effect function chain (includes "perform")...
test lmt =
let msg1 = "The first 20 Hamming numbers are: " ++
|> List.map showTrival
|> String.join ", ") ++ "."
msg2 = "The 1691st Hamming number is " ++
(hammingsLog() |> nthCIS 1691
|> showTrival) ++ "."
msg3 = "The " ++ String.fromInt cLIMIT ++ "th Hamming number is:"
in timemillis()
|> andThen (\ strt ->
let rsltstr = hammingsLog() |> nthCIS lmt
|> showTrival in
timemillis()
|> andThen (\ stop ->
succeed [msg1, msg2, msg3, rsltstr ++ " in "
++ String.fromInt (stop - strt)
++ " milliseconds."]))
|> perform Done
-- following code has to do with outputting to a web page using MUV/TEA...
type Msg = Done Model
main : Program () Model Msg
main = -- starts with empty list of strings; views model of filled list...
element { init = \ _ -> (
, update = \ (Done mdl) _
, subscriptions = \ _ -> Sub.none
, view =
{{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 1691st Hamming number is 2125764000.
The 1000000th Hamming number is
519312780448388736089589843750000000000000000000000000000000000000000000000000000000 in 767 milliseconds.</pre>
Do note that, due to the logarithmic response of the Min Heap Priority Queue, the execution time is logarithmic with number of elements evaluation and not linear as it would otherwise be, so if it takes 0.7 seconds to find the millionth Hamming number, it takes something about 10 seconds to find the ten millionth value instead of about 7 seconds. Considering that the generated "native" code is just JavaScript, it is reasonably fast and somewhat competitive with easier implementations in other languages such as F#.
=={{header|Erlang}}==
For relatively small values of n we can use an elegant code:
<syntaxhighlight lang="erlang">
list(N) -> array:to_list(element(1, array(N, [2, 3, 5]))).
nth(N) -> array:get(N-1, element(1, array(N, [2, 3, 5]))).
array(N, Primes) -> array(array:new(), N, 1, [{P, 1, P} || P <- Primes]).
array(Array, Max, Max, Candidates) -> {Array, Candidates};
array(Array, Max, I, Candidates) ->
Smallest = smallest(Candidates),
N_array = array:set(I, Smallest, Array),
array(N_array, Max, I+1, update(Smallest, N_array, Candidates)).
update(Val, Array, Candidates) -> [update_(Val, C, Array) || C <- Candidates].
update_(Val, {Val, Ind, Mul}, Array) ->
{Mul*array:get(Ind, Array), Ind+1, Mul};
update_(_, X, _) -> X.
smallest(L) -> lists:min([element(1, V) || V <- L]).
</syntaxhighlight>
However, when n become large (let say above 5e7) the memory needed grew very large as I store all the values. Fortunately, the algorithm uses only a small fraction of the end of the array. So I can drop the beginning of the array when it is no longer needed.
<syntaxhighlight lang="erlang">
nth(N, Batch) ->
array:get(N-1, element(1, compact_array(N, Batch, [2, 3, 5]))).
compact_array(Goal, Lim, Primes) ->
{Array, Candidates} = array(Lim, Primes),
compact_array(Goal, Lim, Lim, Array, Candidates).
compact_array(Goal, _, Index, Array, Candidates) when Index > Goal ->
{Array, Candidates};
compact_array(Goal, Lim, Index, Array, Candidates) ->
{N_array, N_candidates} =
array(compact(Array, Candidates), Index + Lim, Index, Candidates),
compact_array(Goal, Lim, Index+Lim, N_array, N_candidates).
compact(Array, L) ->
Index = lists:min([element(2, V) || V <- L]),
Keep = [E || E <- array:sparse_to_orddict(Array), element(1, E) >= Index],
array:from_orddict(Keep).
</syntaxhighlight>
With this approach memory is no longer an issue:
{{out}}
<pre>
timer:tc(task_hamming_numbers, nth, [100_000_000, 1_000_000]).
{232894309,
18140143309611363532953342430693354584669635033709097929462505366714035156593135818380467866054222964635144914854949550271375442721368122191972041094311075107507067573147191502194201568268202614781694681859513649083616294200541611489469967999559505365172812095568020073934100699850397033005903158113691518456912149989919601385875227049401605594538145621585911726469930727034807205200195312500}
</pre>
So a bit less than 4 minutes to get the 100 000 000th regular number. The complexity is slightly worse than linear which is not a surprise given than all the regular numbers are computed.
=={{header|ERRE}}==
For bigger numbers, you have to use an external program, like MULPREC.R
<syntaxhighlight lang="erre">PROGRAM HAMMING
!$DOUBLE
Line 4,646 ⟶ 4,766:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Hamming_numbers}}
'''Solution'''
[[File:Fōrmulæ - Hamming numbers 01.png]]
'''Case 1.''' First twenty Hamming numbers
[[File:Fōrmulæ - Hamming numbers 02.png]]
[[File:Fōrmulæ - Hamming numbers 03.png]]
'''Case 2.''' 1691-st Hamming number
[[File:Fōrmulæ - Hamming numbers 04.png]]
[[File:Fōrmulæ - Hamming numbers 05.png]]
'''Case 3.''' One million-th Hamming number
[[File:Fōrmulæ - Hamming numbers 06.png]]
[[File:Fōrmulæ - Hamming numbers 07.png]]
=={{header|Go}}==
Line 6,681 ⟶ 6,819:
Took 381 milliseconds for the last.</pre>
Run on a AMD Bulldozer FX8120 3.1 GHz which is about half the speed as an equivalent Intel (but also half the price).
=={{header|Lambdatalk}}==
===1) recursive version===
<syntaxhighlight lang="scheme">
{def hamming
{def hamming.loop
{lambda {:h :a :i :b :j :c :k :m :n}
{if {>= :n :m}
then {A.last :h}
else {let { {:h {A.set! :n {min :a :b :c} :h}}
{:a :a} {:i :i}
{:b :b} {:j :j}
{:c :c} {:k :k}
{:m :m} {:n :n}
} {hamming.loop :h
{if {= :a {A.get :n :h}}
then {* 2 {A.get {+ :i 1} :h}} {+ :i 1}
else :a :i}
{if {= :b {A.get :n :h}}
then {* 3 {A.get {+ :j 1} :h}} {+ :j 1}
else :b :j}
{if {= :c {A.get :n :h}}
then {* 5 {A.get {+ :k 1} :h}} {+ :k 1}
else :c :k}
:m
{+ :n 1} }
}}}}
{lambda {:n}
{hamming.loop {A.new {S.serie 1 :n}} 2 0 3 0 5 0 :n 1}
}}
-> hamming
{S.map hamming {S.serie 1 20}}
-> 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
{hamming 1691}
-> 2125764000 // < 200ms
Currently limited to javascript's integers and by stackoverflow on some computers.
</syntaxhighlight>
===2) iterative version===
Build a table of 2^i•3^j•5^k from i,j,k = 0 to n and sort it.
===2.1) compute===
<syntaxhighlight lang="scheme">
{def ham
{lambda {:n}
{S.sort <
{S.map {{lambda {:n :i}
{S.map {{lambda {:n :i :j}
{S.map {{lambda {:i :j :k}
{* {pow 2 :i} {pow 3 :j} {pow 5 :k}}} :i :j}
{S.serie 0 :n} } } :n :i}
{S.serie 0 :n} } } :n}
{S.serie 0 :n} }
}}}
-> ham
{def H {ham 30}}
-> H
{S.slice 0 19 {H}}
-> 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
{S.get 1690 {H}}
-> 2125764000 // on my macbook pro
</syntaxhighlight>
===2.2) display===
Display a hamming number as 2<sup>a</sup>•3<sup>b</sup>•5<sup>c</sup>
<syntaxhighlight lang="scheme">
{def factor
{def factor.r
{lambda {:n :i}
{if {> :i :n}
then
else {if {= {% :n :i} 0}
then :i {factor.r {/ :n :i} :i}
else {factor.r :n {+ :i 1}} }}}}
{lambda {:n}
:n is the product of 1 {factor.r :n 2} }}
-> factor
{def asproductofpowers
{def asproductofpowers.loop
{lambda {:a :b :c :n}
{if {= {S.first :n} 1}
then 2{sup :a}•3{sup :b}•5{sup :c}
else {asproductofpowers.loop
{if {= {S.first :n} 2} then {+ :a 1} else :a}
{if {= {S.first :n} 3} then {+ :b 1} else :b}
{if {= {S.first :n} 5} then {+ :c 1} else :c}
{W.rest :n} }
}}}
{lambda {:n}
{asproductofpowers.loop 0 0 0 {S.reverse :n}}}}
-> asproductofpowers
{factor 2125764000}
-> 2125764000 is the product of 1 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 5 5 5
{asproductofpowers {factor 2125764000}}
-> 2^5•3^12•5^3
{S.map {lambda {:i} {div}:i: {S.get :i {H}} =
{asproductofpowers {factor {S.get :i {H}}}}}
{S.serie 0 19}}
->
0: 1 = 2^0•3^0•5^0
1: 2 = 2^1•3^0•5^0
2: 3 = 2^0•3^1•5^0
3: 4 = 2^2•3^0•5^0
4: 5 = 2^0•3^0•5^1
5: 6 = 2^1•3^1•5^0
6: 8 = 2^3•3^0•5^0
7: 9 = 2^0•3^2•5^0
8: 10 = 2^1•3^0•5^1
9: 12 = 2^2•3^1•5^0
10: 15 = 2^0•3^1•5^1
11: 16 = 2^4•3^0•5^0
12: 18 = 2^1•3^2•5^0
13: 20 = 2^2•3^0•5^1
14: 24 = 2^3•3^1•5^0
15: 25 = 2^0•3^0•5^2
16: 27 = 2^0•3^3•5^0
17: 30 = 2^1•3^1•5^1
18: 32 = 2^5•3^0•5^0
19: 36 = 2^2•3^2•5^0
</syntaxhighlight>
See http://lambdaway.free.fr/lambdawalks/?view=hamming_numbers3 for a better display as 2<sup>a</sup>•3<sup>b</sup>•5<sup>c</sup>.
=={{header|Liberty BASIC}}==
Line 6,947 ⟶ 7,229:
disp(powers_235(1:20))
disp(powers_235(1691))</syntaxhighlight>
=={{header|Mojo}}==
Since current Mojo (version 0.7) does not have many forms of recursive expression, the below is an imperative version of the First In Last Out (FILO) Queue version of the fastest iterative Nim version using logarithmic approximations for the comparison and final conversion of the power tuples to a big integer output. Since Mojo does not currently have a big integer library, enough of the required functionality of one (multiplication and conversion to string) is implemented in the following code:
{{trans|Nim}}
<syntaxhighlight lang="mojo">from collections.vector import (DynamicVector, CollectionElement)
from math import (log2, trunc, pow)
from memory import memset_zero #, memcpy)
from time import now
alias cCOUNT: Int = 1_000_000
struct BigNat(Stringable): # enough just to support conversion and printing
''' Enough "infinite" precision to support as required here - multiply and
divide by 10 conversion to string...
'''
var contents: DynamicVector[UInt32]
fn __init__(inout self):
self.contents = DynamicVector[UInt32]()
fn __init__(inout self, val: UInt32):
self.contents = DynamicVector[UInt32](4)
self.contents.resize(1, val)
fn __copyinit__(inout self, existing: Self):
self.contents = existing.contents
fn __moveinit__(inout self, owned existing: Self):
self.contents = existing.contents^
fn __str__(self) -> String:
var rslt: String = ""
var v = self.contents
while len(v) > 0:
var t: UInt64 = 0
for i in range(len(v) - 1, -1, -1):
t = ((t << 32) + v[i].to_int())
v[i] = (t // 10).to_int(); t -= v[i].to_int() * 10
var sz = len(v) - 1
while sz >= 0 and v[sz] == 0: sz -= 1
v.resize(sz + 1, 0)
rslt = str(t) + rslt
return rslt
fn mult(inout self, mltplr: Self):
var rslt = DynamicVector[UInt32]()
rslt.resize(len(self.contents) + len(mltplr.contents), 0)
for i in range(len(mltplr.contents)):
var t: UInt64 = 0
for j in range(len(self.contents)):
t += self.contents[j].to_int() * mltplr.contents[i].to_int() + rslt[i + j].to_int()
rslt[i + j] = (t & 0xFFFFFFFF).to_int(); t >>= 32
rslt[i + len(self.contents)] += t.to_int()
var sz = len(rslt) - 1
while sz >= 0 and rslt[sz] == 0: sz -= 1
rslt.resize(sz + 1, 0); self.contents = rslt
alias lb2: Float64 = 1.0
alias lb3: Float64 = log2[DType.float64, 1](3.0)
alias lb5: Float64 = log2[DType.float64, 1](5.0)
@value
struct LogRep(CollectionElement, Stringable):
var logrep: Float64
var x2: UInt32
var x3: UInt32
var x5: UInt32
fn __del__(owned self): return
@always_inline
fn mul2(self) -> Self:
return LogRep(self.logrep + lb2, self.x2 + 1, self.x3, self.x5)
@always_inline
fn mul3(self) -> Self:
return LogRep(self.logrep + lb3, self.x2, self.x3 + 1, self.x5)
@always_inline
fn mul5(self) -> Self:
return LogRep(self.logrep + lb5, self.x2, self.x3, self.x5 + 1)
fn __str__(self) -> String:
var rslt = BigNat(1)
fn expnd(inout rslt: BigNat, bs: UInt32, n: UInt32):
var bsm = BigNat(bs); var nm = n
while nm > 0:
if (nm & 1) != 0: rslt.mult(bsm)
bsm.mult(bsm); nm >>= 1
expnd(rslt, 2, self.x2); expnd(rslt, 3, self.x3); expnd(rslt, 5, self.x5)
return str(rslt)
alias oneLR: LogRep = LogRep(0.0, 0, 0, 0)
alias LogRepThunk = fn() escaping -> LogRep
fn hammingsLogImp() -> LogRepThunk:
var s2 = DynamicVector[LogRep](); var s3 = DynamicVector[LogRep](); var s5 = oneLR; var mrg = oneLR
s2.resize(512, oneLR); s2[0] = oneLR.mul2(); s3.resize(1, oneLR); s3[0] = oneLR.mul3()
# var s2p = s2.steal_data(); var s3p = s3.steal_data()
var s2hdi = 0; var s2tli = -1; var s3hdi = 0; var s3tli = -1
@always_inline
fn next() escaping -> LogRep:
var rslt = s2[s2hdi]
var s2len = len(s2)
s2tli += 1;
if s2tli >= s2len:
s2tli = 0
if s2hdi == s2tli:
if s2len < 1024:
s2.resize(1024, oneLR)
else:
s2.resize(s2len + s2len, oneLR) # ; s2p = s2.steal_data()
for i in range(s2hdi):
s2[s2len + i] = s2[i]
# memcpy[UInt8, 0](s2p + s2len, s2p, sizeof[LogRep]() * s2hdi)
s2tli += s2len; s2len += s2len
if rslt.logrep < mrg.logrep:
s2hdi += 1
if s2hdi >= s2len:
s2hdi = 0
else:
rslt = mrg
var s3len = len(s3)
s3tli += 1;
if s3tli >= s3len:
s3tli = 0
if s3hdi == s3tli:
if s3len < 1024:
s3.resize(1024, oneLR)
else:
s3.resize(s3len + s3len, oneLR) # ; s3p = s3.steal_data()
for i in range(s3hdi):
s3[s3len + i] = s3[i]
# memcpy[UInt8, 0](s3p + s3len, s3p, sizeof[LogRep]() * s3hdi)
s3tli += s3len; s3len += s3len
if mrg.logrep < s5.logrep:
s3hdi += 1
if s3hdi >= s3len:
s3hdi = 0
else:
s5 = s5.mul5()
s3[s3tli] = rslt.mul3(); let t = s3[s3hdi];
mrg = t if t.logrep < s5.logrep else s5
s2[s2tli] = rslt.mul2(); return rslt
return next
fn main():
print("The first 20 Hamming numbers are:")
var f = hammingsLogImp();
for i in range(20): print_no_newline(f(), " ")
print()
f = hammingsLogImp(); var h: LogRep = oneLR
for i in range(1691): h = f()
print("The 1691st Hamming number is", h)
let strt: Int = now()
f = hammingsLogImp()
for i in range(cCOUNT): h = f()
let elpsd = (now() - strt) / 1000
print("The " + str(cCOUNT) + "th Hamming number is:")
print("2**" + str(h.x2) + " * 3**" + str(h.x3) + " * 5**" + str(h.x5))
let lg2 = lb2 * Float64(h.x2.to_int()) + lb3 * Float64(h.x3.to_int()) + lb5 * Float64(h.x5.to_int())
let lg10 = lg2 / log2(Float64(10))
let expnt = trunc(lg10); let num = pow(Float64(10.0), lg10 - expnt)
let apprxstr = str(num) + "E+" + str(expnt.to_int())
print("Approximately: ", apprxstr)
let answrstr = str(h)
print("The result has", len(answrstr), "digits.")
print(answrstr)
print("This took " + str(elpsd) + " microseconds.")</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 1691st Hamming number is 2125764000
The 1000000th Hamming number is:
2**55 * 3**47 * 5**64
Approximately: 5.1931278110620553E+83
The result has 84 digits.
519312780448388736089589843750000000000000000000000000000000000000000000000000000000
This took 3626.192 microseconds.</pre>
The above was as run on an AMD 7840HS CPU single-thread boosted to 5.1 GHz. It is about the same speed as the Nim version from which it was translated.
=={{header|MUMPS}}==
Line 7,992 ⟶ 8,451:
This is a basic implementation; finding the millionth term requires 1 second and 54 MB. Much better algorithms exist.
<syntaxhighlight lang="parigp">Hupto(n)={
my(
for(m=2,n,
if(
if(
if(
);
};
H(n)=Hupto(n)[n];
Line 8,730 ⟶ 9,188:
3 elemcount 1209 out of 1236
5 elemcount 1 out of 2
...
change zu use 12 primes [2..37] ( 32 bit ) -> 2.2x runtime over using 3 primes
Line 8,751 ⟶ 9,210:
31 elemcount 15 out of 17
37 elemcount 1 out of 2
@home:
//tested til 1E12 with 4.4 Ghz 5600G Free Pascal Compiler version 3.2.2-[2022/11/22] for x86_64
Timed 1,000,000,000,000 in 57:53.015
ln 19444.3672890 2^1126 3^16930 5^40 -> see Haskell-Version [https://ideone.com/RnAh5X]
Actual Index 1000075683108
ln 19444.3672890 2^8295 3^2426 5^6853
2 elemcount 106935365 out of 156797362
3 elemcount 12083 out of 12969
5 elemcount 1 out of 2
user 57m51.015s <<
sys 0m1.616s
</pre>
Line 9,380 ⟶ 9,851:
The original author is Raymond Hettinger and the code was first published [http://code.activestate.com/recipes/576961/ here] under the MIT license. Uses iterators dubbed "cyclical" in a sense that they are referring back (explicitly, with <code>p2, p3, p5</code> iterators) to the previously produced values, same as the above versions (through indices into shared storage) and the classic [[#Haskell|Haskell]] version (implicitly timed by lazy evaluation).
Memory is efficiently maintained automatically by the <code>tee</code> function for each of the three generator expressions, i.e. only that much is maintained as needed to produce the next value (although, for Python versions older than 3.6 it looks like the storage is not shared so three copies are maintained implicitly there -- whereas for 3.6 and up the storage <i>is</i> shared between the returned iterators, so only a single underlying FIFO queue is maintained, according to the [https://docs.python.org/3.6/library/itertools.html#itertools.tee documentation]).
<syntaxhighlight lang="python">from itertools import tee, chain, groupby, islice
from heapq import merge
Line 9,467 ⟶ 9,938:
print hamming(1691)[0]
print hamming(1000000)[0]</syntaxhighlight>
=={{header|QBasic}}==
{{works with|QBasic|1.1}}
Line 9,906 ⟶ 10,377:
h(20) = 36
h(1691) = 2125764000
</pre>
=={{header|RPL}}==
RPL does not provide any multi-precision capability, so only parts 1 and 2 of the task can be implemented.
Using global variables <code>In</code> and <code>Xn</code> avoids stack acrobatics that would have made the code slower and unintelligible, despite the ugly <code> 'var_name' STO</code> syntax inherited from vintage HP calculators.
≪ 1 ‘I2’ STO 1 ‘I3’ STO 1 ‘I5’ STO 2 ‘X2’ STO 3 ‘X3’ STO 5 ‘X5’ STO
{ 1 } 1 ROT 1 - '''FOR''' n
X2 X3 MIN X5 MIN
SWAP OVER + SWAP
'''IF''' X2 OVER == '''THEN''' 1 ‘I2’ STO+ OVER I2 GET 2 * ‘X2’ STO '''END'''
'''IF''' X3 OVER == '''THEN''' 1 ‘I3’ STO+ OVER I3 GET 3 * ‘X3’ STO '''END'''
'''IF''' X5 == '''THEN''' 1 ‘I5’ STO+ DUP I5 GET 5 * ‘X5’ STO '''END'''
'''NEXT'''
≫ 'HAMM' STO
20 HAMM
1691 HAMM DUP SIZE GET
{{out}}
<pre>
2: { 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 }
1: 2125764000
</pre>
Line 11,839 ⟶ 12,332:
=={{header|UNIX Shell}}==
{{works with|ksh93}}
{{works with|Bourne Again SHell|4+}}
Large numbers are not supported.
<syntaxhighlight lang="bash">
typeset -a hamming=(1) q2 q3 q5
function nextHamming {
typeset -
q2+=( $(( h*2 )) )
q3+=( $(( h*3 )) )
Line 11,855 ⟶ 12,349:
function ashift {
ary=( "${ary[@]:1}" )
}
Line 11,862 ⟶ 12,356:
function min3 {
if (( $1 < $2 )); then
(( $1 < $3 )) &&
else
(( $2 < $3 )) &&
fi
}
Line 11,870 ⟶ 12,364:
for ((i=1; i<=20; i++)); do
nextHamming
printf
done
for ((; i<=1690; i++)); do nextHamming; done
nextHamming
printf
</syntaxhighlight>
{{out}}
Line 12,162 ⟶ 12,657:
</pre>
=={{header|V (Vlang)}}==
{{trans|go}}
===Concise version using dynamic-programming===
<syntaxhighlight lang="v (vlang)">import math.big
fn min(a big.Integer, b big.Integer) big.Integer {
Line 12,211 ⟶ 12,706:
===Fast version with no duplicates algorithm using arrays for memoization and logarithmic approximations===
The V (Vlang) language isn't yet stable enough (version 0.30) to support a fully functional version using generic lazy lists as per the Haskell language versions and in truth is mostly an imperative language anyway; however, it already can do the page task very quickly with a more imperative algorithm using arrays for memoization storage and logarithmic approximations for sorting comparisons to avoid "infinite" precision integer calculations except for the final result values, as per the following code, which is Nim's "ring buffer" version as that is faster due to less copying required:
{{trans|Nim}}
<syntaxhighlight lang="v (vlang)">// compile with: v -cflags -march=native -cflags -O3 -prod
import time
Line 12,279 ⟶ 12,774:
struct HammingsLog {
mut:
s3 []LogRep = []LogRep { len: 1024, cap: 1024 }
s5 LogRep = one.mul5()
mrg LogRep = one.mul3()
s3hdi int
s3nxti int
}
[direct_array_access][inline]
fn (mut hl HammingsLog) next() ?LogRep {
if rsltp.lg < hl.mrg.lg {
hl.
hl.s2hdi &= hl.s2msk
} else {
mut rslt := hl.mrg
rsltp = &rslt
hl.s3[hl.s3nxti] =
s3hdp := &hl.s3[hl.s3hdi]
if unsafe { s3hdp.lg < hl.s5.lg } {
hl.mrg = *s3hdp
hl.s3hdi++
hl.s3hdi &= hl.s3msk
} else {
hl.s5 = hl.s5.mul5()
hl.s3nxti++
hl.s3nxti &= hl.s3msk
if hl.s3nxti == hl.s3hdi { // buffer full: grow it
sz := hl.s3msk + 1
hl.s3msk = sz + sz
unsafe { hl.s3.grow_len(sz) }
hl.s3msk--
if hl.s3hdi == 0 {
hl.s3nxti = sz
} else {
unsafe { vmemcpy(&hl.s3[hl.s3hdi + sz], &hl.s3[hl.s3hdi],
int(sizeof(LogRep)) * (sz - hl.s3hdi)) }
hl.s3hdi += sz
}
}
}
hl.s2nxti++
hl.s2nxti &= hl.s2msk
if hl.s2nxti == hl.s2hdi { // buffer full: grow it
sz := hl.s2msk + 1
hl.s2msk = sz + sz
unsafe { hl.s2.grow_len(sz) }
hl.s2msk--
if hl.s2hdi == 0 {
hl.s2nxti = sz
} else {
unsafe { vmemcpy(&hl.s2[hl.s2hdi + sz], &hl.s2[hl.s2hdi],
int(sizeof(LogRep)) * (sz - hl.s2hdi)) }
hl.s2hdi += sz
}
}
Line 12,368 ⟶ 12,872:
2125764000
519312780448388736089589843750000000000000000000000000000000000000000000000000000000
Above result for 1000000 elements in
The above result is as computed on an Intel i5-6500 at 3.6 GHz (single-threaded, boosted); the execution time is somewhat variable due to V currently using Garbage Collection by default, but the intention is to eventually use automatic reference counting by default which should make it slightly faster and more consistent other than for any variations caused by the memory allocator. The above version can calculate the billionth Hamming number in about 5.3 seconds.
===Extremely fast version inserting values into the error band and using logarithmic approximations for sorting===
Line 12,377 ⟶ 12,879:
The above code is about as fast as one can go generating sequences/iterations; however, if one is willing to forego sequences/iterations and just calculate the nth Hamming number (repeatedly when a sequence is desired, but that is only for the first required task of three and then only for a trivial range), then some reading on the relationship between the size of numbers to the sequence numbers is helpful (Wikipedia: Regular Number). One finds that there is a very distinct relationship and that it quite quickly reduces to quite a small error band proportional to the log of the output value for larger ranges. Thus, the following code just scans for logarithmic representations to insert into a sequence for this top error band and extracts the correct nth representation from that band. It reduces time complexity to O(n^(2/3)) from O(n) for the sequence versions, but even more amazingly, reduces memory requirements to O(n^(1/3)) from O(n^(2/3)) and thus makes it possible to calculate very large values in the sequence on common personal computers. This version uses a multi-precision integer as the representation of the logarithmic approximation of the value for sorting of the error band to extend the precision for accurate results up to almost the 64-bit number range (in about a day on common desktop computers). The code is as follows:
{{trans|Nim}}
<syntaxhighlight lang="v (vlang)">// compile with: v -cflags -march=native -cflags -O3 -prod HammingsLog.v
import time
Line 12,486 ⟶ 12,988:
=={{header|Wren}}==
===Simple but slow===
{{libheader|Wren-big}}
<syntaxhighlight lang="wren">import "./big" for BigInt, BigInts
var primes = [2, 3, 5].map { |p| BigInt.new(p) }.toList
Line 12,531 ⟶ 13,033:
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="wren">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>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">func Hamming(N); \Return 'true' if N is a Hamming number
int N;
[if N = 1 then return true;
if rem(N/2) = 0 then return Hamming(N/2);
if rem(N/3) = 0 then return Hamming(N/3);
if rem(N/5) = 0 then return Hamming(N/5);
return false;
];
int N, C;
[N:= 1; C:= 0;
loop [if Hamming(N) then
[C:= C+1;
IntOut(0, N); ChOut(0, ^ );
if C >= 20 then quit;
];
N:= N+1;
];
CrLf(0);
N:= 1<<31; \ 8-)
repeat N:= N-1 until Hamming(N);
IntOut(0, N);
]</syntaxhighlight>
{{out}}
<pre>
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
2125764000</pre>
=={{header|Yabasic}}==
Line 12,544 ⟶ 13,161:
sub hamming(limit)
local x2,
x3,x5,i,j,k,n
h(0) =1
| |||