THE PUZZLET PAGE


How_Does_It_Work


FUNCTION:  MinInt().  Pass an integer to this function and it finds the minimum-value digit within the integer and return that value to the calling routine. This is one of those functions that are so short you may be tempted to ask why not just put the code in the main routine and save the effort? There are two very good reasons.

Firstly, you may need to repeat this operation many times over from different parts of your program. Having a function means it only has to be typed into the code once. In addition, if you type the function in without error, it is always right. But if you have to type it into several parts of your program, a new opportunity for typos arises each time.

Secondly, it makes for neat top-down programming. The main routine can just say something like: min = MinInt(n). It's immediately clear to even an untutored reader what's going on, an uncluttered appearance is maintained, and the main routine is physically much shorter, making a visual overview much easier.

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

Here's the code:


sub MinInt(m)
' Returns the minimum value
' digit of argument m.
' Will give incorrect result if
' m not within integer limits.
' By Dave Ellis.
def LSD, min: int
min = 9
do
    LSD = m % 10:  get LSD

    if LSD < min
        min = LSD
    endif
    m = m/10: 'chop off LSD
until m = 0: 'all chopped off!
return min

The lines will be numbered below to make a detailed description simpler to follow.

1
2
3
4
5
6
7
8
9
10

def LSD, min: int
min = 9
do

    LSD = m % 10: 
'get  LSD
    if LSD < min
        min = LSD
    endif
    m = m/10: 'chop off LSD
until m = 0: 'all chopped off!
return min

Here's a blow-by-blow description of exactly what the code does.

1

def LSD, min: int.   Declaration of local variables.  LSD holds the Least_Significant (rightmost) digit of the integer currently being processed.  min is used to store the smallest digit of the function's argument discovered so far.

2

min = 9.  If the value in variable min wasn't initialised, it would default to 0.  Most of the time, this would be the incorrect value.  So it's initialised here to its maximum possible value, 9.  As the function works through its process, this value will usually decrease to that of the least digit in the argument. 

3

do.  Opens a do-until loop.

4

LSD = m % 10.  Line 4 uses integer arithmetic. It means "take the remainder of dividing m by 10, and save it in variable LSD, discarding the rest .  Overwrite the value already stored in LSD by this new value." If m is, say, 12345, then m divided by 10 will be 1234 remainder 5. The 5 is the bit we want.  It's saved back into LSD.

5

if LSD < min.  Line 5 is asking the question "Is the value stored in variable LSD less than that stored in variable min?

6

min = LSD.  Line 6 is only executed if the answer to the question posed in line 5 is "Yes."  This means that the new value stored in variable LSD is less than that currently stored in variable min.  In other words, a digit has been found whose value is less than any found previously in argument m.  Clearly, the last value must be discarded and the new one saved. So line 6 is saying "Copy the value stored in variable LSD into variable min, over-writing whatever was already stored there."

7

endif.  Housekeeping - closes if-endif clause opened in line 5.

8

m = m/10.   The instruction m = m/10 means "change the value in m to be equal to m/10." If m is 12345, the new value will be 1234.5, won't it? No! The original declaration defined m as an integer, a number with no decimal part.  So the decimal part is dropped, and we end up with 1234. This has effectively lopped off the LSD.

9

until m = 0.  The 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.  If the last time it processed m it was only one digit long, executing m/10 would reduce it to zero. At that time all processing must be finished, and no more executions of the loop are necessary. This last instruction recognised that condition. It can be paraphrased as "Execute the DO loop again unless m equals zero."

10

return min.  The final line  returns whatever value is currently stored in variable min to the calling routine.  This will, of course, be the argument's least-value digit, as required.


Here's a trace of the function for an argument 539476:

ArgumentLSDminComments
539476   9   Initial conditions
539476   66   6 replaces 9 in min
53947   76   Ignored
5394   44   4 replaces 6 in min
539   94   Ignored
53   33   3 replaces 4 in min
5   53   Ignored
0   3   Final value


MAIN MENU
HOW DOES IT WORK?

Site design/maintenance: Dave Ellis E-mail me!
Last Updated: September 19th, 2010.