Example 28 generates meaningless Pythagorean numbers such as 6, 8, and 10. In order to prevent this, all we have to do is to exclude x and y whose greatest common divisor is greater than 1, so we can do that by implanting Example 35 directly into Example 28 as shown below.
100 FOR x=1 TO 100 110 FOR y=x TO 100 120 LET a=x 130 LET b=y 140 DO 150 LET r=MOD(a,b) 160 IF r=0 THEN EXIT DO 170 LET a=b 180 LET b=r 190 LOOP 200 IF b=1 THEN 210 LET z=SQR(x^2+y^2) 220 IF INT(z)=z THEN PRINT x,y,z 230 END IF 240 NEXT y 250 NEXT x 260 END
However, it is not easy to make such a program in many case.
For example, if Example 28 uses a, b, c instead of x, y, z as variable names, the combined programs will not operate normally.
BASIC provides us with many built-in functions, but they are not sufficient.
DEF statements enables us to define a function, but only a function that can be indicated by an expression. BASIC also provides us with facilities with which we can define such a function that can only be found through more complicated processing.
The program shown in the preceding paragraph can be more easily written by denoting the greatest common divisor of 2 numbers a and b as GCD(a,b). To do this, we use an external function definition, so called.
In BASIC, the portion to the END line is called a main program. And the END line is followed by what are called external procedures. An external function definition is one type of a external procedure.
In Example 47, the portion from line 200 to line 280 is the external function definition to define the GCD function. An external function definition starts with an EXTERNAL FUNCTION line and ends with an END FUNCTION line. The EXTERNAL FUNCTION line holds the name of the function and the parameter list, which is parenthesized. If there are two or more parameters, they are delimited with commas.
100 DECLARE EXTERNAL FUNCTION GCD 110 FOR x=1 TO 100 120 FOR y=x TO 100 130 IF GCD(x,y)=1 THEN 140 LET z=SQR(x^2+y^2) 150 IF INT(z)=z THEN PRINT x,y,z 160 END IF 170 NEXT y 180 NEXT x 190 END 200 EXTERNAL FUNCTION GCD(a,b) 210 DO 220 LET r=MOD(a,b) 230 IF r=0 THEN EXIT DO 240 LET a=b 250 LET b=r 260 LOOP 270 LET GCD=b 280 END FUNCTION
The main program and external procedures are called program units.
In a program unit that uses an external function, a declaration statement that holds the name of the external function is written. In the above program, such a declaration statement as line 100 is written to use GCD as the external function in the main program. Writing such a declaration statement makes it possible to do correct operation even if there is a built-in function whose name is the same as the name of the external function. The declaration statement is written in a line above where the function is actually used.
As for the syntax, just the needed function name is written succeeding “DECLARE EXTERNAL FUNCTION”.
In the above program, the GCD function is used in line 130.
This is called an invocation of the function.
Parameters, such as x and y in the above program, written in an invocation are called arguments.
When the GCD function is invoked, the values of the arguments are substituted for the variables a, b, and then the lines of the function definition are executed. The value of the function is decided by a LET statement in the form of substituting for the function name as in line 270.
Each program unit is independent as to variable names. Even if there is a variable of the same name in another program unit, it is a different variable on the computer. For example, if the variables x, y, z in the main program of Example 47 are changed to a, b, c, the program will operate normally.
Utilizing the external function definition makes it easy to find the greatest common divisor of 3 numbers. It is done as follows:
100 DECLARE EXTERNAL FUNCTION GCD 110 INPUT a,b,c 120 PRINT GCD(GCD(a,b),c) 190 END 200 EXTERNAL FUNCTION GCD(a,b) ………… … Same as Example 47 … ………… 280 END FUNCTION
As to a factorial n!, the recurrence formula
0!=1, n!=n•(n－1)! holds.
Therefore 7! can be found by multiplying 6! by 7.
Then 6! can be found by multiplying 5! by 6.
When we decrease the numerical values like the above, finally we reach the formula
0!=1 to solve the problem.
The method to solve a problem by repeatedly recurring to a problem similar but smaller in this manner is called recurrence.
In BASIC it is allowed to invoke itself in a function definition. In the following program, the function FACT uses itself to calculate the factorial in its definition.
Example 48. Factorial
10 DECLARE EXTERNAL FUNCTION FACT 20 INPUT n 30 PRINT FACT(n) 40 END 100 EXTERNAL FUNCTION FACT(n) 110 IF n=0 THEN 120 LET FACT=1 130 ELSE 140 LET FACT=n*FACT(n-1) 150 END IF 160 END FUNCTION
In computer programming, invoking itself in a function defining is known as a recursive invocation. The reason why the recursive invocation goes well in BASIC is that the variables are allocated anew each time the function is invoked. For example, even if line 140 is replaced with
LET FACT=FACT(n－1)*n, the program actually operates correctly.
But if the value of n changes in the course of calculation of
FACT(n－1), it should not correctly operate.
That is, each time the function FACT is invocated, the variable n valid only for that invocation is allocated anew to a different place in the memory.
The Euclidean algorithm, which finds the greatest common divisor, is also a typical example of recursive algorithm.
This algorithm can be written in BASIC as follows.
10 DECLARE EXTERNAL FUNCTION GCD 20 INPUT a,b 30 PRINT GCD(a,b) 40 END 100 EXTERNAL FUNCTION GCD(a,b) 110 LET r=MOD(a,b) 120 IF r=0 THEN LET GCD=b ELSE LET GCD=GCD(b,r) 130 END FUNCTION
Full BASIC is not provided with an instruction to draw a circle, but it is provided with means to define the instruction to draw a circle.
That is called a picture definition.
10 DECLARE EXTERNAL PICTURE circle 20 OPTION ANGLE DEGREES 30 SET WINDOW -8,8,-8,8 40 DRAW circle 50 DRAW circle WITH SCALE(2) 60 DRAW circle WITH SCALE(3,2) 70 DRAW circle WITH SCALE(3,2)*SHIFT(3,4) 80 DRAW circle WITH SCALE(5,3)*ROTATE(60) 90 END 100 EXTERNAL PICTURE circle 110 OPTION ANGLE DEGREES 120 FOR t=0 TO 360 130 PLOT LINES:COS(t),SIN(t); 140 NEXT t 150 END PICTURE
The portion from line 100 to line 150 is called an external picture definition.
In the first line of the external picture definition, the picture name is written following “EXTERNAL PICTURE”.
In the above program, “circle” is the picture name.
An parameter list part can be written as in the case of external function definitions, if necessary.
The picture circle draws a circle of radius 1 with center the origin. to be exact, a regular 360-gon is drawn, but it looks like a circle on the display of the computer.
Each program unit is independent as to OPTION statements. Even if OPTION ANGLE DEGREES is written in the main program, the unit of angle measure is not changed in an external picture definition.
A DRAW statement is used for executing a picture. Such transformation as rotating or scaling with center the origin, or translation can be specified in a DRAW statement.
SCALE(a,b) stands for an expansion of a-fold in the x-axis direction and b-fold in the y-axis direction with the center at the origin, where a and b can be negative numbers. In the case of a=b, it can be written as SCALE(a).
SHIFT(a,b) stands for a translation that moves the origin to the point (x, y).
ROTATE(α) stands for a rotation of angle α with the center at the origin.
Transformations can be composed with *. The composing transformations are executed from the left. For example, SCALE(3,2)*SHIFT(3,4) is scaling first and then parallel shifting.
All of the functionalities of an external subprogram are included in those of an external picture definition,
provided that subprograms have no ability of transformation of graphics.
100 DECLARE EXTERNAL SUB circle 120 SET WINDOW -4,4,-4,4 130 CALL circle(1,-1,2) 140 END 200 EXTERNAL SUB circle(a,b,r) 210 OPTION ANGLE DEGREES 220 FOR t=0 TO 360 230 PLOT LINES: a+r*COS(t),b+r*SIN(t); 240 NEXT t 250 END SUB
Example 51 defines a subprogram circle (a,b,r) that draws a circle of radius r with center at (a, b).
Use a CALL statement to invoke a subprogram. If a subprogram has parameters, the parameters list is described in the same format as for a function.
The picture and subprogram have some characteristics different from the function definition.
One of those is variable parameter (pass by reference).
10 DECLARE EXTERNAL SUB double 20 LET a=3 30 CALL double(a) 40 PRINT a 50 END 100 EXTERNAL SUB double(x) 110 LET x=x*2 120 END SUB
In Example 52, the subprogram double(x) doubles the value of the variable written as an argument.
If a variable is written as an argument of a CALL statement, the invoked subprogram uses the actual area of the variable on the memory as the memory area for the parameter to which the variable has been assigned. Therefore, if the value of the parameter is changed during the execution of the subprogram, the value of the variable also changes.
If the argument is not a variable, for example, a constant, an arithmetic operation or a parenthesize variable, the parameter to which the argument is assigned is allocated to a new memory area and the value of the argument is substituted for it.
For example, if line 30 is changed to “
CALL double (1*a)”, just the numerical value of the calculation result of 1*a is passed to the subprogram and the value of the variable a does not changes.
We consider a problem to find an integer solution of an equation ax+by = c, where a, b, c are integer constants.
When b=0, the solution is obvious. If c can be divided by a, the solution is x=c/a, y can be any, so let y=0.
Conversely, if c cannot be divided by a, there is no solution.
When b≠0, let q be the quotient when a is divided by b, and r the remainder.
Since a=bq+r, the original equation can be replaced by b(qx+y)+rx=c.
Then, if the solution of the equation bu+rv=c is obtained, the solution is x=v, y=u－qv, and if there is no solution for bu+rv=c, the equation has no solution.
Here the solution of bu+rv=c is always fixed. This is because when ax+by = c and bx+ry=c are compared, the coefficient of y is surely close to 0. Since the coefficient of y is an integer, it will surely become 0 after several repetitions.
10 DECLARE EXTERNAL SUB solve 20 INPUT a,b,c 30 WHEN EXCEPTION IN 40 CALL solve(a,x,b,y,c) 50 PRINT x,y 60 USE 70 PRINT "no solution" 80 END WHEN 90 END 100 EXTERNAL SUB solve(a,x,b,y,c) 110 IF b=0 THEN 120 IF MOD(c,a)=0 THEN 130 LET x=c/a 140 LET y=0 150 ELSE 160 CAUSE EXCEPTION 999 170 END IF 180 ELSE 190 LET q=INT(a/b) 200 LET r=MOD(a,b) 210 CALL solve(b,u,r,v,c) 220 LET x=v 230 LET y=u-q*v 240 END IF 250 END SUB
A CAUSE EXCEPTION statement (in line 160) causes an exception of the specified number.
The exception numbers of 1 to 999 are reserved for users.
If the statement that has caused the exception is not enclosed by a WHEN EXCEPTION ～ USE, the exception is propagated to the invoking statement.