Hamming numbers: Difference between revisions
→{{header|Vlang}}: Rename "Vlang" in "V (Vlang)"
(→{{header|Wren}}: Added a second much faster version.) |
(→{{header|Vlang}}: Rename "Vlang" in "V (Vlang)") |
||
Line 12,162:
</pre>
=={{header|V (Vlang)}}==
{{trans|go}}
===Concise version using dynamic-programming===
<syntaxhighlight lang="v (vlang)">import math.big
fn min(a big.Integer, b big.Integer) big.Integer {
Line 12,211:
===Fast version with no duplicates algorithm using arrays for memoization and logarithmic approximations===
The V (Vlang) language isn't yet stable enough (version 0.30) to support a fully functional version using generic lazy lists as per the Haskell language versions and in truth is mostly an imperative language anyway; however, it already can do the page task very quickly with a more imperative algorithm using arrays for memoization storage and logarithmic approximations for sorting comparisons to avoid "infinite" precision integer calculations except for the final result values, as per the following code, which is Nim's "ring buffer" version as that is faster due to less copying required:
{{trans|Nim}}
<syntaxhighlight lang="v (vlang)">// compile with: v -cflags -march=native -cflags -O3 -prod HammingsLogQ.v
import time
Line 12,384:
The above code is about as fast as one can go generating sequences/iterations; however, if one is willing to forego sequences/iterations and just calculate the nth Hamming number (repeatedly when a sequence is desired, but that is only for the first required task of three and then only for a trivial range), then some reading on the relationship between the size of numbers to the sequence numbers is helpful (Wikipedia: Regular Number). One finds that there is a very distinct relationship and that it quite quickly reduces to quite a small error band proportional to the log of the output value for larger ranges. Thus, the following code just scans for logarithmic representations to insert into a sequence for this top error band and extracts the correct nth representation from that band. It reduces time complexity to O(n^(2/3)) from O(n) for the sequence versions, but even more amazingly, reduces memory requirements to O(n^(1/3)) from O(n^(2/3)) and thus makes it possible to calculate very large values in the sequence on common personal computers. This version uses a multi-precision integer as the representation of the logarithmic approximation of the value for sorting of the error band to extend the precision for accurate results up to almost the 64-bit number range (in about a day on common desktop computers). The code is as follows:
{{trans|Nim}}
<syntaxhighlight lang="v (vlang)">// compile with: v -cflags -march=native -cflags -O3 -prod HammingsLog.v
import time
| |||