Legendre prime counting function: Difference between revisions
Content added Content deleted
GordonBGood (talk | contribs) (→{{header|CoffeeScript}}: add Chapel non-memoizing versions above...) |
GordonBGood (talk | contribs) m (→{{header|F#}}: clarify recursion explanation in last version...) |
||
| Line 803: | Line 803: | ||
'''The Non-Recursive Partial Sieving Algorithm''' |
'''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: |
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 to same compiled code as a simple loop in other languages: |
||
{{trans|Nim}} |
{{trans|Nim}} |
||
<syntaxhighlight lang="fsharp">let masks = Array.init 8 ((<<<) 1uy) // quick bit twiddling |
<syntaxhighlight lang="fsharp">let masks = Array.init 8 ((<<<) 1uy) // quick bit twiddling |
||