THE PUZZLET PAGE


How_Does_It_Work


FUNCTION:  IsUpOrdered().  An "UpOrdered" number is an integer whose digits are all in ascending order, left to right, such as 123, 46779, etc.

When an integer is passed to IsUpOrdered(), the function checks out  all of its argument's digits. If they are arranged as described above, TRUE (-1) is returned, otherwise FALSE (0).

In this version, repeated digits are allowed, as in the case of 46779. It's a very simple matter to exclude repeated digits if this is required. Just add an "=" sign after the "<" sign in line 4 as defined and explained later.

It's up to you what kind of integer you pass to the function, as long as the function declaration has already taken this data-typing into account. See the table below for the parameter limits.

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 IsUpOrdered(d: int) (or whatever integer type you want).

Here's the code:


sub IsUpOrdered(d)
' If the digits of argument d are
' arranged in ascending order returns
' TRUE (-1), else returns FALSE (0).
' Note: this algorithm is around four
' times faster than a string method.
def flag, LSD: int
flag = -1
do
    LSD = d % 10: 'store LSD
    d = d/10: 'chop off LSD
    'is new LSD bigger than old LSD?
    if LSD < d % 10
        flag = 0: 'abort - not ordered
    endif
until not flag | d <10
return flag

Overview:  Variable d holds the number to be checked for ascending orderliness.  The code copies the LSD (Least Significant, or rightmost, Digit) into variable LSD, then chops the LSD off d, so that a new LSD exists on the end of d (what used to be the second last digit, in fact).

Now the new LSD is compared to the contents stored in variable LSD.  If LSD is less than the new LSD, d wasn't in ascending order, so no further checks are made.  The function quits, returning FALSE (0) to the calling routine.

If 
LSD isn't less than the new LSD, ascending orderliness hasn't been disproved yet, so another round of checks as above is carried out.  Each time these checks are carried out, d gets a bit shorter since its LSD is being chopped off every time. 

Eventually, if no failures in orderliness are detected, d will be reduced to zero length.  When this happens, TRUE (-1) is returned to the calling routine.


Let's look at the variables before we begin on the code detail.

d is the function's argument which has been submitted by the calling routine. It's asking the question "Is d an UpOrdered number?" and expects one of two replies: TRUE (-1) or FALSE (0). IsUpOrdered()'s job therefore is to determine d's ascending orderliness and respond accordingly.

Variable flag is used to indicate d's orderliness. It's set to TRUE (-1) to begin with, and will stay that way unless d is found not to be ordered, at which point it will be reset to FALSE (0). The code picks the change up and aborts further investigation, making the function work more efficiently.

Variable LSD is used to hold d's LSD (that is, the least significant, or rightmost, digit). In this function, d is repeatedly shortened by chopping off the rightmost digit. Everytime this happens, a new rightmost digit appears, and this is loaded into LSD. So the contents of this variable change all the time.

To make it simpler to follow a detailed code description, I've numbered the lines as shown below.


1
2
3
4
5
6
7
8

do
    LSD = d % 10
    d = d/10
    if LSD < d % 10
        flag = 0
    endif
until not flag | d <10
return flag

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

1

do.  Opens the main DO loop.

2

LSD = d % 10.  We can paraphrase this expression as "Divide d by 10 and save the remainder in variable LSD." Such a division is called integer arithmetic. 

Example:  Assume d is 12345.  Dividing by 10 gives 1234 remainder 5. The 5 is saved in LSD.  So you can see that the effect is simply to find d's own LSD and save it in variable LSD.

Note two important things here. Firstly, only the remainder of the division is saved. Secondly, d itself isn't changed when this line is executed, because we didn't save anything into d itself, so whatever was there remains there.  You could therefore more accurately paraphrase the line as "Find out what the remainder would be if d were to be divided by 10, and, without actually changing d, save that remainder in variable LSD."


3

d = d/10.  To paraphrase the expression, "Divide variable d by 10 and save the result in d  itself, over-writing the original contents." 

This line performs a neat operation.  To explain it, let's assume that d has value 12345.  Normally, dividing it by 10 would give 1234.5, but something else happens here.

Remember that d was declared as an integer in the declaration? That means that it must remain an integer, no matter what we do to it. And an integer contains no decimal part. So the operation on this occasion gives d's new value as 1234 - the 0.5 has been discarded.

Thus, the operation in effect says "Chop off the rightmost digit of LSD."


4

if LSD < d % 10.  Once again, a paraphrase can help us understand this expression more clearly: "Divide variable d by 10. Is value already stored in variable LSD less than the remainder?"

It's important to remember that the value stored in LSD was obtained from the last digit of d a couple of lines back, and that since then d's rightmost digit has been chopped off. So they're now two different animals!

Why are we making this comparison? Assume d started with value 1235446. After one execution of lines  2 and 3, LSD contains 6 and d now contains 123544. So d %10 will yield 4. Thus, at the moment, LSD is not greater than d % 10.

The next time around the DO loop things have changed, because lines 2 and 3 have been executed again. 
LSD now contains 4 and d now contains 12354. So d %10 will also yield 4. At the moment, although both contain 4, LSD is not greater than d % 10.

As mentioned in the introductory remarks, this acceptance of identical digits depends on the expression saying "
if LSD < d % 10". Changing to "if LSD <= d % 10." will make it reject identical digits as well due to the insertion of the "=" sign there.

A third time around the DO loop things have changed again.  LSD now contains another 4 and d now contains 1235. So d %10 will yield 5. Thus, at this time, LSD is greater than d % 10.

5

flag = 0.  If the code reaches this line, it found two successive digits weren't equal to each other and weren't in ascending order. It immediately sets flag to zero so that the code will be able to quit without wasting time on further unnecessary digit checks.

6

endif.  Housekeeping - closes IF-ENDIF clause opened in line 4.

7

until not flag | d < 10The 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 | d < 10 is the decision-maker.  It can be paraphrased as "execute the DO loop again unless either flag is FALSE (0) or the value of d is less than 10."

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-ordered digit has been found, so there's no need to look at any more of d's digits. The function can return the FALSE (0) immediately.

And the alternative for exiting the DO loop is if d is less than 10. Remember, d's length is decremented by 1 each time the DO loop executes without finding a non-ordered digit. So, eventually, if all the digits are ordered, d will be shortened to just 1 digit - obviously having value less than 10. Since there is no other digit to its left to compare to, the necessary digit checks are complete and the program can quit.

8

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 ascending orderliness of d.

This code was originally written with a different algorithm, using strings. This version runs abour four times faster.

MAIN MENU
HOW DOES IT WORK?

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