# Fast Hamming sequence generation in Haskell

I found some months ago that I could generate Hamming multiples of 3 and 5 multiples (3^x & 5^x) in one list comprehension. There are many fewer 3 and 5 Hamming multiples in a Hamming sequence. I did not have to be concerned with duplicate multiples as it is 2 disparate lists.

All I needed to do was add the Hamming 2 multiples.

When I did, it was chaos. Multiples of the 3 and 5 multiples with the 2^x produced clean Hamming numbers but left even more at the end of the list that had missing Hamming numbers between them.

The problem was the Cartesian product of the 2 multiples and the 3&5 multiples.

I had used the 3^x times 5^x’s in another algorithm successfully. I had limited the list with some involved calculation.

Then, I encountered the same problem working with primes. I wanted a list to subtract from a wheel but the list contained much excess. It was another huge Cartesian product of values.

I didn’t know which elements to eliminate from either list and I thought them intermixed.

Then it dawned on me. I tried it with the primes and it worked. Then with the Hamming 2s and it worked.

First I rewrote the 3 & 5 multiples list comprehension with the much simpler logic and way less calculation.

What was the solution? All it is, is using the end value of the generated first list to limit values of subsequent lists. List comprehensions take the first value of the first list and apply it to all values in the second list thus making a list. It is the first list end value that is the limit of each subsequent list. These limited lists do not generate any excess at the end of any list

The prime’s composite list to subtract is top and bottom diagonal to form a rouge triangle. In it x and y are identical. The Hammings lists are bottom, irregular diagonal only. The x and y are different.

My problem, now, is how to specify how many Hammings I want instead of thex in 2^x as the parameter. Is it just practical to use take with some derived value of x (in 2^x) to get the number of Hammings wanted? How can x be derived from specified n number of Hamming wanted? The second thing is how fast is this compared to the fastest Hamming list generators?

The Hamming functions follow

gnf n f = scanl (*) 1 $replicate f n mk35 n = (\c-> [m| t<- gnf 3 n, f<- gnf 5 n, m<- [t*f], m<= c]) (2^(n+1)) mkHams n = (\c-> sort [m| t<- mk35 n, f<- gnf 2 (n+1), m<- [t*f], m<= c]) (2^(n+1))  last$ mkHams 50

2251799813685248

(0.03 secs, 12,869,000 bytes)

2^51

2251799813685248

5/6/2019

Well, I tried limiting differently but always come back to what is simplest. I am opting for the least memory usage as also the fastest. I also opted to use map with an implicit parameter. I also found that mergeAll from Data.List.Ordered is faster that sort or sort and concat. I also like when sublists are created so I can analyze the data much easier. Then, because of @Wil Ness on SO switched to iterate instead of scanl making much cleaner code. Also because of @Wil Ness I stopped using last of of 2s list and switched to one value determining all lengths.

Just separating the function into two doesn't make a difference so the 3 and 5 multiples would be

m35 lim = mergeAll $map (takeWhile (<=lim).iterate (*3))$
takeWhile (<=lim).iterate (*5)  $1  And the 2s each multiplied by the product of 3s and 5s ham n = mergeAll$
map (takeWhile (<=lim).iterate (*2)) $m35 lim where lim= 2^n  After editing the function I ran it last$ ham 50

1125899906842624

(0.00 secs, 7,029,728 bytes)

then

