Older Version
Newer Version
tsh73
Jun 6, 2013
- "initial upload"
=Operations in a loop= //[[tsh73]]//, June 2013 [[toc]] ---- Let’s have a run with loops. Loops are very ubiquitous thing in programming, and having standard loop tricks at your fingertips is a must. =Terms= First, let’s recall our terms. We will consider single FOR loop (that is, no nesting). It has header (loop operator), and a body (“payload”). Body executes several times (well, that was the idea about loops). Each pass through the loop called “iteration”. In Basic, FOR loop has also word NEXT marking where payload ends: [[code format="lb"]] FOR i=1 TO 10 STEP 4 'payload NEXT i [[code]] Variable in the header (i) is called loop control variable, loop variable, loop counter, or index. It goes from start value (here, just 1) to end value (here 10) with given step. Actually, loop executes until index value gets bigger then end value – and like in our example, it might not exactly hit it. (Put "print i" as a payload and see.) STEP is optional – without it, index incremented by 1. Naming loop variable after NEXT optional too. Let’s make a loop that does something. A loop that prints pairs (x, f(x)) for say sin(x) over interval 0..20 with step 2: [[code format="lb"]] for x = 0 to 20 step 2 y=sin(x) print x, y next [[code]] =Filter= First concept is //filter//. Our loop produces some data; by setting a condition, we could filter it, selecting only things we like. For example, let’s print only positive values of a function. [[code format="lb"]] for x = 0 to 20 step 2 y=sin(x) if y>0 then print x, y end if next [[code]] So filter is a condition put in a loop, which checks each iteration and allow for processing only things we like. Of course you could nest filters. Or use “else” part, if you need to. After all, it’s just conditions. =Index, counter, flag= ==Index== We already agreed that loop index is just loop variable. Here, x. It runs from initial value till the bitter end with given step. ==Counter== If we have a loop that goes from 1 to 10 with step 1 (or STEP omitted), we might be pretty sure loop executes exactly 10 times. If we have no EXIT FOR somewhere inside, that is. But if start value, end value, step turned to be variables, when it might get tricky. (No, we cannot just suppose N=int((endValue-startValue)/step)+1. Just try it on {{FOR x=1 TO 2 STEP 0.1}}, then run that loop and see for yourself.) //Counter// is the answer. We take a variable; set it to 0 before start of the loop; and add 1 to it on each pass. Like this. [[code format="lb"]] counter=0 FOR x=0 TO 1 STEP 0.1 counter = counter+1 next print "counter =";counter [[code]] Construction “take some variable, add a thing and put it back” happens in a programs quite often. It is said that variable //accumulates// something. Here it accumulates counter. So it really counts stuff that happened. And if we cut it short with EXIT FOR, it will still have correct number. We don’t have to count *ALL* iterations. Here we are counting only positive values of y: [[code format="lb"]] counter=0 for x = 0 to 20 step 2 y=sin(x) if y>0 then counter = counter+1 print x, y end if next print "counter =";counter [[code]] Wait! It’s a counter inside a filter! Yep, true ;). ==Flag== Sometimes, we don’t need to know how much times something happened. We just interested to know does it happen at all - or not (do we already have that guy in an array? Are there any enemy pieces left? Etc.). We can use a counter and check if it became greater then zero; it will work. Common way to handle this – much for clarity sake - usually to peruse special Boolean variable, called //flag//. Boolean variable can hold only two values – true and false (happened or not); in BASIC, folks generally use 1 (or -1) and 0, 0 being false. So before loop, we set flag to false (0); on each iteration, we check condition, and if it holds, set flag to true. After loop, we check flag value to gather information if our event happened or not. Note: since it is Boolean, it could be checked for true/false without explicit compare operator. Let’s check if we have any negatives in our loop: [[code format="lb"]] flag=0 'false for x = 0 to 20 step 2 y=sin(x) if y<0 then flag=1 'true print x, y next if flag then print "We have negatives" [[code]] If you recall that logical operations (comparisons) return Boolean result (0 or 1 in LB/JB), you might be tempted to write string that sets flag without IF, like this: [[code format="lb"]] flag = (y<0) [[code]] Don’t do that, it will not work. Flag needs to change only “one way”, from false to true, and stay that way. Without IF, it could change back and forth on any iteration. =Sum, product, concatenation= ==Sum== If we start from zero and add 1 on each loop, we’ll get loop counter. If we start from zero and add some value (like, value of a function), we’ll get a //sum// of these values - we accumulate sum. Here’s we calculate sum of our function, y=sin(x): [[code format="lb"]] sum=0 for x = 0 to 20 step 2 y=sin(x) sum=sum+y print x, y next print "sum= ";sum [[code]] ==Concatenation== Now, we can accumulate not only sum (numeric) but also strings. Let’s build string containing alphabet: [[code format="lb"]] a$="" 'start with empty FOR i=asc("A") TO asc("Z") a$=a$;chr$(i) 'accumulate in a string next print a$ [[code]] I used string concatenation operator, (;) to emphasize that we work on strings, but you can use (+) all the same: [[code format="lb"]] a$=a$+chr$(i) [[code]] But you better have in mind that contrary to numerical (+), result of string concatenation depends on order. So with this line instead [[code format="lb"]] a$=chr$(i)+a$ [[code]] we’ll have our alphabet reversed. ==Product== Similar pattern holds for calculating a //product//: we start with initial value, multiply our variable by a value, put result back to that variable, and get product of all values then loop ends. Obviously, we should not use 0 as initial value. But 1 will do. Let’s calculate n!, defined as 1*2*3…*(n-1)*n: [[code format="lb"]] n=5 f=1 'start with 1 for product FOR i=1 TO n f=f*i 'accumulate factorial next print "Factorial of "; n; " equals to "; f [[code]] =Average= ==Arithmetic mean== //Average//, or //arithmetic mean//, defined as sum of values divided by their number. Or, on our terms, sum / counter. We have already seen both, and could calculate them in a single loop. So, average of all values y=sin(x) in our loop: [[code format="lb"]] sum=0 counter=0 for x = 0 to 20 step 2 y=sin(x) sum=sum+y counter=counter+1 print x, y next print "average= ";sum/counter [[code]] ==Geometric mean== If you remember some mean other then arithmetic, it likely involves counter and some operation in a loop. For example, //geometric mean// is defined as N-th root of a product (has sense only for positive values), where N is counter. [[code format="lb"]] product=1 'initial for product always 1 counter=0 for x = 0 to 20 step 2 y=sin(x) if y>0 then product=product*y counter=counter+1 end if print x, y next print "geometric mean for positives= ";product^(1/counter) [[code]] =Min, max= ==Minimum == Let’s have a take on //minimum//. Reasonable approach is: * assign first value to minimum variable * for all other values, ** compare value to minimum variable ** If it is less then current minimum, we change current minimum to value. ** So minimum variable always has smallest of values encountered so far. * After the loop, this gives us smallest of all values. That would look something like this: [[code format="lb"]] x0=0: xEnd=20: dx=2 minimum = sin(x0) 'first value for x = x0+dx to xEnd step dx 'start from second value y=sin(x) if y < minimum then minimum = y print x, y next print "minimum= ";minimum [[code]] It could be simplified a bit, at cost of computer working slightly more. First, if loop start from first value, all we have is extra calculating of sin(x0). Resulting value of minimum will not change. This leaves us with line [[code format="lb"]] for x = x0 to xEnd step dx [[code]] As a bonus, having all values processed in the same manner is beneficial – you likely could reuse same loop for some other task (as we did, printing function table). Second simplification gets rid of separate calculating first value. Instead, we will set minimum initially to impossible value, so that first check sure change it to real one. Usual choice is something obviously big, like 1e10. This came with a bonus, too. If we insert a filter, we cannot be sure beforehand what first value passes through filter. Getting rid of separately calculating first value solves this problem. So our program ends up like this: [[code format="lb"]] x0=0: xEnd=20: dx=2 minimum = 1e10 'impossible value for x = x0 to xEnd step dx y=sin(x) if y < minimum then minimum = y print x, y next print "minimum= ";minimum [[code]] In LB, you can write [[code format="lb"]] minimum = min (minimum, y) [[code]] instead of “if y < minimum” line. ==argMin== Pretty often you need to find not only minimum value, but an argument (or loop index) that provides that value. In math, this thing called //argMin// (from //argument minimum//). Getting it pretty straightforward: at the line where we change current minimum, we store current index: [[code format="lb"]] if y < minimum then minimum = y: argMin = x [[code]] Interesting thing happens if we have several equal minimal values. Minimum found would be one and the same; but there are several possible argMins. Which one we’ll get, depends on our test condition. If we test for “<”, argMin will return first value: if “<=”, it’ll return last value. ==Maximum (and argMax)== As you already guessed, it’s really similar. If we change condition in the first program in “Minimum” section from "<" to ">", program will return maximum. Of course, you'd better rename variable ;) In the second program, we should also change initial value. While for minimum it starts impossibly big (like "1e10"), here it should start impossibly small (like, “-1e10”). =Mixing it together= These operations, in fact, are building blocks. Also, you can insert any operation inside a filter. Then you master them, some tasks will decompose themselves into easily understand pieces. Let’s take some examples. 1. Count positive values. > We already did that in “Counter” section. 2. Calculate average negative value. > Again, pretty clear: we need filter only negative values and apply “average” recipe. Single loop is enough. 3. Calculate statistical range. > It is defined as the difference between the largest and smallest values. Calculate minimum and maximum in the same loop, when report the difference. 4. Find minimal value above average. > That’ll take two loops: >> first, we’ll find average; >> in second loop, we apply filter “value > average” and find minimum of what left. 5. Selecting best pupil from arrays of name$(..) and mark(..). > Involves finding best mark (maximum) and returning name$ from same array index (argMax). ---- [[toc|flat]]