The fastest way to check if a number has a zero anywhere?
Dividing by a number other than the cardinality of $ 2 $ will take the same number of operations no matter what the number is. So instead of repeatedly dividing $ x $ by $ 10 $ and testing each remainder against $ 0 $, consider repeatedly dividing $ x $ by $ 10 ^ 6 $ (say) and testing each remainder on a lookup table by $ [0, 10 ^ 6) $ ... The lookup table must indicate "yes" if the remainder contains an internal zero, "no" if it contains no zeros, and "maybe" if the remainder has only leading zeros (in this case, check if $ x $ is currently different and return "yes" or "no" respectively).
Binary zeros: (~ x) would be nonzero if there were zero bits. I am assuming that you are not interested in binary numbers.
If your data starts out as strings, leave it that way. If not, DO NOT convert to strings and then check. The conversion to a string does more work than is necessary to determine the zero digit. This can be language specific. In c or assembly, the conversion will be slower than your own detection algorithm.
For example, if you have base 10 numbers stored as integers (as in c), you can create a lookup table with 1000 items. Lookup [100] = 1, Lookup [123] = 0, etc. Then you will need to divide your input numbers by 1000 instead of 10. The rest is the search index. This can go 3x faster than dividing by 10. The small lookup table will go into the cache. The table is too large and you will experience loss of productivity due to the reel being so slow. In c, unsigned ints can divide faster than signed ones because the optimizer can accept some shortcuts.
Finally, let's look at a few threads for doing this.
I need to develop a quick method as I have to perform these checks for numbers close to 109 in less than 20 seconds.
Ah, a programming question.
Will there be a zero search after converting it to a string?
If all you feed to input is a number on its line that doesn't have zero or trailing zeros, then / 0 / does the trick. But yes, the lines will be the fastest. For a more complex representation with zeros or non-numbers in the mix, you should use this regex for integers:
/^[1-9]+0[0-9]*$|^0$/
This requires a number that has a carrier zero, or a number that is zero. It also accepts integers.
$ cat numbers
375
391
940
493
566
804
800
453
726
527
428
77
984
510
795
077
0
$ egrep '^[1-9]+0[0-9]*$|^0$' numbers
940
804
800
510
0
Decimal numbers can be a little more complex if they are of fixed width. If not, adding a period with each of the two brackets should suffice, unless your decimal numbers start with "0.nnn" instead of ".nnn". Tell me your numbers, I will correct the correct solution.
source to share