Legendre prime counting function: Difference between revisions
m
→{{header|F#}}: minor comment corrections...
GordonBGood (talk | contribs) m (→Non Memoized Haskell Versions: Haskell: improve comments...) |
GordonBGood (talk | contribs) m (→{{header|F#}}: minor comment corrections...) |
||
Line 744:
The above time as run on an Intel i5-6500 (3.6 GHz single-threaded boost) isn't particularly fast but includes some DotNet initialization and JIT compilation overhead, and is about as fast as a highly optimized page-segmented wheel-factorized Sieve of Eratosthenes; Although this is about ten times faster than if it were using memoization (and uses much less memory), it is only reasonably usable for trivial ranges such as this (trivial in terms of prime counting functions).
'''The Less Recursive "Bottom-Up" with a TinyPhi LUT Algorithm'''
Just substitute the following F# code for the `countPrimes` function above to enjoy the gain in speed:
Line 803:
'''The Non-Recursive Partial Sieving Algorithm'''
Just substitute the following F# code for the `countPrimes` function above to enjoy the further gain in speed; note that rather than using a recursive function loop for the partial sieving culling pass as per the above two version, this version uses a Seq iteration which is slower but more concise in expression, but as sieving is a negligible part of the total execution time, it doesn't matter and conciseness was considered to be more important; this version may appear to be recursive to those unfamiliar with Functional Programming (FP) implementations but FP generally turns all function recursions in tail-call position (which all of these are) into
{{trans|Nim}}
<syntaxhighlight lang="fsharp">let masks = Array.init 8 ((<<<) 1uy) // quick bit twiddling
| |||