Monday, February 16, 2009

Hamming numbers III

It is possible to generate the hamming numbers without duplicates. The key intuition it to generate the sets:
1. M2 = { h : h=2^l , l \in N, l < max }
2. M3 = { h : h=3^o , o \in N, o < max }
3. M5 = { h : h=5^p , p \in N, p < max }
Then we generate:
1. M23 = { i : i = h*k, h \in M2, k \in M3}
2. M25 = { i : i = h*k, h \in M2, k \in M5}
3. M35 = { i : i = h*k, h \in M3, k \in M5}
4. M235 = { i : i = h*k, h \in M23, k \in M5}
Here is the code. Let's have a look to the complexity in terms of analyzed numbers. Let P the maximum integer you can represent. Then, generating the sets M2, M3, M5 takes O(logP), since |M2| <= log2(P) , |M3| <= log3(P), |M5| <= log5(P). As a consequence, generating M23, M25, M35, M235 takes (log(P))^2. We are sub-linear in terms of input and cubic in terms of output.