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!
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