Antonio Gulli's coding playground

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.

Post a Comment

[フレーム]