Hamming numbers: Difference between revisions

The Elm language has many restrictions that make the implementation of the Hamming Number sequence algorithms difficult, as the classic Edsger Dijkstra algorithm as written in Haskell [[Hamming_numbers#The_classic_version]] cannot be written in Elm as current Elm forbids cyclic value references (the value "hamming" is back referenced three times), and the implementation wouldn't be efficient even if it could as the current Elm version 0.19.x has removed the "Lazy" package the would defer the memoization of the result of a computation as necessary in implementing Haskell's lazy lists. Thus, one has to implement memoization using a different data structure than a lazy list; however, all current Elm data structures are persistent/forbid mutation and can only implement some sort of Copy On Write (COW), thus there is no implementation of a linear array and the "Array" module is a tree based structure (with some concessions to data blocks for slightly better performance) that will have a logarithmic execution complexity when the size increases above a minimum. In fact, all Elm data structures that could be used for this also have a logarithmic response (Dict, Set, Array). The implementation of List is not lazy so new elements can't be added to the "tail" but need to be added to the "head" for efficiency, which means if one wants to add higher elements to a list in increasing order, one needs to (COW) reverse the List (twice) in order to do it!

The solution here uses a pure functional implementation of a Min Heap (Binary Heap) Priority Queue so that the minimum element can be viewed in O(1) time although inserting new elements/replacing elements still takes O(log n) time where "n" is the number of elements in the queue. As written, no queue needs to be maintained for the multiples of five, but two quesqueues are maintained, one for the merge of the multiples of five and three, and the larger one for the merge of all the multiples of five, three, and two. In order to minimize redundant computation time, the implementation maintains the "next" comparison values as part of the recursive function loop states that can change with every loop.

In addition, in order to reduce the "BigInt" computation time, the calculations are done on the basis of a "Float" logarithmic approxitmationapproximation while maintaining "Trival" triple representation of the number of timespowers of two, three, and five, are multiplied in order to obtain the current value represented by the logarithmic approximation. The working code is as follows:

import Html exposing (Html, div, text )

otherwiseNothing -> m235 -- at the beginning!

otherwiseNothing -> mrg -- at the beginning!

|> andThen (\ t -> succeed ( t, nthCIS lmt (hammingsLog()) ))|> takeCIS2List 20

element { init = \ _ -> ( Model[], 0test cLIMIT )

, update = \ (Done mdl) _ -> ("The first 20 Hamming numbers are:mdl , "Cmd.none ++)

, view = myviewdiv [] << List.map (div [] << List.singleton << text) }</syntaxhighlight>

The 1000000th Hamming number is 519312780448388736089589843750000000000000000000000000000000000000000000000000000000 in 756 milliseconds.</pre>:

Do note that, due to the logarithmic response of the Min Heap Priority Queue, the execution time is logarithmic with number of elements evaluation and not linear as it would otherwise be, so if it takes 0.7 seconds to find the millionth Hamming number, it takes something about 10 seconds to find the ten millionth value instead of about 7 seconds. Considering that the generated "native" code is just JavaScript, it is reasonably fast and somewhat competitive with easier implementations in other languages such as F#.