IsAPower

FUNCTION: IsAPower(). This function takes an integer as its argument. If its argument is a perfect power of some smaller integer), it returns the root integer, otherwise it returns FALSE (0). For example, 316 would return 6, since 316 equals 6³, wherease 79 would return zero, since 79 is prime and cannot therefore be a power of any smaller integer.

The integer used for the argument can be any of the usual IBasic types, as shown below:

Type	Exponent of 2	Value
int	2³⁰	1073741824
uint	2³¹	2147483648
int64	2⁶¹	2305843009213693952
uint64	2⁶²	4611686018427387904

Declaring the function must be done like this:

declare IsAPower(p: int) (or whatever type of integer you choose).

Here's the code:

sub IsAPower(p)
' If argument p is any power of some
' smaller integer, returns the integer,
' otherwise returns 0.
' By Dave Ellis.
def flag, max, pwr, result, root: int
if p % 2 = 0: 'argument even nr?
    root = 2: 'root must be even
else
    root = 3: 'root must be odd
endif
flag = 0
max = sqrt(p): 'limit of search range
do
    pwr = 2: 'lowest possible power
    do
        result = root^pwr: 'test root^power
        if result = p: 'equal to argument?
            flag = -1: 'yes
        else
            pwr = pwr + 1: 'get next power
        endif
    until (flag = -1) | (result > p)
    root = root + 2: 'get next root
until (root > max) | (flag = -1)
if flag = -1: 'argument a power?
    flag = root -2: 'return root
endif
return flag

Overview and Strategy:

Variable root is created to hold the root of the function's argument, p. The first few lines of code are used to determine if the root is even or odd. This is an efficiency, since an odd power must have an odd root, and an even power must have an even root. Later in the program this fact makes it possible to search only half the roots it would otherwise investigate.

Starting with the lowest possible power, the root is tried with successively higher powers until it either equals or exceeds the argument. Obviously, if it equals the argument it's a power of a smaller integer! This process is repeated as necessary, incrementing the root by two each time, until it exceeds the square root of the argument (its maximum possible value).

To make a detailed description of the code itself easier, I've numbered the main routine's lines, as shown below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

' Main Routine
def flag, max, pwr, result, root: int
if p % 2 = 0: 'argument even nr?
    root = 2: 'root must be even
else
    root = 3: 'root must be odd
endif
flag = 0
max = sqrt(p): 'limit of search range
do
    pwr = 2: 'lowest possible power
    do
        result = root^pwr: 'test root^power
        if result = p: 'equal to argument?
            flag = -1: 'yes
        else
            pwr = pwr + 1: 'get next power
        endif
    until (flag = -1) | (result > p)
    root = root + 2: 'get next root
until (root > max) | (flag = -1)
if flag = -1: 'argument a power?
    flag = root -2: 'return root
endif
return flag

Let's take a line-by-line look at the code now, using those line numbers.

def flag, max, pwr, result, root: int. These are the local variable declarations. Note that they are all integer types. Here's a brief description of what each one does:

Variable	What it Does	Range of Values
flag	Indicates that a solution has been found, enabling a quick exit from the do-until loop.	TRUE (-1) or FALSE (0)
max	Indicates the maximum value of root to try with the argument. This cannot exceed the square root of the argument, or the power would be less than 2.	Integer value of the square root of the argument
pwr	Indicates the power to which any given root must be raised.	Minimum 2, maximum when root^pwr equals or exceeds the argument.
result	Holds the value of root^pwr	Minimum 2^2, maximum when root^pwr equals or exceeds the argument.
root	Values to be tried as possible roots of the argument	Minimum 2, maximum equals the integer value of the square root of the argument.

if p % 2 = 0. As explained in the Overview and Strategy notes, an efficiency is available if it is known whether the root is odd or even. This is because an odd power must have an odd root, and an even power must have an even root. It will make it possible to elimiinate 50% of the roots needing examination.

Line 2 gets this information by using integer arithmetic. The % sign in IBasic causes the code to make a division and discard everything from the result except the remainder. So the instruction can be paraphrased as a question: "Is the remainder when dividing the value stored in argument p by 2 equal to zero?" If it is, p is obviously an even number.

root = 2. This line is only executed if the answer to the question posed in line 2 is "Yes," meaning that the argument is an even number. Because of this fact, the first value to be tried as a root of the argument must be the lowest even number possible, 2, and line 3 stores value 2 in variable root.

else. Indicates that, if the answer to the question in line 2 was "No," there is an alternative action, given in the next line.

root = 3. If the code is executing this line, it must be because it has established from line 2 that the argument is an odd number. Therefore it loads variable root with the lowest possible odd value, in this case 3.

endif. Housekeeping - closes the if-endif clause opened in line 2.

flag = 0. Loads variable flag with FALSE (0) preparatory to entering the main do-until loop. This effectively says that the current values of root and pwr being tried as root and power respectively of the argument are not solutions. When a solution is found, the value will be reset to TRUE (-1), enabling a quick exit of the do-until loop.

