Finding Hamming Numbers - not code or distance

Question

I'm currently learning C++.

I am looking for Hamming numbers (numbers whose prime divisors are less or equal to 5).

When I input a number n, the program should output the n-th Hamming number.

Following numbers are input, and output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...

1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 ...

Finding Hamming numbers looks easy, but increasing the input number increases run time cost exponentially.

If I input over 1000, it almost costs over 1 second, and over 1200, it almost costs over 5 seconds.

This is the code I wrote:

while (th > 1)
{
    h++;
    x = h;

    while (x % 2 == 0)
        x /= 2;
    while (x % 3 == 0)
        x /= 3;
    while (x % 5 == 0)
        x /= 5;

    if (x == 1)
        th--;
}

So I would like to know how I can find the answer faster. This algorithm doesn't seem to be very good.

Thanks in advance.

Answer 1

Your code is good if you want to check whether one particular number is a hamming number. When you want to build a list of hamming numbers, it is inefficient.

You can use a bottom-up approach: Start with 1 and then recursively multiply that with 2, 3, and 5 to get all hamming numbers up to a certain limit. You have to take care of duplicates, because you can get to 6 by way of 2·3 and 3·2. A set can take care of that.

The code below will generate all hamming numbers that fit into a 32-bit unsigned int. It fills a set by "spreading" to all hamming numbers. Then it constructs a sorted vector from the set, which you can use to find a hamming number at a certain index:

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>

typedef unsigned int uint;

const uint umax = 0xffffffff;

void spread(std::set<uint> &hamming, uint n)
{
    if (hamming.find(n) == hamming.end()) {
        hamming.insert(n);

        if (n < umax / 2) spread(hamming, n * 2);
        if (n < umax / 3) spread(hamming, n * 3);
        if (n < umax / 5) spread(hamming, n * 5);
    }
}

int main()
{
    std::set<uint> hamming;

    spread(hamming, 1);

    std::vector<uint> ordered(hamming.begin(), hamming.end());

    for (size_t i = 0; i < ordered.size(); i++) {
        std::cout << i << ' ' << ordered[i] << '\n';
    }

    return 0;
}

This code is faster than your linear method even if you end up creating more hamming numbers than you need.

You don't even need a set if you make sure that you don't construct a number twice. Every hamming number can be written as h = 2^n2 + 3^n3 + 5^n5, so if you find a means to iterate through these uniquely, you're done:

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>

typedef unsigned int uint;

int main()
{
    const uint umax = 0xffffffff;
    std::vector<uint> hamming;

    for (uint k = 1;; k *= 2) {
        for (uint l = k;; l *= 3) {
            for (uint m = l;; m *= 5) {
                hamming.push_back(m);
                if (m > umax / 5) break;
            }
            if (l > umax / 3) break;
        }
        if (k > umax / 2) break;
    }

    std::sort(hamming.begin(), hamming.end());

    for (size_t i = 0; i < hamming.size(); i++) {
        std::cout << i << ' ' << hamming[i] << '\n';
    }

    return 0;
}

The strange break syntax for the loops is required, because we have to check the size before the overflow. If umax*5 were guananteed not to overflow, these conditions could be written in the condition part of the loop.

The code examples in the Rosetta Code link Koshinae posted use similar strategies, but I'm surprised how lengthy some of them are.

Answer 2

In this link you can find two different solutions for finding the nth hamming number. The second method is the optimized one which can get the result in a few seconds.

/* Function to get the nth ugly number*/
unsigned getNthUglyNo(unsigned n) 
{ 
    unsigned ugly[n]; // To store ugly numbers 
    unsigned i2 = 0, i3 = 0, i5 = 0; 
    unsigned next_multiple_of_2 = 2; 
    unsigned next_multiple_of_3 = 3; 
    unsigned next_multiple_of_5 = 5; 
    unsigned next_ugly_no = 1; 

    ugly[0] = 1; 
    for (int i=1; i<n; i++) 
    { 
        next_ugly_no = min(next_multiple_of_2, 
                           min(next_multiple_of_3, 
                               next_multiple_of_5)); 
        ugly[i] = next_ugly_no; 
        if (next_ugly_no == next_multiple_of_2) 
        { 
            i2 = i2+1; 
            next_multiple_of_2 = ugly[i2]*2; 
        } 
        if (next_ugly_no == next_multiple_of_3) 
        { 
            i3 = i3+1; 
            next_multiple_of_3 = ugly[i3]*3; 
        } 
        if (next_ugly_no == next_multiple_of_5) 
        { 
           i5 = i5+1; 
           next_multiple_of_5 = ugly[i5]*5; 
        } 
    } /*End of for loop (i=1; i<n; i++) */

return next_ugly_no; 
}