THE PUZZLET PAGE


How_Does_It_Work


FUNCTION:  AllDigitsSame().  Pass an integer to this function and it will inspect each digit in the integer. If they're all identical (such as 999, or 222222, etc) the function returns TRUE (-1), otherwise it returns FALSE (0).

It's up to you what data type you make the argument, depending on the type of integer you want to process.


Type

Exponent of 2
Value

int 230 1073741824
uint 231 2147483648
int64 261 2305843009213693952
uint64 262 4611686018427387904

Declaring the function must be done like this:

declare AllDigitsSame(p: int) (or whatever integer type you want).

Here's the code:


sub AllDigitsSame(n)
' If all the digits of argument n
' are the same returns TRUE (-1),
' otherwise returns FALSE (0).
' Note: this algorithm is approx.
' three times faster than one
' using strings.
def flag, LSD: int
LSD = n % 10: 'store LSD
n = n/10: 'chop off LSD
flag = -1
do
    if n % 10 <> LSD: 'different digit
        flag = 0
    else
        n = n/10: 'chop off LSD
    endif
until not flag | n = 0: 'fail or finish
return flag

Variable flag is a flag used to store the code's result.  It can hold -1 or 0, corresponding to TRUE or FALSE. When a non-identical digit is found before they've all been checked, it prevents further unnecessary checks, improving the efficiency of the code. Ultimately, it is this value which must be returned to the calling routine. 

Variable LSD is used to hold the LSD (least significant, or right-most, digit) of argument n at the beginning of the routine. Later you'll see that is progressively made shorter by digits being chopped off from the right. So it is continuously having a different LSD. However, the original remains stored in variable LSD, and never changes.

In the description of the code which follows, I have applied line numbers to make it easier to follow. Here they are:

1
2
3
4
5
6
7
8
9
10
11

LSD = n % 10
n = n/10
flag = -1
do
    if n % 10 <> LSD
        flag = 0
    else
        n = n/10
    endif
until not flag | n = 0
return flag

Now for a line-by-line exegesis of the code.

1

LSD = n % 10.  This expression can be paraphrased as "Divide n by 10 and save the remainder in variable LSD." For example, assume n = 24638. Dividing by 10 leaves a remainder of 8. This is, of course the least significant digit, so saving it in LSD has achieved the desired result.

The reason for this is that the code can now compare the rest of n's digits one at a time with LSD. If it finds even one that is different from LSD, it knows they can't all be identical.

Be aware that we haven't actually altered n's value at this time, because we didn't save the result anywhere. n still has the value before the trial division took place.

This type of operation is known as integer arithmetic. The same is true of line 2, and the same types of operation appear within the main DO loop as well.

2

n = n/10.  To paraphrase this line as well, we can say "Divide n by 10, throw away any remainder, and save the result back into n."  To illustrate, using the previous value for n of 24638. Dividing by 10 gives 2463 remainder 8. Throw the 8 away and store the rest in n, which is now 2463.  The net effect of this action is to discard n's least significant digit. And this time, of course, n's value is permanently changed.

The reason this works is that n was set as an integer in the declaration of the function. This means that it can't have a decimal part.  Going back to the value of 24638 for a moment. 24638/10 would normally be 2463.8, but since we're assigning the result back to n (an integer), the decimal part is discarded and we end up with 2463.

3

flag = -1. Sets variable flag to TRUE (-1). Thus, the code assumes all n's digits are the same for the time being.

4

do.  Opens the main DO loop. The code will continue to execute within this loop until either it finds a digit that's different to the rest, or it has checked them all and found they're all the same.

5

if n % 10 <> LSD.  This is the actual digit comparison. The expression means "If the remainder of dividing n by 10 isn't equal to the value stored in LSD ... " Once again, n's current value isn't actually changed by this line.

6

flag = 0.  If the code reaches this line, it means a digit has been found which is different to the least significant digit. The flag is set to FALSE (0) so that the search can stop, as we'll see in line 10 below.

7

else.  This line provides for alternate action in the event that the last digit examined was identical to LSD.

8

n = n/10.  And this is the alternate action - chop off the current LSD (not the original one; that's still stored in variable LSD).  This line works in exactly the same way as line 2, explained above.

9

endif.  Housekeeping. Closes the IF-ENDIF clause.

10

until not flag | n = 0The code now reaches the end of the DO loop. It needs to decide whether to execute the loop again, or just move on to the next instruction.

The line
until not flag | n = 0 is the decision-maker.  It can be paraphrased as "execute the DO loop again unless either flag is FALSE (0) or the value of n equals zero."

The "
until not flag" may appear confusing, but it's actually simple. The normal phrase is "until flag" and means "execute the DO loop until flag is set to TRUE (-1)." So "until not flag" means the opposite: "execute the DO loop until flag is set to FALSE (0)."

Clearly, if flag is FALSE (0), a non-identical digit has been found, so there's no need to look at any more of n's digits. The function can return the FALSE (0) immediately.

And the alternative for exiting the DO loop is if n equals zero. Remember, it's decremented by 1 each time the DO loop executes without finding a non-identical digit. So, eventually, if all the digits are identical to LSD, n will reach zero.

11

return flag.   One of those two alternatives will cause the last line of code to be executed: return flag. The calling routine will thus receive either a FALSE (0) or TRUE (-1), corresponding to the presence or absence of non-identical digits within n.


Earlier versions of this function used strings, but I have found this method, using integer arithmetic, is about three times faster.


MAIN MENU
HOW DOES IT WORK?

Site design/maintenance: Dave Ellis E-mail me!
Last Updated: February 3rd, 2010.