Anonymous user
Talk:Hamming numbers: Difference between revisions
no edit summary
No edit summary |
|||
Line 56:
: O, I didn't realize this. But the millionth will be a problem. So, should I retreat my solution? --[[User:Gaaijz|Gaaijz]]
:: Hi, No, keep it in. You might want to mention if the millionth is not achieved due to lack of multi-precision integer arithmetic or excessive run-time though. Thanks. --[[User:Paddy3118|Paddy3118]] 05:43, 6 January 2010 (UTC)
==Changes to the Java algorithm==
Originally the Java algorithm kept the whole sequence in memory. While that could be useful, it ran into out-of-memory errors quite easily.
My contribution was to split the Hamming sequence memory into three buffers: one for Hamming numbers to multiply by two, one for Hamming numbers to multiply by three and another for Hamming numbers to multiply by five. Hamming numbers which were already multiplied can be forgotten (resetting them to null frees memory occupied by BigInteger).
The first buffer contains only numbers with factor two (they are powers of two) since that is always the smallest unique Hamming number that can appear in that buffer e.g. 6 = 2*3 multiplied by two is 12 = 2*2*3, but 4 = 2*2 is a smaller Hamming number which appears in the "multiply by three" buffer so we don't need 6 in the "multiply by two" buffer.
The "multiply by three" buffer contains only numbers with factors two and three for the same reasons. The "multiply by five" buffer contains numbers with factors two, three and five. That division in three buffers prevents duplicates when merging. Note that it can be generalised to 7-smooth numbers, 11-smooth etc.
Looking at the algorithm, the "multiply by two" buffer never grows -- it always contains exactly one element. So it can be eliminated. The "multiply by three" buffer never receives more than half the limit numbers, which is what I use as buffer size. Since this buffer only grows with powers of two, we could use a circular buffer sized after log2(limit) but that would complicate the code.
| |||