Tuesday, December 21, 2010

Self-numbers

For any given base, a number is called as Self-number, if it cannot be represented as a sum of another integer and the sum of this integer's digits. Hmm... seems like a pretty simple coding-task. Indeed it is! Sat for about half-an-hour and here (released under GNU-GPL) is the program which can generate first 'n' self-numbers for base 10. I profiled this code and given below are the results:
$ make profile
printCpuInfo.sh
Processor Information:
processor       : 0
vendor_id       : GenuineIntel
model name      : Intel(R) Xeon(R) CPU           E5450  @ 3.00GHz

selfnumber -nooutput -profile -limit 1000001
Found 0 self-numbers among first '1000000' integers.
Took 0.004973 seconds to search for self-numbers among these integers.

selfnumber -nooutput -profile -limit 10000001
Found 0 self-numbers among first '10000000' integers.
Took 0.060016 seconds to search for self-numbers among these integers.

selfnumber -nooutput -profile -limit 100000001
Found 0 self-numbers among first '100000000' integers.
Took 0.597042 seconds to search for self-numbers among these integers.

selfnumber -nooutput -profile -limit 1000000001
Found 0 self-numbers among first '1000000000' integers.
Took 5.440813 seconds to search for self-numbers among these integers.

~5ms for 1 million numbers seems like pretty fast. Isn't it?


UPDATE1:
I moved this program to github. Read-only access for this is at git://github.com/teju85/Self-Numbers.git. I also optimized the inner loop to perform modulus operations only for one in 100 numbers. This way, I was able to reduce the run-time to 2ms for 1 million numbers!

$ make profile
printCpuInfo.sh
Processor Information:
processor       : 0
vendor_id       : GenuineIntel
model name      : Intel(R) Xeon(R) CPU           X5355  @ 2.66GHz

selfnumber -nooutput -profile -limit 1000001
Found 97786 self-numbers among first '1000000' integers.
Took 0.002037 seconds to search for self-numbers among these integers.

selfnumber -nooutput -profile -limit 10000001
Found 977787 self-numbers among first '10000000' integers.
Took 0.018121 seconds to search for self-numbers among these integers.

selfnumber -nooutput -profile -limit 100000001
Found 9777788 self-numbers among first '100000000' integers.
Took 0.185008 seconds to search for self-numbers among these integers.

selfnumber -nooutput -profile -limit 1000000001
Found 97777789 self-numbers among first '1000000000' integers.
Took 1.789393 seconds to search for self-numbers among these integers.

No comments:

Post a Comment