QUICKBASIC/QBASIC TUTORIAL RE: ALGORITHMS
=========================================
By Edward F. Moneo
TABLE OF CONTENTS:
-----------------
1. INTRODUCTION
2. DETERMINE IF A NUMBER IS A POWER OF 2
3. GENERATE A GRAY CODE PATTERN
4. COMPUTE THE NEXT MULTIPLE
5. COMPUTE THE NEAREST MULTIPLE
6. ROUNDING NUMBERS
7. INPUT ONE AND ONLY ONE CHARACTER
8. REPRESENT A NUMBER AS BINARY BITS
9. BIT OPERATIONS
10. CENTIGRADE/FAHRENHEIT CONVERSION
11. GENERATE A RANDOM NUMBER
12. EUCLID'S ALGORITHM FOR GREATEST COMMON DIVISOR
1. INTRODUCTION
The following is a collection of algorithms or proven methods for solving
common problems. Before you incorporate any of these into your programs,
it is recommended that you fully understand the code, and that you test
the algorithm with the range of numbers that you intend using. You will
notice that for the most part, with few indicated exceptions, there are
no type declarations on the variables used, and therefore, as a default,
integer variables are assumed, and the logic has been tested using integers.
Also, with few indicated exceptions, the variables are assumed to be
positive numbers.
It is important to note that many of the following algorithms were
chosen as the best available under intensive scrutiny and testing by
members of the Qbasicnews and QBNZ forums.
NOTE: Credit is given for code developed by other programmers. If no
credit is indicated, the code was developed by the author.
2. DETERMINE IF A NUMBER IS A POWER OF 2:
CREDIT: Xhantt of Qbasicnews.
GIVEN: N is the positive number in question.
LOGIC: When you AND a number which is a power of 2
with the number-1, which would be all 1 bits,
then if the result is zero (because no other bits were found),
then the number must be a power of 2.
if (N>0) and ((N and (N-1))=0) then print N; " is a power of 2"
3. GENERATE A GRAY CODE PATTERN:
CREDIT: author unknown
Gray Code, named after Frank Gray of Bell Labs, is a series of bytes
or words where each byte/word in the series differs from the preceding
BY ONLY ONE BIT. Example: 0, 1, 3, 2, 6, 7. These patterns have been
used for testing logic circuits, communication transmissions, etc.
GIVEN: Generate a Gray Code pattern for values from 0 to 255.
for x=0 TO 255
GRAY = x XOR (INT(x/2))
rem ...Here you print or output successive Gray Code values in GRAY.
next x
4. COMPUTE THE NEXT MULTIPLE:
GIVEN: Given a positive number N, compute the NEXT multiple of X.
Result to R.
EXAMPLE #1: Given 47, compute the next multiple of 5, which is 50.
EXAMPLE #2: Given 50, compute the next multiple of 5, which is 55.
R = int((N+X)/X)*X
5. COMPUTE THE NEAREST MULTIPLE:
GIVEN: Given a positive number N, compute the NEAREST multiple of X.
Result to R.
Note: Nearest multiple means that if N is already a multiple of X,
don't move up to next multiple. This is kind of like rounding;
e.g., round to nearest $5. If already $5, leave it alone.
EXAMPLE #1: Given 47, compute the nearest multiple of 5, which is 50.
EXAMPLE #2: Given 50, compute the nearest multiple of 5, which is 50.
R = int((N+X-1)/X)*X
6. ROUNDING NUMBERS (POSITIVE OR NEGATIVE):
CREDIT: Oracle of Qbasicnews and QBNZ.
The purpose is to round positive or negative numbers to the nearest whole
number. The standard convention of "half-adjusting" by a rounding factor of
.5 is used. Notice that positive numbers must be rounded up, and negative
numbers are rounded down, that is, to a greater negative number.
NOTE: If you do INT(123.9) you will get 123. However, if you do INT(-123.9)
you will get -124. This is the documented method of how the INT works
in QB, which in the case of the INT(-123.9), is NOT what we want,
since we want -123.
The following code takes the above conditions into consideration.
* The absolute or ABS assures that the number to work with is positive.
* This positive number is rounded by the rounding factor of "+.5".
* The integer value INT is taken on the above positive result.
* The sign of the original input number is restored by multiplying by the
sign or SGN which is 1 for positive, -1 for negative, and 0 for zero.
GIVEN:
* N is the number to be rounded. Obviously, since it can have decimals,
it must have a type declaration of single or double floating point.
We will define it as single (!) for this example.
* R will be the resultant rounded whole number.
R = SGN(N!) * INT(ABS(N!) + .5)
7. INPUT ONE AND ONLY ONE CHARACTER:
GIVEN: With the following routine, we want to input only one character,
and if the user enters more than one character, we want to get rid
of the extra characters.
We get rid of the extra characters in order that they will not be
processed later by any code performing an input or an inkey$.
Example: If we ask the user for a yes/no answer and prompt him to
enter Y or N, he could by error type in NO. If we don't get rid
of the extra O, then it will be given as input to the next prompt.
* Input the one character into TheKey$
DO
TheKey$=INKEY$
LOOP WHILE TheKey$=""
WHILE INKEY$<>"":WEND
8. REPRESENT A NUMBER AS BINARY BITS:
GIVEN: Assume N is from 0 to 255; that is, 8 bits.
zbin$="00000000"
for X = 0 to 7
if (N and 2^X) then mid$(zbin$,(X xor 7)+1,1)="1"
next X
print zbin$
8a. A similar approach:
CREDIT: Francisco Moneo of ITAM University.
DIM BIN AS LONG
BIN=0
FOR X=0 TO 7
IF (N AND 2^X) THEN BIN=BIN+10^X
NEXT X
PRINT RIGHT$("00000000"+LTRIM$(STR$(BIN)),8)
9. BIT OPERATIONS:
Here are some useful bit operations:
9a. Flip a switch that has a zero or one value.
switch = switch xor 1
9b. Another method to flip a switch that has a zero or one value.
CREDIT: WhiteTiger0990 of Qbasicnews.
switch = 1 - switch
9c. Yet another method to flip a switch that has a zero or one value.
This works, but it's tricky. Note that the expression switch=0
will evaluate as true (-1) or false (0) before performing the AND 1.
CREDIT:Oracle of Qbasicnews and QBNZ.
switch = (switch = 0) AND 1
9d. Flip a switch that has a zero (false) or minus one (true) value.
switch = not(switch)
9e. NOTE: When testing a switch that has a zero or one value,
you must specify the complete expression when doing an IF.
if switch = 1 then goto swon 'This is correct
if switch = 0 then goto swoff 'This is correct
if switch then goto swon 'This is not correct
9f. NOTE: When testing a switch that has a zero (false)
or a minus one (true) value, you must may test the switch as follows:
if switch then goto swon 'This is correct
if not(switch) then goto swoff 'This is correct
if switch = -1 then goto swon 'This is also correct
if switch = 0 then goto swoff 'This is also correct
The recommended and more explicit way of handling switches
with zero (false) and minus one (true) is as follows:
CONST FALSE = 0 ' 0
CONST TRUE = NOT(FALSE) ' -1
if switch = TRUE then goto swon
if switch = FALSE then goto swoff
9g. Perform an XOR without using the XOR operator.
GIVEN: Perform the equivalent of a XOR b.
result = (a and not(b)) or (b and not(a))
10. CENTIGRADE/FAHRENHEIT CONVERSION:
GIVEN: Convert Centigrade degrees in C# to Fahrenheit degrees in F#.
F# = 9/5*C# + 32
GIVEN: Convert Fahrenheit degrees in F# to Centigrade degrees in C#.
C# = 5/9*(F# - 32)
11. GENERATE A RANDOM NUMBER:
GIVEN: Generate a random integer greater than or equal to the LOWER
parameter and less than or equal to the UPPER parameter.
RANDOMIZE TIMER 'Seed the random number generator
'(You must do this at the beginning of your program)
RandInt% = INT(RND * (UPPER - LOWER + 1)) + LOWER
12. EUCLID'S ALGORITHM FOR GREATEST COMMON DIVISOR:
CREDIT: Donald E. Knuth's book "The Art of Computer Programming,
Volume 1: Fundamental Algorithms".
GIVEN: Find the GREATEST common divisor for two non-zero,
positive numbers M and N.
IF M