Klarner-Rado sequence: Difference between revisions
→{{header|Phix}}: added faster version (trans Wren)
(→Version 2 (faster): Added a third much faster version.) |
(→{{header|Phix}}: added faster version (trans Wren)) |
||
Line 918:
</pre>
Unfortunately JavaScript can't quite cope/runs out of memory with a 100 million element sieve, so it only goes to the 10^5th under p2js.
=== much faster ===
{{trans|Wren}} slightly faster to 1e7 than the above is to 1e6.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">klarnerRado</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">dst</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">i2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i3</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">m2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m3</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m3</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">dst</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">m2</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">m</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">m2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dst</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i2</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">i2</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">m3</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">m</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">m3</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dst</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i3</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">3</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">i3</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">dst</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">kr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">klarnerRado</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1e7</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"First 100 elements of Klarner-Rado sequence:\n%s\n"</span><span style="color: #0000FF;">,</span>
<span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #000000;">kr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">100</span><span style="color: #0000FF;">],</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"%4d"</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #000000;">7</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The %,d%s Klarner-Rado number is %,d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">ord</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">),</span><span style="color: #000000;">kr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">]})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
First 100 elements of Klarner-Rado sequence:
1 3 4 7 9 10 13 15 19 21 22 27 28 31 39 40 43 45 46 55
57 58 63 64 67 79 81 82 85 87 91 93 94 111 115 117 118 121 127 129
130 135 136 139 159 163 165 166 171 172 175 183 187 189 190 193 202 223 231 235
237 238 243 244 247 255 256 259 261 262 271 273 274 279 280 283 319 327 331 333
334 343 345 346 351 352 355 364 367 375 379 381 382 387 388 391 405 406 409 418
The 1,000th Klarner-Rado number is 8,487
The 10,000th Klarner-Rado number is 157,653
The 100,000th Klarner-Rado number is 2,911,581
The 1,000,000th Klarner-Rado number is 54,381,285
The 10,000,000th Klarner-Rado number is 1,031,926,801
"1.1s"
</pre>
=={{header|PL/M}}==
| |||