THE PUZZLET PAGE


How_Does_It_Work


FUNCTION:  SumPowers().  This is rather a specialised function, but is included in the library as it gets used in different programs occasionally.

When an integer is passed to SumPowers(), the function separates each digit, takes the power of that digit according to its position from the MSD (Most Significant, or left-most, digit), adds the results together, and returns the sum to the calling routine.

Example:  print SumPowers(253) will print out 54. This is due to the fact that 21 + 52 + 33 = 54.

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

Here's the code:


sub SumPowers(s)
' Separates out each digit in argument s
' and raises that digit to the power
' corresponding to its position within s.
' The results are totalised and returned.
' Example: if s = 324, returns 71, since
' 3^1 + 2^2 + 4^3 = 71.
def power, sum: int
power = 1 + log10(s): 'length of s
sum = 0
do
    sum = sum + (s % 10)^power
    s = s/10: 'chop off LSD
    power = power - 1
until power = 0
return sum

Overview:  Logarithms are used to establish the power to which the LSD (least significant, or right-most, digit) needs to be raised, as this will be the greatest power encountered for any particular argument. The value is stored in power.

Integer arithmetic is used to separate out the LSD, and it's raised to the power just established. The result is stored in sum.

The LSD is now chopped off,  power decremented, and the process repeated.  This goes on until every digit in the argument has been raised to the appropriate power and added to sum

When power has been decremented all the way to zero  the process is completed.  sum is returned to the calling routine and the program stops.

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

s is the function's argument which has been submitted by the calling routine. This is the number which the calling routine needs to know the value of according to the specification for summing powers.

Variable power is used to indicate the power that a particular digit is to be raised to.

Variable sum is used to hold the running total of summing the various digits after they've been raised to the appropriate power. The final value of sum is passed back to the calling routine.

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

power = 1 + log10(s)
sum = 0
do
    sum = sum + (s % 10)^power
    s = s/10
    power = power - 1
until power = 0
return sum

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

1

power = 1 + log10(s).  The LSD (Least Significant, or right-most, digit) of the argument will be raised to a higher power than any other in the process.  And the value of that power is going to be the same as the number of characters in the argument.  For instance, for an argument abcd, digit d will be raised to the highest power, 4 in this case. 

Now the length of any number is always one greater than the exponent of that number's base-10 logarithm.  We can use this fact to establish the maximum required value for power, as shown in the example table below.

Typical Arguments
Log10
Exponent + 1
Actual Length
3
0.4771
1
1
29
1.4624
2
2
164
2.2148
3
3
3882
3.5891
4
4

2

sum = 0.  Initialises variable sum ready to begin totalising the various digits raised to the appropriate powers.

3

do.  Opens the main DO loop.

4

sum = sum + (s % 10)^power.  This line is the powerhouse of the function.  It can be paraphrased as:  "Take the remainder of dividing  variable s by 10 and raise it the power stored in variable power, add it the value stored in variable sum, then save the total back into variable sum, overwriting what was stored there previously."

The expression s % 10  is called integer arithmetic.  The result is the remainder of s/10 - the rest is discarded.

Example:  Assume s is 1376.  Dividing by 10 gives 137 remainder 6. The 6 is retained and the 137 discarded.  Using this value, and assuming power has value 3, sum has value 12, the expression
sum = sum + (s % 10)^power would yield 12 + 6^3 = 228. This would be saved in sum, overwriting the previous value of 12.

5

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

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

Remember that s 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 s's new value as 1234 - the 0.5 has been discarded.

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

6

power = power - 1.  This decrements the contents of variable power.  For example, if power contains 3, the expression power = power - 1 will alter its value to 2.

7

until power = 0.  We've reached the end of the DO loop, and it's time to make a decision.  Should the DO loop be executed again, or should the program move on to the next instructions?

This line makes the decision. It can be paraphrased as "Execute the DO loop again unless the value of the newly-decremented variable power is zero.

If it's zero, we've been around the loop as many times as there are digits in argument s, so all its digits have been processed, and it's time to quit.

8

return sum.  Variable sum  now holds the required value, as all s's digits have been processed.  All that's required now is to return this value to the calling routine, and this line carries out that task.

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

MAIN MENU
HOW DOES IT WORK?

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