Hello! Hoping for some feedback on the following code that I would like to submit to Rosetta Code http://rosettacode.org/wiki/Amicable_pairs
I originally kludged together the FORTRAN, Pascal, and C examples into the Crystal language and the below is my translation of that into Nim. (My Crystal version is posted in a similar post on their forum)
My goal is not for the most advanced or most Nim way of getting the job done but to show code that any novice can understand while having a general Nim flavor... without embarrassing Nim as a language either.
Looking for any suggestions to enhance the style or performance without sacrificing novice readability.
The code generates all the amicable pairs from 524000000 down to 2 and on my machine takes 6hrs 32mins to complete.
import math
proc isEven(x: int): bool =
var testx: int = (x shr 1) shl 1
result = (x == testx)
proc sumProperDivisors(someNum: int, chk4less: bool): int =
var sum: int = 1
var maxPD: int = toInt(math.sqrt(toFloat(someNum)).floor)
if isEven(someNum):
for divNum in (2..maxPD):
if someNum mod divNum == 0:
sum = sum + divNum + (toInt(someNum/divNum))
if (chk4less == true) and sum >= someNum:
sum = 0
break
else:
for divNum in countup(3, maxPD, 2):
if someNum mod divNum == 0:
sum = sum + divNum + (toInt(someNum/divNum))
if chk4less == true and sum >= someNum:
sum = 0
break
result = sum
var
startNum: int = 2
endNum: int = 524000000
n: int = endNum
m: int
while n != startNum:
m = sumProperDivisors(n, true)
if m == 0:
n = n - 1
continue
else:
var ntest: int = sumProperDivisors(m, false)
if n == ntest:
echo($m, " ", $n)
n = n - 1
I'm having trouble adding a reply so I'm editing the original post with my reply.
Thank you everyone!!!
Your feedback is exemplary, I couldn't have asked for better.
Nim should be very proud of its community.
I will definitely implement the ideas proposed by OderWat, Nycto, def, and Stefan_Salewski.
I learned a lot just from reviewing and am looking forward to actually stepping through the changes.
I also smacked my forehead a few times too...
using countup in the proc but not countdown for the initial number range >WHACK<
Will need a minute... or three to wrap my head around the algo RPG suggested.
At quick glance it looks like its creating an indexed list of all divSums and comparing the values at indexes m and n...
I will try to walk through it and really understand.
Thanks again to all!!
I would have written those different:
isEven(someNum) replaced by someNum mod 2 == 0 or simply (someNum and 1) == 0.
(toInt(someNum/divNum)) is just someNim div divNum
A quick test seems to shows the same numbers.
takes 6hrs 32mins to complete.
If not for this, I would say that Nim could run this entire application at compile time
Other observations:
Without testing, I may be losing some nuance, but it looks like yoru while loop can be simplified to:
while n != startNum:
let m = sumProperDivisors(n, true)
if m != 0:
if n == sumProperDivisors(m, false):
echo($m, " ", $n)
n = n - 1
As far as the while loop itself is concerned, I would probably factor it out into an iterator to de-clutter the meat of the application itself
Just a quick cleanup, shouldn't change performance:
from math import sqrt
proc sumProperDivisors(x: int, checkLess: bool): int =
template check(divNum) =
if x mod divNum == 0:
result += divNum + x div divNum
if checkLess and result >= x:
return 0
result = 1
let maxPD = sqrt(x.float).int
if x mod 2 == 0:
for divNum in 2..maxPD:
check divNum
else:
for divNum in countup(3, maxPD, 2):
check divNum
#for n in countdown(524_000_000, 2):
for n in countdown(20_000, 2):
let m = sumProperDivisors(n, true)
if m != 0 and n == sumProperDivisors(m, false):
echo m, " ", n
If you want more performance, the other Rosetta Code entries usually give good inspiration.
Edit: Simplified with Nycto's suggestions
The if statements in that for loop can be combined:
if m != 0 and n == sumProperDivisors(m, false):
echo m, " ", n
At this point, I would also argue that the isEven function doesn't need to be split out.
let offset = abs(x) mod 2
for divNum in countup(3 - offset, maxPD, 2 - offset):
check divNum
And so we do not really need the template at all, we can replace it by the actual code.
Using cache and a little trick source could be simplified:
from math import sqrt
# var N = 524000000
var N = 20000
var divSum: seq[int] = @[]
divSum.setLen(N + 1)
for i in 2..N: divSum[i] = 1
for i in 2..sqrt(N.float).int:
for j in i..N:
let p = i * j
if p <= N:
divSum[p] += i + j
else:
break
for n in 2..N:
let m = divSum[n]
if m <= N:
if divSum[m] == n and n < m:
echo n, ' ', m
Best is C version on rosetta but it isn't simple.
Looking at RPGs code I would omit the else and just write:
for i in 2..sqrt(N.float).int:
for j in i..N:
let p = i * j
if p > N: break
divSum[p] += i + j
But using the seq is not so nice if you have high N :)
And finally, allow user to specify N:
import os, strutils
from math import sqrt
var N = 10000000
if paramCount() > 0:
N = parseInt(paramStr(1))
var divSum = newSeq[int](N + 1)
for i in 2..N: divSum[i] = 1
for i in 2..sqrt(N.float).int:
for j in i..N:
let p = i * j
if p > N: break
divSum[p] += i + j
for n in 2..N:
let m = divSum[n]
if m <= N and divSum[m] == n and n < m:
echo n, ' ', m
LOL, @canyonblue77, it was fun for me also.
But does your work computer really have less than two gig memory available or did you not set some magical Windows permission that allows you to use more than two gigs of memory?
Please post a nice clean version to Rosetta. You are repping Nim for us all.
const N = 524000000.int32
const N = 524_000_000.int32
@srwiley: Something is definitely throttling the mem. The system shows 163 KB avail when running the code with 485m,
but the graph shows total usage at only around 60%. There's also about .5G cached for probably no good real reason.
The AMP2 version has been posted to Rosetta.
@Manfred: Tried to make the underscore edits but there's an issue with their site, will do that ASAP though.
How did you manage to change your avatar????
The forum uses Gravatar, simply register on that website with the email address you registered on the forum and you can upload your avatar.
How to make a line break in the forum? Bullet points are pretty lame, LOL
Unfortunately no way AFAIK. Only double breaks.
This should be fixed. Like having a hard-coded |br| using a raw directive.
Until then you can use:
this will
break lines
where I want it
Made like this:
| this will | break lines | where I want it