last $ham 100 1267650600228229401496703205376 (0.03 secs, 64,395,928 bytes) It is probably better to use 10^n but for comparison I again used 2^n. 5/11/2019 Because I so prefer infinite and recursive lists I became a bit obsessed with making these infinite. I was so impressed and inspired with @Daniel Wagner and his Data.Universe.Helpers I started using +*+ and +++ but then added my own infinite list. I had to mergeAll my list to work but then realized the infinite 3 and 5 multiples were exactly what they should be. So, I added the 2s and mergeAlld everything and they came out. Before, I stupidly thought mergeAll would not handle infinite list but it does most marvelously. When a list is infinite in Haskell, Haskell calculates just what is needed, that is, is lazy. The adjunct is that it does calculate from, the start. Now, since Haskell multiples until the limit of what is wanted, no limit is needed in the function, that is, no more takeWhile. The speed up is incredible and the memory lowered too, The following is on my slow home PC with 3GB of RAM. tia = mergeAll.map (iterate (*2))$
mergeAll.map (iterate (*3)) $iterate (*5) 1  last$ take 10000 tia

288325195312500000

(0.02 secs, 5,861,656 bytes)

6.5.2019

I learned how to gch -O2. The following is for 50,000 Hammings to 2.38E+30. The only change from rerunning this is MUT is .016 and GC is .031 and total is .047 or like this one GC is .047 and total is the same.

INIT    time    0.000s  (  0.000s elapsed)
MUT     time    0.000s  (  0.916s elapsed)
GC      time    0.047s  (  0.041s elapsed)
EXIT    time    0.000s  (  0.005s elapsed)
Total   time    0.047s  (  0.962s elapsed)

Alloc rate    0 bytes per MUT second
Productivity   0.0% of total user, 95.8% of total elapsed


6.13.2019

@Will Ness rawks. He provided a clean and elegant revision of tia above and it proved to be five times as fast in GHCi. When I ghc -O2 +RTS -s his against mine, mine was several times faster. There had to be a compromise.

mai n = mergeAll.map (iterate (*n))
mai 2 $mai 3$ iterate (*5) 1


It matched Will's at 0.08 for 100K Hammings in GHCi but what really surprised me is (also for 100K Hammings.) The elapsed is really what gets me.

 TASKS: 3 (1 bound, 2 peak workers (2 total), using -N1)

SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)

INIT    time    0.000s  (  0.000s elapsed)
MUT     time    0.000s  (  0.002s elapsed)
GC      time    0.000s  (  0.000s elapsed)
EXIT    time    0.000s  (  0.000s elapsed)
Total   time    0.000s  (  0.002s elapsed)

Alloc rate    0 bytes per MUT second

Productivity 100.0% of total user, 90.2% of total elapsed

• What are "Hamming multiples of 3 and 5 multiples"? What is "a Hamming sequence"? There's a lot of explanation here of your path to the current version of the code, but I can't find an intelligible explanation of the problem it's trying to solve. – Peter Taylor Apr 3 at 14:48
• mkHams 50 will generate 6911 Hamming #s in sequence. Here is a link to the well understood Hamming sequence generation rosettacode.org/wiki/Hamming_numbers#Haskell The entry "Direct calculation through triples enumeration" is what this is trying to solve but in a more direct & simpler way. There is a Wiki, too. They are also known as ugly or regular numbers. I first was using involved calculation like the code in Rosetta Code but then I found the value of the end point of the first list of a Cartesian product as a limit of all other list values. c This could be 2^i * 3^j * 5^k – fp_mora Apr 3 at 16:09
• It's slow as you need to screen or filter in each subStep. When you calculate the fold of 3 and all those larger than 2^(n+1) needed to be removed. same for the 5 .same for the 3*5 , you did it but maybe too late. The final steps also has such problems. you need to early stop guard. How about add a where clause some where to do it. Actually both questions has one answer. Build a queue with [1,2,3,5], every popped one multiple(2, 3, 5) and then insert back to the queue but keep unique value for the queue. The result is all popped ones. It is countable without extra number. – E.Coms Apr 3 at 17:18
• Yes. Still it's slow. try the queue one should be 100 times fast than this one as you have to visit many unnecessary big numbers. In order to get it faster, you may cache three positions and then insert from there respectively, which will be very attractive. – E.Coms Apr 3 at 17:37
• It is great to hear that. – E.Coms Apr 3 at 17:52