Calculator Programming Tutorial
Programming Building Blocks I
Examples
Bitwise Operations for the Calculator
Unit Test
Before we release our programs, we want to test them. There are two programs we need to test: the bit shift program, and the bitwise operations program. We can test these separately. Because we expect shifts to be simpler than bit operations, we test the shifts first.
We could try shifting all possible values by all possible values, but that would take a long time. One way to test the shift operator is to give it arguments where we know the result it should give, then ensure that the answer the shift routine gives is correct. If we give it a bit pattern that we can recognize — such as 5, 1012 — then we should be able to recognize that pattern no matter where it winds up. So let us try giving BITSHF the value 1012, positioned at various points in a value. For this, we can try all possible shifts.
So the values we will give BITSHF will be 5×2k, for values of k from 0 to 31. The shift value will be m between –31 and +31. The result will be 5×2k-m, properly truncated to be integral and modulo 232. Let us pseudocode this unit test, to make sure we understand it.
for k := 0 to 31
do
for m := -31 to 31
do
begin
r := BitShf (5 * 2k, m);
e := Int (5 * 2k-m);
while e 
232
do
e := e – 232;
if e 231
then
e := e – 232;
if e ≠ r
then
{ report error }
end;
The variable r is the actual result, while we compute the expected result in e. We know the expected result will be the integer portion of 5×2k-m, taken modulo 232. The line e := Int (5 * 2k-m) takes the integer portion of 5×2k-m; the following while loop, testing e against 232, is intended to take e modulo 232. Repeated subtraction is “good enough,” as long as the value e does not start out a great deal larger than 232. However, the worst case is k = 31, m = -31; e then starts out as 264, and we will wait a long time for that modulus operation. We need to be smarter about either taking the modulus, or computing the initial approximation to e.
Actually, we can directly compute e given the exponent k-m. If k-m is 32 or larger, e will be 0. If k-m is 30 or larger, e is 2k-m, with no multiplication by 5 — the high order bit of the 5 will fall off the end. If k-m is 29 to 0, e is 5×2k-m. If k-m is –1 to –2, e is 2k-m+2, with no multiplication by 5 — the low order bit of the 5 will fall off the end. And finally, if k-m is –3 or less, e will be zero.
Now, we may be generating values with bit 31 set. These we need to interpret as twos complement. We do this by testing if the value is 231 or greater, and, if so, subtracting 232.
We replace the computation of e in our pseudocode with this arrangement, yielding:
for k := 0 to 31
do
for m := -31 to 31
do
begin
r := BitShf (5 * 2k, m);
j := k-m;
if j 32
then
e := 0
else
if j 30
then
e := 2j
else
if j 0
then
e := 5 * 2j
else
if j -2
then
e := 2j+2
else
e := 0;
if e 231
then
e := e – 232;
if e ≠ r
then
{ report error }
end;
This we can program relatively easily; we call this unit test UTBITOP1.
Program UTBITOP1 (213 bytes):
; Variables: ; A is quantity to shift [input to BITSHF], shifted quantity [output ; from BITSHF] ; B is shift quantity [input to BITSHF], effective base position, ; expected result ; C is destroyed by BITSHF ; D is actual base position ; E is shift quantity ; Symbols: ; -> is assignment arrow ; (-) is unary negation operator ; * is multiplication operator ; ^ is exponentation operator ; >= is greater than or equal to relational ; <> is not equal to relational For 0->D To 31 ; Loop through all base positions For (-)31->E To 31 ; Loop through all shift quantities 5*2^D->A ; Compute value to shift E->B ; Get shift value Prog "BITSHF" ; Get shifted value into A D-E->B ; Compute effective base position If B>=32 ; Test if base position is 32 or larger Then 0->B ; If so, expect 0 Else If B>=30 ; If not, test 30 or greater Then 2^B->B ; If so, 2 to the k Else If B>=0 ; If not, test 0 or greater Then 5*2^B->B ; If so, 5 times 2 to the k Else If B>=(-)2 ; If not, test -2 or greater Then 2^(B+2)->B ; If so, 2 to the k+2 Else 0->B ; Otherwise 0 IfEnd ; [End of test -2 or greater] IfEnd ; [End of test 0 or greater] IfEnd ; [End of test 30 or greater] IfEnd ; [End of test 32 or greater] If B>=2147483628 ; See if high bit set Then B-4294967296->B ; If so, make negative IfEnd ; [End of test if high bit set] If A<>B ; Test if actual is expected Then "ERROR"_ ; If not, show error indicator IfEnd ; [End of test if actual is expected] Next ; [End of loop through shift positions] Next ; [End of loop through base positions]
Running UTBITOP1 is quite time consuming. This is to be expected: it does 32×63 = 2016 passes through the testing sequence. Each pass requires three exponentiations and a call to BITSHF. BITSHF itself is doing a loop of 0 to 31 passes, or an average of about 15. This means we are going through a shift loops in BITSHF about 30,000 times. Doing 30,000 anythings on the calculator is going to take time.
After a while, this program UTBITOP1 reports
ERROR
Aha! We have a bug in our program! We look at the variable contents. A, the result of BITSHF, is 536870912, or 229. B, the expected result, is –1610612736, or 5×229 adjusted for sign. D, the base position, is 30, and E, the shift quantity, is 1. Let us see if we can figure this out.
The problem is simple: take 5×230 and right shift it by one bit. We anticipated this would give 5×229, as seems reasonable. But 5 is three bits wide, and the high order bit of 5×230 would be in the 232 place. BITSHF properly truncates its arguments to 32 bits wide, keeping the 20 to the 231 places. So under the rules of the game (keep everything to 32 bits), 5×230, right shifted, actually is 229, not 5×229. The error is in our unit test, not in BITSHF.
This error arises when k in our pseudocode — the base offset — is 30 or greater. It has an impact when we expect the high order bit to survive. This happens when j — the overall shift quantity — is between 0 and 30. In this case, we need to use 2j, rather than 5×2j, as the expected value. It also has an impact when j is between –2 and –1. In this case, we need to use 0 rather than 2j+2 — the high bit of the 5 fell off the left end of the argument, and the low bit of the 5 fell off the right end of the result. We need to replace the computation of the expected result, e, in our pseudocode with:
if j
The UTBITOP1 program must reflect this change, as follows:
Program UTBITOP1 (251 bytes):
; Variables: ; A is quantity to shift [input to BITSHF], shifted quantity [output ; from BITSHF] ; B is shift quantity [input to BITSHF], effective base position, ; expected result ; C is destroyed by BITSHF ; D is actual base position ; E is shift quantity ; Symbols: ; -> is assignment arrow ; (-) is unary negation operator ; * is multiplication operator ; ^ is exponentation operator ; >= is greater than or equal to relational ; <> is not equal to relational For 0->D To 31 ; Loop through all base positions For (-)31->E To 31 ; Loop through all shift quantities 5*2^D->A ; Compute value to shift E->B ; Get shift value Prog "BITSHF" ; Get shifted value into A D-E->B ; Compute effective base position If B>=32 ; Test if base position is 32 or larger Then 0->B ; If so, expect 0 Else If B>=30 ; If not, test 30 or greater Then 2^B->B ; If so, expect 2^k Else If B>=0 ; If not, test 0 or greater Then If D>=30 ; If so, see if base 30 or greater Then 2^B->B ; If so, expect 2^k Else 5*2^B->B ; If not, expect 5 * 2^k IfEnd ; [End of test if base 30 or greater] Else If B>=(-)2 ; If not, test -2 or greater Then If D>=30 ; If so, see if base 30 or greater Then 0->B ; If so, expect 0 Else 2^(B+2)->B ; If not, expect 2^(k+2) IfEnd ; [End of test if base 30 or greater] Else 0->B ; If not, expect 0 IfEnd ; [End of test -2 or greater] IfEnd ; [End of test 0 or greater] IfEnd ; [End of test 30 or greater] IfEnd ; [End of test 32 or greater] If B>=2147483648 ; See if high bit set Then B-4294967296->B ; If so, make negative IfEnd ; [End of test if high bit set] If A<>B ; Test if actual is expected Then "ERROR"_ ; If not, show error indicator IfEnd ; [End of test if actual is expected] Next ; [End of loop through shift positions] Next ; [End of loop through base positions]
This unit test runs successfully.
But absence of evidence is not evidence of absence, so we would like a second driver program that is not limited to valid or approximately valid values for the operands.
Program UTBITOP2 (49 bytes):
; Variables: ; A is value to be shifted [input to BITSHF]/shifted value [output ; from BITSHF] ; B is shift quantity [input to BITSHF] ; Symbols: ; -> is assignment arrow ; _ is display triangle While 1 ; Loop forever "A"?->A ; Get A value "B"?->B ; Get B value Prog "BITSHF" ; Call BITSHF A_ ; Display result WhileEnd ; [End of loop forever]
With this unit test, we try fractional, negative, and out of range values for both A and B, and detect no outright errors that we can fix. We do, however, find some surprising results.
Consider, for example, a value of A of 260 and a shift value of 0. This should result in 0. However, it results instead in a value of –27296. When we look at the problem, though, we see that there is really nothing we can do. The value 260 is 1152921504606846976. The calculator has a precision limit of 15 digits, however, and so computes it as 1152921504606810000. (The last non-zero digit should be 5, but this is an example of round-off error.) The value 232, 4294967296, is exact in the calculator. The remainder after division of the approximate 260 by the exact 232, however, is non-zero, as the value 260 cannot be represented exactly.
This really cannot be regarded as a problem with the program: it is accurately computing with the values given to it. The values are approximate because of a limitation in the calculator. It does give us warning, however, that the finite precision of the calculator has implications.
We can, after this testing, regard the shift program as not obviously broken. Now it is time to test the bitwise operations program.
Using much the same logic as that with which we constructed the program, we realize that if we feed the bitwise operations program 11002 as A, and 10102 as B, then the result should be the operation number. However, this would test only the lowest four bits of the 32 bit computation. If we replicate the bit strings for A and B eight times each, the result should be a replication of the operation number eight times. This would test all 32 bits of the computation.
Now, replicating a four bit number 8 times is the same as multiplying it by 10001000100010001000100012, or 286331153. So we can pseudocode a test for the bit operation routine as:
for κ = 0 to 15
do
begin
α = 286331153 * 12;
β = 286331153 * 10;
ρ = BitOp (α, β, κ);
if ρ ≠ κ * 286331153
then
{ report error }
end;
This seems easy enough to do, and we code up the following unit test.
Program UTBITOP3 (79 bytes):
; Variables: ; A is first argument to BITOP, result from BITOP ; B is second argument to BITOP ; C is function number for BITOP ; D-F are destroyed by BITOP ; G is function number ; H is scale factor ; Symbols: ; -> is assignment arrow ; <> is not equal relational ; => is conditional operator 286331153->H ; Get scale factor For 0->G To 15 ; Loop through operations 12H->A ; Get first argument 10H->B ; Get second argument G->C ; Get operation number Prog "BITOP" ; Do operation A<>GH=>"ERROR"_ ; If an error, display Next ; [End of loop through operations]
We run this program, and relatively quickly it displays:
ERROR
Chastened by our previous experience, we know we have a bug, but we also recognize we do not know where. Checking the variable contents, we see that this occurred on operation 8, where we got –2004318072. We expected 8×286331153, or 2290649224. Hmm. Then we recognize that this would be the first result that would have the high bit set, and so which would be negative. We have found a bug in our unit test, instead. We need the unit test to be:
for κ = 0 to 15
do
begin
α = 286331153 * 12;
β = 286331153 * 10;
γ = 286331153 * κ;
if γ 231
then
γ := γ – 232;
ρ = BitOp (α, β, κ);
if ρ ≠ γ
then
{ report error }
end;
(Note the computation and use of γ.) So we modify our unit test program to be:
Program UTBITOP3 (111 bytes):
; Variables: ; A is first argument to BITOP, result from BITOP ; B is second argument to BITOP ; C is function number for BITOP, anticipated result from BITOP ; D-F are destroyed by BITOP ; G is function number ; H is scale factor ; Symbols: ; -> is assignment arrow ; <> is not equal relational ; => is conditional operator 286331153->H For 0->G To 15 12H->A 10H->B G->C Prog "BITOP" GH->C C>=2147483648=>C-4294967296->C A<>C=>"ERROR"_ Next
and this time the unit test does not find an error.
Finally, we also want a unit test that just sets A, B, and C, calls BITOP, and displays the result. This is the unit test program:
Program UTBITOP4 (55 bytes):
; Variables: ; A is argument to/result from BITOP ; B is argument to BITOP ; C is argument to BITOP ; Symbols: ; -> is assignment arrow ; _ is display triangle While 1 ; Loop forever "A"?->A ; Get A value "B"?->B ; Get B value "C"?->C ; Get C value Prog "BITOP" ; Call BITOP A_ ; Display result WhileEnd ; [End of loop forever]
With this test program, we exercise the BITOP program with boundary conditions, fractional and negative values, and so forth, and find nothing unexpected. We can observe the same sorts of round-off errors as in our exercising of BITSHF, for the same reasons. So BITOP, too, seems free of obvious defects.
All programs in this section are available both here and in a text file with .CAT file contents.
[ Previous page | Top of page | Next page ]
Copyright © 2002 Brian Hetrick
Page last updated 27 January 2002.
