Hamming numbers: Difference between revisions
Added Easylang
GordonBGood (talk | contribs) m (→{{header|Elm}}: correct "off by one" error...) |
(Added Easylang) |
||
| (4 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 4,696 ⟶ 4,767:
{{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,136 ⟶ 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,720 ⟶ 12,990:
===Simple but slow===
{{libheader|Wren-big}}
<syntaxhighlight lang="
var primes = [2, 3, 5].map { |p| BigInt.new(p) }.toList
Line 12,773 ⟶ 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
| |||