Talk:Hamming numbers: Difference between revisions
→Original DrDobbs blog discussion: the DDJ link not dead anymore
(→Original DrDobbs blog discussion: upd link) |
(→Original DrDobbs blog discussion: the DDJ link not dead anymore) |
||
| (10 intermediate revisions by 6 users not shown) | |||
Line 1:
==a list of references to add ...==
I have a list of references to add, plus another one or two Python algorithms. --[[User:Paddy3118|Paddy3118]] 18:40, 2 December 2009 (UTC)
:Done. --[[User:Paddy3118|Paddy3118]] 21:55, 2 December 2009 (UTC)
Line 74 ⟶ 75:
Just for the record, I would like to reclaim authorship of that snippet of pseudocode from the DDJ discussion back then, quoted in the Python section that apparently started this whole page. :) No consequences other than to state it here for the record - that link is broken now, gone dead after DDJ moved their blog system to some "new implementation with new and exciting features" which included losing all the old contents apparently.
::: update: https://www.drdobbs.com/architecture-and-design/hamming-problem/228700538 not dead anymore. (web.archive.org has a copy, as well). [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 20:14, 13 May 2020 (UTC)
Two interesting related observations. One, very minor, I can now explain the spaces in <code>x2=2*h[ i ];</code> in the quoted pseudo-code: the old blog system at DDJ would interpret [i] ... [/i] as markers for ''italics''. Another - for me, somewhat major - is that while I came out with that pseudo-code trying to translate the classic ''Haskell'' merging-the-mappings code back into something C-like in my mind, as it turns out, it is in ''almost exact verbatim correspondence'' with the original Edsger Dijkstra's code in his book (IIRC), which I stumbled upon much later, by chance. (I had a link to it somewhere, will add later.) Amazing how it came back in an almost exact loop, this idea, back to where it started - "to Haskell and back!". Interesting... :) [[User:WillNess|WillNess]] 21:06, 20 August 2012 (UTC)▼
▲Two interesting related observations. One, very minor, I can now explain the spaces in <code>x2=2*h[ i ];</code> in the quoted pseudo-code: the old blog system at DDJ would interpret [i] ... [/i] as markers for ''italics''. Another - for me, somewhat major - is that while I came
:Thanks for the original inspiration :-)<br>--[[User:Paddy3118|Paddy3118]] 21:41, 20 August 2012 (UTC)
::Thank ''you'' for getting inspired and making this page happen! :) The book in question is Edsger Dijkstra, "A Discipline of Programming", Prentice-Hall, [http://web.cecs.pdx.edu/~cs410aph/Lectures/Smalltalk%20II/Dijkstra%20on%20Hamming's%20Problem.pdf chap. 17 "An Exercise Attributed to R.W.Hamming"], [http://i.imgur.com/tPygG.gif pg. 132]. -- [[User:WillNess|WillNess]] 17:40, 29 August 2012 (UTC)
== "Cyclic generator variant #1" not efficient ==
The Python [[Hamming numbers#Cyclic generator variant #1.|Cyclic generator variant #1.]] that is said to be much simpler, is not really equivalent to the other solutions. I compared it to another version, measuring how many times the <code>merge</code> iterator is advanced:
<lang python>from itertools import tee, chain, groupby, islice
import heapq
count = 0
def merge(*args):
global count
for x in heapq.merge(*args):
count += 1
yield x
def raymonds_hamming():
# Generate "5-smooth" numbers, also called "Hamming numbers"
# or "Regular numbers". See: http://en.wikipedia.org/wiki/Regular_number
# Finds solutions to 2**i * 3**j * 5**k for some integers i, j, and k.
def deferred_output():
for i in output:
yield i
result, p2, p3, p5 = tee(deferred_output(), 4)
m2 = (2*x for x in p2) # multiples of 2
m3 = (3*x for x in p3) # multiples of 3
m5 = (5*x for x in p5) # multiples of 5
merged = merge(m2, m3, m5)
combined = chain([1], merged) # prepend a starting point
output = (k for k,g in groupby(combined)) # eliminate duplicates
return result
print list(islice(raymonds_hamming(), 100))
print count</lang>
<lang python>from itertools import tee, chain, groupby, islice
import heapq
count = 0
def merge(*args):
global count
for x in heapq.merge(*args):
count += 1
yield x
def hamming_numbers():
last = 1
yield last
a,b,c = tee(hamming_numbers(), 3)
for n in merge((2*i for i in a), (3*i for i in b), (5*i for i in c)):
if n != last:
yield n
last = n
print list(islice(hamming_numbers(), 100))
print count</lang>
The results I get:
{| class="wikitable"
|-
! number of items printed !! raymonds_hamming !! hamming_numbers
|-
| 20 || 28 || 59
|-
| 100 || 201 || 670
|-
| 1,000 || 2,506 || 17,822
|-
| 10,000 || 27,634 || 420,168
|-
| 100,000 || 288,851 || 9,429,734
|}
The new "Cyclic generator variant #1" version seems to be much, much worse. --[[User:Spoon!|Spoon!]] 20:52, 12 October 2012 (UTC)
: The '#1' variant is indeed doing something completely different. Original code's <code>tee()</code> creates multiple copies of a generator, but does this exactly once per <code>raymonds_hamming()</code> call. The '#1' variant is actually recursive: caller calls <code>hamming_number()</code>, which in turn calls <code>tee()</code> and creates copies ... which unfortunately calls <code>hamming_number()</code> again with a new closure, which calles <code>tee()</code> and makes new sets of copies, recursively. Either the author on programmingpraxis site misunderstood how <code>tee()</code> works, or he simply wanted brevity (much) more than efficiency. --[[User:Ledrug|Ledrug]] 03:19, 13 October 2012 (UTC)
== Captha unusable ==
I've been spending over ten attempts to correct an error at the Fortran module, but neither listening nor reading helped a bit.
So I can't add this link again at Fortran, sorry: //fortran.com/big_integer_module.f95
This way the whole darn thing is pretty much counterproductive.
: It's not just you. I've been having problems with captha also. One of the manifestations is that captha arrives on the scene, but it doesn't show me the two fuzzy words. So I click on the audio clues, which are totally worthless (or should I say maaaaarrr cwooooorrrrthleeeesssss...), but then I click on the big '''T''' (for text), and sometimes it then gives me two fuzzy words. If not, I ask for two more (different) fuzzy words, and repeat the cycle over (and over and over and over) again until captha thinks I get it right, either that, captha gets tired of me ... I don't know. Captha acts like an imp or a gremlin really interested in frustrating programmers. Also, if you get a couple of fuzzy words that you correctly answered previously, it will now fail, which is really, really frustrating. I think captha has a mean wicked sense of humor, and it's just screwing with ya. If you get a couple of fuzzy words that you're responded to (correctly or "incorrectly"), ignore them and ask for two other (new) fuzzy words. Don't waste your time if you KNOW the answer (from a previous attempt). It doesn't matter, the answer(s) will be rejected and most of the time, it presents a new pair of fuzzy words (or maybe not). If I were high on something, this could be construed as entertainment, playing Russian roulette with fuzzy words. Hitting your head with a hammer is much more fun, plus it feels soooooo good when you stop. If I sound too sarcastic, it's because I wasted over an hour today ... probably my fault, I entered a whole mess of stuff, and I didn't want all my editing to go down the toilet without a fight. I won, but a lot of hair got pulled out, and I don't have that much to spare. Perhaps someone should start a Village Pump dialogue? -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 22:02, 18 March 2014 (UTC)
: I forgot to say that this happens using Microsoft Windows Internet Explorer, or my main squeeze, Firefox Aurora. This is under Windows/XP with a fibre-optic internet connection. Also, I found out that it helps to shut almost everything else down that can be shut down (just applications, not services). Crossing your fingers and toes doesn't help. Time of day doesn't seem to matter. Root canal is more enjoyable. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 22:09, 18 March 2014 (UTC)
:: I mostly ignore the audio, and just request another image until I find one with low enough ambiguity I am comfortable trying it. I have not tried root canal. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 00:03, 19 March 2014 (UTC)
| |||