Hamming numbers: Difference between revisions
Added Easylang
(Added XPL0 example.) |
(Added Easylang) |
||
| (7 intermediate revisions by 4 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 alias Model = List String
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}}==
Line 4,707 ⟶ 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 7,152 ⟶ 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 12,736 ⟶ 12,990:
===Simple but slow===
{{libheader|Wren-big}}
<syntaxhighlight lang="
var primes = [2, 3, 5].map { |p| BigInt.new(p) }.toList
Line 12,789 ⟶ 13,043:
Not as fast as the statically typed languages but fast enough for me :)
<syntaxhighlight lang="
import "./long" for ULong
import "./big" for BigInt
| |||