Hamming numbers: Difference between revisions
→{{header|F_Sharp|F#}}: fix syntax highlighting; add somewhat imperative logarithmic version...
GordonBGood (talk | contribs) m (→Very fast sequence version using imperative code (mutable vectors) and logarithmic approximations for sorting: fix syntax highlighting...) |
GordonBGood (talk | contribs) (→{{header|F_Sharp|F#}}: fix syntax highlighting; add somewhat imperative logarithmic version...) |
||
Line 3,984:
=={{header|F_Sharp|F#}}==
This version implements Dijkstra's merge solution, so is closely related to the Haskell classic version.
<
let rec hammings() =
Line 4,008:
printfn "%A" (hammings() |> nthLazyList 1691)
printfn "%A" (hammings() |> nthLazyList 1000000)
0</
The above code memory residency is quite high as it holds the entire lazy sequence in memory due to the reference preventing garbage collection as the sequence is consumed,
Line 4,014:
The following code reduces that high memory residency by making the routine a function and using internal local stream references for the intermediate streams so that they can be collected as the stream is consumed as long as no reference is held to the main results stream (which is not in the sample test functions); it also avoids duplication of factors by successively building up streams and further reduces memory use by ordering of the streams so that the least dense are determined first:
{{trans|Haskell}}
<syntaxhighlight lang=fsharp>let cNUMVALS = 1000000▼
<lang fsharp>type LazyList<'a> = Cons of 'a * Lazy<LazyList<'a>> // ': fix colouring▼
▲let cNUMVALS = 1000000
let hammings() =
let rec merge (Cons(x, f) as xs) (Cons(y, g) as ys) =
Line 4,043:
printfn "Found this last up to %d in %d milliseconds." cNUMVALS ((stop - strt) / 10000L)
0 // return an integer exit code</
Both codes output the same results as follows but the second is over three times faster:
Line 4,058:
Since the above pure functional approach isn't very efficient, a more imperative approach using "growable" arrays which are "drained" of unnecessary older values in blocks once the back pointer indices are advanced is used in the following code. The code also implements an algorithm to avoid duplicate calculations and thus does the same number of operations as the above code but faster due to using integer and floating point operations rather an BigInteger ones. Due to the "draining" the memory use is the same as the above by a constant factor. However, note that other than the contents of these arrays, pure functional code using immutable values is used. Note that the implementation of IEnumerable using sequences in F# is also not very efficient and a "roll-your-own" IEnumerable implementation would likely be somewhat faster:
<
let hammingsLog() = // imperative arrays, eliminates the BigInteger operations...
Line 4,107:
printfn ""
0 // return an integer exit code</
{{out}}
<pre>( 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 )
Line 4,115:
The above code produces the same outputs as above, but takes only about 253 milliseconds rather than over a second.
===Even faster version offering means to bypass generation of slow Seq's===
F# has a particularly slow enumeration ability in the use of the `Seq` type (although easy to use) so in order to be able to bypass that, the following code still uses the imperative `ResizeArray`'s but outputs a closure "next" function that can be used directly to avoid the generation of a `Seq` sequence where maximum speed is desired:
<syntaxhighlight lang=fsharp>let cNUMVALS = 1000000
type LogRep = struct val lr: double; val x2: int32; val x3: int32; val x5: int32
new(lr, x2, x3, x5) = {lr = lr; x2 = x2; x3 = x3; x5 = x5 } end
let one: LogRep = LogRep(0.0, 0, 0, 0)
let lg2_2: double = 1.0
let lg3_2: double = log 3.0 / log 2.0
let lg5_2: double = log 5.0 / log 2.0
let inline mul2 (lr: LogRep): LogRep = LogRep(lr.lr + lg2_2, lr.x2 + 1, lr.x3, lr.x5)
let inline mul3 (lr: LogRep): LogRep = LogRep(lr.lr + lg3_2, lr.x2, lr.x3 + 1, lr.x5)
let inline mul5 (lr: LogRep): LogRep = LogRep(lr.lr + lg5_2, lr.x2, lr.x3, lr.x5 + 1)
let lr2BigInt (lr: LogRep): bigint =
let rec rdc v m acc =
if v <= 0 then acc else
if v &&& 1 = 0 then rdc (v >>> 1) (m * m) acc
else rdc (v >>> 1) (m * m) (acc * m)
rdc lr.x2 2I 1I |> rdc lr.x3 3I |> rdc lr.x5 5I
let hammingsLog() = // imperative arrays, eliminates the BigInteger operations...
let mutable s532 = one |> mul2 in let mutable mrg = one |> mul3
let mutable s53 = one |> mul3 |> mul3 // equivalent to 9 for advance step
let mutable s5 = one |> mul5
let h = ResizeArray<_>()
let m = ResizeArray<_>()
let mutable i = 0 in let mutable j = 0
let rec next() = // imperative next closure function to advance value
if h.Capacity = 0 && m.Capacity = 0 then
h.EnsureCapacity 1 |> ignore; m.EnsureCapacity 1 |> ignore; one else
if i > (h.Count >>> 1) then h.RemoveRange(0, i); i <- 0
if s532.lr < mrg.lr then
let rslt = s532 in h.Add(rslt); s532 <- mul2 h.[i]; i <- i + 1; rslt
else let rslt = mrg in h.Add(rslt)
if j >= (m.Count >>> 1) then m.RemoveRange(0, j); j <- 0
if s53.lr < s5.lr then
mrg <- s53; s53 <- mul3 m.[j]; j <- j + 1
else mrg <- s5; s5 <- mul5 s5
m.Add(mrg); rslt
next
let hl2Seq f = Seq.unfold (fun v -> Some(v, f())) (f())
let nthHammingLog n f =
let rec nxt i = if i <= 0 then f() else f() |> ignore; nxt (i - 1) in nxt n
[<EntryPoint>]
let main argv =
printf "( "; hammingsLog() |> hl2Seq |> Seq.take 20
|> Seq.iter (printf "%A " << lr2BigInt); printfn ")"
printfn "%A" (hammingsLog() |> hl2Seq |> Seq.item (1691 - 1) |> lr2BigInt)
let strt = System.DateTime.Now.Ticks
// let rslt = hammingsLog() |> hl2Seq |> Seq.item (cNUMVALS - 1) // slow way
let rslt = hammingsLog() |> nthHammingLog (cNUMVALS - 1) // fast way using closure
let stop = System.DateTime.Now.Ticks
printfn "%A" <| lr2BigInt rslt
printfn "Found this last for %d elements in %d milliseconds."
cNUMVALS ((stop - strt) / 10000L)
0 // return an integer exit code</syntaxhighlight>
{{out}}
<pre>( 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 )
2125764000
519312780448388736089589843750000000000000000000000000000000000000000000000000000000
Found this last for 1000000 elements in 63 milliseconds.</pre>
As you can see, the above code is another four times faster due to not using a `Seq` sequence.
===Extremely fast non-enumerating version sorting values in error band===
Line 4,120 ⟶ 4,191:
If one is willing to forego sequences and just calculate the nth Hamming number, 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. The code is as follows:
{{trans|Haskell}}
<
if n < 1UL then failwith "nthHamming; argument must be > 0!"
if n < 2UL then 0u, 0u, 0u else // trivial case for first value of one
Line 4,181 ⟶ 4,252:
System.Console.ReadKey(true) |> ignore
printfn ""
0 // return an integer exit code</
{{output}}
<pre>( 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 )
Line 4,200 ⟶ 4,271:
Due to the limited 53-bit mantissa of 64-bit double floating piint numbers, the above code can't properly sort the error band for input arguments somewhere above 10**13; the following code makes the sort accurate by using a multi-precision logarithm representation of sufficient precision so that the sort is accurate for arguments well beyond the uint64 input argument range, at about a doubling in cost in execution speed:
{{trans|Haskell}}
<
if n < 1UL then failwith "nthHamming: argument must be > 0!"
if n < 2UL then 0u, 0u, 0u else // trivial case for first value of one
Line 4,233 ⟶ 4,304:
let sbnd = bnd |> List.sortBy (fun (lg, _) -> -lg) // sort in decending order
let _, rslt = sbnd.[ndx]
rslt</
=={{header|Factor}}==
| |||