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.

FindBin equivalent in bash

Perl has a really useful module called 'FindBin'. Using this module, one can find the actual directory of the current script and also can find the real name of the script (when the current script is just a symlink). What's the equivalent of it in bash? Answer is 'FindBin.sh'.
I wrote this bash script to imitate the behavior of both $FindBin::RealBin and $FindBin::RealScript. You can find this script here. I uses the environment variable 'PATH' to figure out the dir name and actual name of the current script.

How use it?
It's really simple! 'FindBin.sh' currently accepts 2 command line options: '-bin' and '-script'. '-bin' is equivalent to FindBin::RealBin and '-script' is to 'FindBin::RealScript'. After these commandline options, just pass the name of the current script. (which is generally stored in $0).
Example: myRealBin=`FindBin.sh -bin "$0"` 

Help?
Use the '-h' option with this script in order to know about its usage.

Happy coding!