Ulam numbers: Difference between revisions
→{{header|Wren}}: Added a third version based on XPL0 algorithm.
(Added really fast XPL0 example.) |
(→{{header|Wren}}: Added a third version based on XPL0 algorithm.) |
||
Line 494:
Took 6.366709 seconds.
</pre>
===Version 3===
{{trans|XPL0}}
This version is even quicker than Version 2 and reduces the time needed to calculate the 10,000th Ulam number to about 3.65 seconds. It also makes the 100,000th Ulam number a viable proposition for the Wren interpreter coming in at about 6 minutes 50 seconds.
The only downside with this version is that you need to know how much memory to allocate in advance.
<lang ecmascript>import "/fmt" for Fmt
var ulam = Fn.new { |n|
if (n <= 2) return n
var max = 1352000
var list = List.filled(max+1, 0)
list[0] = 1
list[1] = 2
var sums = List.filled(max*2+1, 0)
sums[3] = 1
var size = 2
var query
while (true) {
query = list[size-1] + 1
while (true) {
if (sums[query] == 1) {
for (i in 0..size-1) {
var sum = query + list[i]
var t = sums[sum] + 1
if (t <= 2) sums[sum] = t
}
list[size] = query
size = size + 1
break
}
query = query + 1
}
if (size >= n) break
}
return query
}
var start = System.clock
var n = 10
while (true) {
Fmt.print("The $,r Ulam number is $,d", n, ulam.call(n))
n = n * 10
if (n > 100000) break
}
System.print("\nTook %(System.clock - start) seconds.")</lang>
{{out}}
<pre>
</pre>
| |||