max = sqrt(p). Variable stores the maximum value to try out as a root of the argument p. This clearly cannot exceed the square root of the argument, since the square of any larger number would be greater than the argument. So line 8 loads the argument's square root into variable max. Once again, integer arithemetic is in use here, though it's not all that obvious.

This function, IsAPower() has to be declared like this: declare IsAPower(p: int). So the code knows p must be an integer. Often it happens that the square root of p won't be an integer, so the code will round it down to an integer. For instance, if p is 47, the square root of which is 6.856, the value assigned will actually be 6, the maximum practical value for a root of 47.

do. All the preparatory work has been done, and the code is now ready to start checks. In line 9 it opens the main do-until loop which contains all the tests. Note that this is an outer loop, controlling the values to be tried out as a root of the argument. Note that the starting root value has already been established in line 8, and will subsequently be controlled from within the do-until loop. There is also an inner, nested do-until loop which we will come to in line 11.

pwr = 2. Initialises trial values for a power to the lowest possible value, 2.

do. This is an inner, nested do-until loop, which holds the current value of root as established by the outer do-until loop fixed while varying the values of pwr to try with it. Note that pwr was initialised in line 10.

result = root^pwr. Right away, the first checks are made with the currently-stored values for root and power. The idea is to see if root^power equals the argument. Thus, line 12 effectively says "Take the value stored in variable root and raise it to the power stored in variable pwr then save the answer in variable result."

if result = p. Now the answers found line 12 are checked against the specificiation. A question is being asked here: "Is the value stored in variable p equal to the value stored in argument p?"

flag = -1. This line is only ever executed if the answer to the question in line 13 is "Yes." It means the code has found a root which can be raised to an power to equal the function's argument - a solution. The success is recorded by saving TRUE (-1) in the variable flag. At the end of the do-until loop, it will enable the code to exit the loop immediately, improving efficiency.

else. Indicates that, if the answer to the question in line 13 was "No," there is an alternative action, given in the next line.

pwr = pwr + 1. If the code is executing this line, it must be because it has established from line 13 that the current values of root and pwr don't yield a solution. Since the outer do-until loop is holding the value of root steady, this line, which is within the inner do-until loop, increases the value stored in pwr by 1 so that the next combination can be tested.

endif. Housekeeping - closes the if-endif clause opened in line 13.

until (flag = -1) | (result > p). The code has now reached the end of the inner do-until loop, and must make a decision: execute the loop again, or move on? There are only two criteria for exiting the loop: one, a result has been found, or two, raising the current value of root to the current value of pwr produces a result greater than the argument. In the former case, there's no need to continue, since the solution has been found, and in the latter case there's no point in continuing because all further trials will be greater than the argument and therefore not solutions.

So line 18 can be paraphrased as: "If the value stored in variable flag is TRUE (-1), or the value stored in variable result is greater than that stored in argument p, quit the do-until loop, otherwise execute it again."

root = root + 2. The code has reached the end of the outer do-until loop. Remember, this loop controls the try-out values for root. In preparation for another execution of the loop, the value stored in root is incremented. Note that it's incremented by 2, as explained above. If it's odd, its stays odd; if it's even, it stays even. The code already knows whether the root is going to be odd or even and has set its search on one or the other. Incrementing root by 2 ensures it keeps to the pattern.

until (root > max) | (flag = -1). This is the end of the outer do-until loop. Once again, the code must make a decision: execute the loop again, or move on? There are only two criteria for exiting the loop: one, incrementing the current value of root produces a result greater than the value stored in variable max, beyond which no solution is available, or a result has been found, indicated by flag's status of TRUE (-1). In the former case, there's no point in continuing because all further trials will be greater than the argument and therefore not solutions, and in the latter case the solution has already been found.

So line 20 can be paraphrased as: "If the value stored in variable root is greater than that stored in variable max, or the value stored in variable flag is TRUE (-1), quit the do-until loop, otherwise execute it again."

if flag = -1. The function has completed its task, and all that remains is to tidy things up and return the result. A check is made here to see if a result has been found. This is done by asking the question "Is the value stored in variabel flag TRUE (-1)?"

flag = root -2. This line is only ever executed if the answer to the question in line 21 is "Yes." It means the code has found a solution. The plan here is to store the solution temporarily in variable flag. You'll see in line 24 why this is done. So line 22 says "Decrement the value stored in variable root by two and store the result in variable flag, over-writing whatever was already stored in there."

The value was decremented by 2 to compensate for the fact that the last instruction within the do-until loop incremented root's value by 2 ready for another iteration if necessary. Since a solution was found, further iterations weren't required, so the value stored in root has to be corrected.

endif. Housekeeping - closes the if-endif clause opened in line 22.

return flag. At this point, flag will have one of two things stored in it: either its initial value of zero, set up in line 7, or the value assigned by line 22. The zero means no solution was found. The alternative value, a non-zero integer, means two things to the calling routine: firstly, a solution was found, and secondly the root of the solution is the actual value in flag.

Whichever of the two possible solution types is stored in flag is now returned to the calling routine and the function is exited, returning control to the calling routine.