1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
discard """
cmd: "nim c --gc:orc -d:nimThinout -r $file"
output: '''The first 20 hammings are: 1 2 3 4 5 MEM IS 0'''
"""
# test Nim Hamming Number Lazy List algo with reference counts and not...
# compile with "-d:release -d:danger" and test with various
# memory managment GC's, allocators, threading, etc.
from times import epochTime
from math import log2
# implement our own basic BigInt so the bigints library isn't necessary...
type
BigInt = object
digits: seq[uint32]
let zeroBigInt = BigInt(digits: @[ 0'u32 ])
let oneBigInt = BigInt(digits: @[ 1'u32 ])
proc shladd(bi: var BigInt; n: int; a: BigInt) =
var cry = 0'u64
for i in 0 ..< min(bi.digits.len, a.digits.len):
cry += (bi.digits[i].uint64 shl n) + a.digits[i].uint64
bi.digits[i] = cry.uint32
cry = cry shr 32
if cry > 0'u64:
bi.digits.add cry.uint32
proc `$`(x: BigInt): string =
if x.digits.len == 0 or (x.digits.len == 1 and x.digits[0] == 0'u32):
return "0"
var n = x
var msd = n.digits.high
result = ""
while msd >= 0:
if n.digits[msd] == 0'u32: msd.dec; continue
var brw = 0.uint64
for i in countdown(msd, 0):
let dvdnd = n.digits[i].uint64 + (brw shl 32)
let q = dvdnd div 10'u64; brw = dvdnd - q*10'u64; n.digits[i] = q.uint32
result &= $brw
for i in 0 .. result.high shr 1:
let tmp = result[^(i + 1)]
result[^(i + 1)] = result[i]
result[i] = tmp
proc convertTrival2BigInt(tpl: (uint32, uint32, uint32)): BigInt =
result = oneBigInt
let (x2, x3, x5) = tpl
for _ in 1 .. x2: result.shladd 1, zeroBigInt
for _ in 1 .. x3: result.shladd 1, result
for _ in 1 .. x5: result.shladd 2, result
type LogRep = (float64, (uint32, uint32, uint32))
type LogRepf = proc(x: LogRep): LogRep
const one: LogRep = (0.0f64, (0u32, 0u32, 0u32))
proc `<`(me: LogRep, othr: LogRep): bool = me[0] < othr[0]
const lb2 = 1.0'f64
const lb3 = 3.0'f64.log2
const lb5 = 5.0'f64.log2
proc mul2(me: LogRep): LogRep =
let (lr, tpl) = me; let (x2, x3, x5) = tpl
(lr + lb2, (x2 + 1, x3, x5))
proc mul3(me: LogRep): LogRep =
let (lr, tpl) = me; let (x2, x3, x5) = tpl
(lr + lb3, (x2, x3 + 1, x5))
proc mul5(me: LogRep): LogRep =
let (lr, tpl) = me; let (x2, x3, x5) = tpl
(lr + lb5, (x2, x3, x5 + 1))
type
LazyList = ref object
hd: LogRep
tlf: proc(): LazyList {.closure.}
tl: LazyList
proc rest(ll: LazyList): LazyList = # not thread-safe; needs lock on thunk
if ll.tlf != nil:
ll.tl = ll.tlf()
ll.tlf = nil
ll.tl
iterator hamming(until: int): (uint32, uint32, uint32) =
proc merge(x, y: LazyList): LazyList =
let xh = x.hd
let yh = y.hd
if xh < yh: LazyList(hd: xh, tlf: proc(): auto = merge x.rest, y)
else: LazyList(hd: yh, tlf: proc(): auto = merge x, y.rest)
proc smult(mltf: LogRepf; s: LazyList): LazyList =
proc smults(ss: LazyList): LazyList =
LazyList(hd: ss.hd.mltf, tlf: proc(): auto = ss.rest.smults)
s.smults
proc unnsm(s: LazyList, mltf: LogRepf): LazyList =
var r: LazyList = nil
let frst = LazyList(hd: one, tlf: proc(): LazyList = r)
r = if s == nil: smult mltf, frst else: s.merge smult(mltf, frst)
r
var hmpll: LazyList = ((nil.unnsm mul5).unnsm mul3).unnsm mul2
# var hmpll: LazyList = nil; for m in [mul5, mul3, mul2]: echo one.m # ; hmpll = unnsm(hmpll, m)
yield one[1]
var cnt = 1
while hmpll != nil:
yield hmpll.hd[1]
hmpll = hmpll.rest # almost forever
cnt.inc
if cnt > until: break
#when declared(thinout):
thinout(hmpll)
proc main =
stdout.write "The first 20 hammings are: "
for h in hamming(4):
write stdout, h.convertTrival2BigInt, " "
for h in hamming(200):
discard h.convertTrival2BigInt
let mem = getOccupiedMem()
main()
echo "MEM IS ", getOccupiedMem() - mem
#[
result = (smults, :envP.:up)(rest(:envP.ss2))
proc anon =
var
:tmpD_284230
:tmpD_284233
:tmpD_284236
try:
`=sink_283407`(result_283502,
`=sink_283927`(:tmpD_284236, (smults_283495,
wasMoved_284234(:tmpD_284233)
`=_284014`(:tmpD_284233, :envP_283898.:up_283899)
:tmpD_284233))
:tmpD_284236(
`=sink_283407`(:tmpD_284230, rest_283366(:envP_283898.ss2_-283497))
:tmpD_284230))
finally:
`=destroy_283914`(:tmpD_284236)
`=destroy_283388`(:tmpD_284230)
proc smuls(ss: LazyList_283350; :envP_283891): LazyList_283350 =
var :env_283913
try:
`=destroy_283951`(:env_283913)
internalNew_43643(:env_283913)
`=_283401`(:env_283913.ss2_-283497, ss_283497)
:env_283913.:up_283899 = :envP_283891
`=sink_283407`(result_283498, LazyList_283350(hd_283353: :envP_283891.mltf1_-283492(
:env_283913.ss2_-283497.hd_283353), tlf_283356: (:anonymous_283499,
let blitTmp_284227 = :env_283913
wasMoved_284228(:env_283913)
blitTmp_284227)))
finally:
`=destroy_283951`(:env_283913)
proc smul =
var
:env_283969
:tmpD_284220
try:
`=destroy_284008`(:env_283969)
internalNew_43643(:env_283969)
`=_283976`(:env_283969.mltf1_-283492, mltf_283492)
proc smults(ss: LazyList_283350; :envP_283891): LazyList_283350 =
result_283498 = LazyList_283350(hd_283353: mltf_283492(ss_283497.hd_283353), tlf_283356: proc (
:envP_283898): auto_43100 = result_283502 = smults_283495(rest_283366(ss_283497)))
`=sink_283407`(result_283494,
`=sink_283927`(:tmpD_284220, (smults_283495,
let blitTmp_284218 = :env_283969
wasMoved_284219(:env_283969)
blitTmp_284218))
:tmpD_284220(s_283493))
finally:
`=destroy_283914`(:tmpD_284220)
`=destroy_284008`(:env_283969)
]#
|