Anonymous user
Self numbers: Difference between revisions
→{{header|Nim}}
m (→{{header|Phix}}: added syntax colouring the hard way) |
|||
Line 1,069:
10,000,000 102,272,662
100,000,000 1,022,727,208</pre>
=={{header|Nim}}==
In order to use less memory, we have chosen to use indexing at bit level. So, our sieve is a custom object defined by its length in bits and its value which is a sequence of bytes. With bit indexing, the sieve uses eight times less memory than with byte indexing.
Of course, there is a trade off to this strategy: reading values from and writing values to the sieve are significantly slower.
===Simple sieve===
{{trans|Go}}
We use the Go algorithm with bit indexing. As a consequence the sieve uses about 250MB instead of 1 GB. And the program is about five times slower.
Note that we used a sequence of ten nested loops as in the Go solution but we have not memorized the intermediate sums as the C compiler does a good job to detect the loop invariants (remember, Nim produces C code and this code has proved to be quite optimizable by the C compiler). The ten loops looks a lot better this way, too 🙂.
<lang Nim>import bitops, strutils, std/monotimes, times
const MaxCount = 2 * 1_000_000_000 + 9 * 9
# Bit string used to represent an array of booleans.
type BitString = object
len: Natural # length in bits.
values: seq[byte] # Sequence containing the bits.
proc newBitString(n: Natural): BitString =
## Return a new bit string of length "n" bits.
result.len = n
result.values.setLen((n + 7) shr 3)
template checkIndex(i, length: Natural) {.used.} =
## Check if index "i" is less than the array length.
if i >= length:
raise newException(IndexDefect, "index $1 not in 0 .. $2".format(i, length))
proc `[]`(bs: BitString; i: Natural): bool =
## Return the value of bit at index "i" as a boolean.
when compileOption("boundchecks"):
checkIndex(i, bs.len)
result = bs.values[i shr 3].testbit(i and 0x07)
proc `[]=`(bs: var BitString; i: Natural; value: bool) =
## Set the bit at index "i" to the given value.
when compileOption("boundchecks"):
checkIndex(i, bs.len)
if value: bs.values[i shr 3].setBit(i and 0x07)
else: bs.values[i shr 3].clearBit(i and 0x07)
proc fill(sieve: var BitString) =
## Fill a sieve.
var n = 0
for a in 0..1:
for b in 0..9:
for c in 0..9:
for d in 0..9:
for e in 0..9:
for f in 0..9:
for g in 0..9:
for h in 0..9:
for i in 0..9:
for j in 0..9:
sieve[a + b + c + d + e + f + g + h + i + j + n] = true
inc n
let t0 = getMonoTime()
var sieve = newBitString(MaxCount + 1)
sieve.fill()
echo "Sieve time: ", getMonoTime() - t0
# Find first 50.
echo "\nFirst 50 self numbers:"
var count = 0
var line = ""
for n in 0..MaxCount:
if not sieve[n]:
inc count
line.addSep(" ")
line.add $n
if count == 50: break
echo line
# Find 1st, 10th, 100th, ..., 100_000_000th.
echo "\n Rank Value"
var limit = 1
count = 0
for n in 0..MaxCount:
if not sieve[n]: inc count
if count == limit:
echo ($count).align(10), ($n).align(12)
limit *= 10
echo "Total time: ", getMonoTime() - t0</lang>
{{out}}
<pre>Sieve time: 2 seconds, 59 milliseconds, 67 microseconds, and 152 nanoseconds
First 50 self numbers:
1 3 5 7 9 20 31 42 53 64 75 86 97 108 110 121 132 143 154 165 176 187 198 209 211 222 233 244 255 266 277 288 299 310 312 323 334 345 356 367 378 389 400 411 413 424 435 446 457 468
Rank Value
1 1
10 64
100 973
1000 10188
10000 102225
100000 1022675
1000000 10227221
10000000 102272662
100000000 1022727208
Total time: 7 seconds, 903 milliseconds, 752 microseconds, and 944 nanoseconds</pre>
===Improved sieved===
{{trans|Pascal}}
Using bit indexing is very useful here as with byte indexing, the sieve needs 10GB. On a computer with only 8 GB , as this is the case of the laptop I use to run these programs, it fails to execute (I have a very small swap and don’t want to use the swap anyway). With bit indexing, the sieve needs only 1,25GB which is more reasonable.
Of course, the program is slower but not in the same proportion that in the previous program: it is about twice slower than the Pascal version. Note that the execution time varies significantly according to the way statements are written. For instance, writing <code>if not sieve[n]: inc count</code> has proved to be more efficient than writing <code>inc count, ord(not sieve[n])</code> or <code>inc count, 1 - ord(sieve[n])</code> which is surprising as the latter forms avoid a jump. Maybe changing some other statements could give better results, but current time is already satisfying.
<lang Nim>import bitops, strutils, std/monotimes, times
const MaxCount = 103 * 10_000 * 10_000 + 11 * 9 + 1
# Bit string used to represent an array of booleans.
type BitString = object
len: Natural
values: seq[byte]
proc newBitString(n: Natural): BitString =
## Return a new bit string of length "n" bits.
result.len = n
result.values.setLen((n + 7) shr 3)
template checkIndex(i, length: Natural) {.used.} =
## Check if index "i" is less than the array length.
if i >= length:
raise newException(IndexDefect, "index $1 not in 0 .. $2".format(i, length))
proc `[]`(bs: BitString; i: Natural): bool =
## Return the value of bit at index "i" as a boolean.
when compileOption("boundchecks"):
checkIndex(i, bs.len)
result = bs.values[i shr 3].testbit(i and 0x07)
proc `[]=`(bs: var BitString; i: Natural; value: bool) =
## Set the bit at index "i" to the given value.
when compileOption("boundchecks"):
checkIndex(i, bs.len)
if value: bs.values[i shr 3].setBit(i and 0x07)
else: bs.values[i shr 3].clearBit(i and 0x07)
proc initDigitSum9999(): array[10000, byte] {.compileTime.} =
## Return the array of the digit sums for numbers 0 to 9999.
var i = 0
for a in 0..9:
for b in 0..9:
for c in 0..9:
for d in 0..9:
result[i] = byte(a + b + c + d)
inc i
const DigitSum9999 = initDigitSum9999()
proc fill(sieve: var BitString) =
## Fill a sieve.
var n = 0
for a in 0..102:
for b in 0..9999:
var s = DigitSum9999[a].int + DigitSum9999[b].int + n
for c in 0..9999:
sieve[DigitSum9999[c].int + s] = true
inc s
inc n, 10_000
let t0 = getMonoTime()
var sieve = newBitString(MaxCount + 1)
sieve.fill()
echo "Sieve time: ", getMonoTime() - t0
# Find first 50.
echo "\nFirst 50 self numbers:"
var count = 0
var line = ""
for n in 0..MaxCount:
if not sieve[n]:
inc count
line.addSep(" ")
line.add $n
if count == 50: break
echo line
# Find 1st, 10th, 100th, ..., 1_000_000_000th.
echo "\n Rank Value"
var limit = 1
count = 0
for n in 0..MaxCount:
if not sieve[n]: inc count
if count == limit:
echo ($count).align(10), ($n).align(12)
limit *= 10
echo "Total time: ", getMonoTime() - t0</lang>
{{out}}
<pre>Sieve time: 13 seconds, 340 milliseconds, 45 microseconds, and 528 nanoseconds
First 50 self numbers:
1 3 5 7 9 20 31 42 53 64 75 86 97 108 110 121 132 143 154 165 176 187 198 209 211 222 233 244 255 266 277 288 299 310 312 323 334 345 356 367 378 389 400 411 413 424 435 446 457 468
Rank Value
1 1
10 64
100 973
1000 10188
10000 102225
100000 1022675
1000000 10227221
10000000 102272662
100000000 1022727208
1000000000 10227272649
Total time: 28 seconds, 135 milliseconds, 481 microseconds, and 697 nanoseconds</pre>
=={{header|Pascal}}==
| |||