Primorial numbers: Difference between revisions
Content deleted Content added
Line 1,695:
=={{header|Nim}}==
===Single thread===
{{libheader|bignum}}
We use a sieve of Erathosthenes to generate the primes, but with only the odd numbers to reduce memory usage. Even for one millions primes, the execution time is negligible (0.12s)
Line 1,782 ⟶ 1,783:
Total time: 127.65 s</pre>
CPU: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz, 2607 MHz with 8GB RAM.
===Multiple threads===
With several threads, we cannot use an iterator anymore. For N threads (workers), we split the list of primes in N sublists and let each worker compute a product. We terminate with a final multiplication of the N results. With four workers, we get the result in about 10 seconds. With eight workers, we get it in about five seconds.
Note that to get execution time, we can no longer use “cpuTime” as it returns only the CPU time used by the main thread. So, we use “getMonoTime” instead.
<lang Nim>import std/monotimes
let t0 = getMonoTime()
####################################################################################################
# Build list of primes.
const
NPrimes = 1_000_000
N = 16 * NPrimes
var sieve: array[(N - 1) div 2 + 1, bool] # False (default) means prime.
for i, composite in sieve:
if not composite:
let n = 2 * i + 3
for k in countup(n * n, N, 2 * n):
sieve[(k - 3) div 2] = true
var primes = @[2]
for i, composite in sieve:
if not composite:
primes.add 2 * i + 3
if primes.len < NPrimes:
quit "Not enough primes. Please, increase value of N."
####################################################################################################
# Compute primorial.
import strformat, threadpool
import bignum
const NWorkers = 8
proc computeProduct(a: openArray[int]): Int =
result = newInt(1)
for n in a: result *= n
proc primorial(n: int): Int =
if n == 0: return newInt(1)
# Prepare sublists.
var input: array[NWorkers, seq[int]]
for i in 0..<n:
input[i mod NWorkers].add primes[i]
# Spawn workers and get partial products.
var responses: array[NWorkers, FlowVar[Int]]
for i in 0..<NWorkers:
responses[i] = spawn computeProduct(input[i])
# Compute final product.
result = ^responses[0]
for i in 1..<NWorkers:
result *= ^responses[i]
for n in 0..9:
echo &"primorial({n}) = {primorial(n)}"
for n in [10, 100, 1_000, 10_000, 1_000_000]:
echo &"primorial({n}) has {len($primorial(n))} digits"
echo ""
echo &"Total time: {(getMonoTime() - t0)}"</lang>
{{out}}
<pre>primorial(0) = 1
primorial(1) = 2
primorial(2) = 6
primorial(3) = 30
primorial(4) = 210
primorial(5) = 2310
primorial(6) = 30030
primorial(7) = 510510
primorial(8) = 9699690
primorial(9) = 223092870
primorial(10) has 10 digits
primorial(100) has 220 digits
primorial(1000) has 3393 digits
primorial(10000) has 45337 digits
primorial(1000000) has 6722809 digits
Total time: (seconds: 5, nanosecond: 270238339)</pre>
=={{header|PARI/GP}}==
| |||