## digitalmars.D - Re: Hamming numbers comparison, take 2

```This D2 code adapted from the Java version finds the correct solutions, but I
don't think of it as the a good solution because it stores all items and uses
lot of memory. The Python version I was trying to translate uses only few MB of
RAM, while this version uses almost 100 MB of it.

import std.stdio: writeln;
import std.bigint: BigInt;
import std.algorithm: min, map;
import std.range: iota;
import std.array: array;

BigInt hamming(int limit) {
BigInt two   = 2;
BigInt three = 3;
BigInt five  = 5;

auto h = new BigInt[limit];
h[0] = 1;
BigInt x2 = 2;
BigInt x3 = 3;
BigInt x5 = 5;
int i, j, k;

foreach (ref el; h[1 .. \$]) {
el = min(x2, x3, x5);
if (x2 == el)
x2 = two * h[++i];
if (x3 == el)
x3 = three * h[++j];
if (x5 == el)
x5 = five * h[++k];
}
return h[\$ - 1];
}

const(char)[] bigIntRepr(BigInt i) {
const(char)[] result;
i.toString((const(char)[] s){ result = s; }, "d");
return result;
}

void main() {
writeln(array(map!bigIntRepr(map!hamming(iota(1, 21)))));
writeln(bigIntRepr(hamming(1691)));
writeln(bigIntRepr(hamming(1_000_000)));
}

I think it's the first time I am able to write a working program that uses
BigInt :-)
In the first line of the main I have had to use two maps because I was not able
to make it run with just one map.
While writing this program I have found only two problems (beside the known map
one), filed as 4300 and 4301.
This code runs in D 2.62 seconds, its Java version in 1.95 seconds, and its
Python+Psyco version in 1.03 seconds. (The Haskell version that uses a better
algorithm can be a bit faster than the Python version).

The Python translation:

import psyco

def hamming(limit):
h = [1] * limit
x2, x3, x5 = 2, 3, 5
i = j = k = 0

for n in xrange(1, limit):
h[n] = min(x2, x3, x5)
if x2 == h[n]:
i += 1
x2 = 2 * h[i]
if x3 == h[n]:
j += 1
x3 = 3 * h[j]
if x5 == h[n]:
k += 1
x5 = 5 * h[k]

return h[-1]

psyco.bind(hamming)
print [hamming(i) for i in xrange(1, 21)]
print hamming(1691)
print hamming(1000000)

Bye,
bearophile
```
Jun 10 2010