Vampire search algorithms
My search program uses several techniques to achieve the speed.
My program searches for vampires c=d · e with two nested loops. The outer loop varies d and the inner loop e. I use modulo 9 arithmetic to reduce the number of tests. Some d don't have to be tested and the rest only requires every 9th e to be
My time critical inner loop uses no multiplication or division. This is possible when e values in arithmetic progression are tested.
When testing d · e I store some values and the next test is d · (e+9)=d · e+9 · d.
I precompute 9 · d in the outer loop for d and reuse the just computed d · e. Only additions are left to find the new product.
I found a method to compute and compare digit counts very fast. During initialization I count the digits in 0-9999 and store each count in a dig table of 32-bit integers. I use 3 bits per digit (leaves 2 unused bits), e.g. decimal 3309 is represented in octal as dig=1000002001, where the first octal digit is the number of 9's.
Both d, e and c=d · e are computed and stored 4 digits at a time using carries.
Let | be concatenation of 4-digit groups with c=c3|c2|c1|c0, d=d1|d0, e=e1|e0. The vampire test is simply to test whether:
dig[c3]+dig[c2]+dig[c1]+dig[c0] = dig[d1]+dig[d0]+dig[e1]+dig[e0]
No slow division to find decimal digits is required. I chose to only store 4 digits at a time because the dig table fits in the cache ram and access is much faster. Using only 3 bits per digit gives "overflow" if a digit occurs at least 8 times on a side of (* ). If a vampire is tested then there is matching overflow on both sides and no problems. Theoretically overflow could also give false positives on non-vampires so I double-check all vampires with a slower method (this turned out to never be necessary). The slower method is actually just a variant with a 64-bit dig table using 4 bits per digit to avoid overflow.
For additional speed, I use the standard idea of moving as much code as possible out of the inner loop, so (*) is not used in precisely that form.
The 14-digit vampires gives a lot of output. This was no problem with a big
hard disk. The 208496456 vampire equations c=d · e filled a 7 GB text file sorted by d. I used the dos sort command to sort it
lexicographically which was equivalent to a numeric sort by c. I was a little worried about the size but sort had no problems. It required a 7 GB temporary file in addition to the 7 GB source and target files but I had 21 GB available - good that
hard disks get bigger and cheaper :-) It was easy to write a program to scan the sorted file for adjacent lines with the same c.
I am not going to compute and count the 16-digit vampires. In addition to taking months, this would give my
hard disk problems! Actually I have thought about how to do it and it is possible to compute the vampires in intervals, sort and count each interval, delete it and move on. If I had several PC's available - maybe... I only have my own and want to use it for other number theoretic purposes.
The C source computes all 12-digit vampires. It takes no input and it outputs to stdout which can be redirected to a 128 MB file.
Sorry the source looks a little messy. The above algorithm descriptions should be much easier to understand.