Liberty BASIC Programmer's Encyc - LoopOperations

<h1>Operations in a loop</h1>
<em><a class="wiki_link" href="/tsh73">tsh73</a></em>, May - June 2013<br />
<img id="wikitext@@toc@@normal" class="WikiMedia WikiMediaToc" title="Table of Contents" src="/site/embedthumbnail/toc/normal?w=225&h=100"/><hr />
Common operations in a FOR loop. <br />
After all, loops are ubiquitous thing in programming, and having standard loop tricks at your fingertips is a must.<br />
<br />
<h1>Terms</h1>
First, let’s recall our terms.<br />
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:<br />

<pre class="lb">FOR i=1 TO 10 STEP 4<br/>'payload<br/>NEXT i</pre>
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 &quot;print i&quot; as a payload and see.)<br />
STEP is optional – without it, index incremented by 1.<br />
Naming loop variable after NEXT optional too.<br />
<br />
Let’s make a loop that does something.<br />
A loop that prints pairs (x, f(x)) for say sin(x) over interval 0..20 with step 2:<br />

<pre class="lb">for x = 0 to 20 step 2<br/>    y=sin(x)<br/>    print x, y<br/>next</pre>
<br />
<h1>Filter</h1>
First concept is <em>filter</em>. Our loop produces some data; by setting a condition, we could filter it, selecting only things we like.<br />
For example, let’s print only positive values of a function. <br />

<pre class="lb">for x = 0 to 20 step 2<br/>    y=sin(x)<br/>    if y&gt;0 then<br/>        print x, y<br/>    end if<br/>next</pre>
So filter is a condition put in a loop, which checks each iteration and allow for processing only things we like.<br />
Of course you could nest filters. Or use “else” part, if you need to. After all, it’s just conditions.<br />
<br />
<h1>Index, counter, flag</h1>
<br />
<h2>Index</h2>
We already agreed that loop index is just loop variable. Here, x. It runs from initial value till the bitter end with given step.<br />
<br />
<h2>Counter</h2>
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.<br />
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 <tt>FOR x=1 TO 2 STEP 0.1</tt>, then run that loop and see for yourself.)<br />
<em>Counter</em> 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.<br />

<pre class="lb">counter=0<br/>FOR x=0 TO 1 STEP 0.1<br/>    counter = counter+1<br/>next<br/>print &quot;counter =&quot;;counter</pre>
Construction “take some variable, add a thing and put it back” happens in a programs quite often. It is said that variable <em>accumulates</em> something. Here it accumulates counter. <br />
So it really counts stuff that happened. And if we cut it short with EXIT FOR, it will still have correct number.<br />
We don’t have to count *ALL* iterations. Here we are counting only positive values of y:<br />

<pre class="lb">counter=0<br/>for x = 0 to 20 step 2<br/>    y=sin(x)<br/>    if y&gt;0 then<br/>        counter = counter+1<br/>        print x, y<br/>    end if<br/>next<br/>print &quot;counter =&quot;;counter</pre>
Wait! It’s a counter inside a filter! Yep, true ;).<br />
<br />
<h2>Flag</h2>
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.<br />
Common way to handle this – much for clarity sake - usually to peruse special Boolean variable, called <em>flag</em>. 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. <br />
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.<br />
Note: since it is Boolean, it could be checked for true/false without explicit compare operator.<br />
Let’s check if we have any negatives in our loop:<br />

<pre class="lb">flag=0  'false<br/>for x = 0 to 20 step 2<br/>    y=sin(x)<br/>    if y&lt;0 then flag=1  'true<br/>    print x, y<br/>next<br/>if flag then print &quot;We have negatives&quot;</pre>
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:<br />

<pre class="lb">flag = (y&lt;0)</pre>
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. <br />
<br />
<h1>Sum, product, concatenation</h1>
<br />
<h2>Sum</h2>
If we start from zero and add 1 on each loop, we’ll get loop counter.<br />
If we start from zero and add some value (like, value of a function), we’ll get a <em>sum</em> of these values - we accumulate sum.<br />
Here’s we calculate sum of our function, y=sin(x):<br />

<pre class="lb">sum=0<br/>for x = 0 to 20 step 2<br/>    y=sin(x)<br/>    sum=sum+y<br/>    print x, y<br/>next<br/>print &quot;sum= &quot;;sum</pre>
<br />
<h2>Concatenation</h2>
Now, we can accumulate not only sum (numeric) but also strings. Let’s build string containing alphabet:<br />

<pre class="lb">a$=&quot;&quot;   'start with empty<br/>FOR i=asc(&quot;A&quot;) TO asc(&quot;Z&quot;)<br/>    a$=a$;chr$(i)   'accumulate in a string<br/>next<br/>print a$</pre>
I used string concatenation operator, (;) to emphasize that we work on strings, but you can use (+) all the same:<br />

<pre class="lb">a$=a$+chr$(i)</pre>
But you better have in mind that contrary to numerical (+), result of string concatenation depends on order. So with this line instead<br />

<pre class="lb">a$=chr$(i)+a$</pre>
we’ll have our alphabet reversed.<br />
<br />
<h2>Product</h2>
Similar pattern holds for calculating a <em>product</em>: 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.<br />
Let’s calculate n!, defined as 1*2*3…*(n-1)*n:<br />

<pre class="lb">n=5<br/>f=1   'start with 1 for product<br/>FOR i=1 TO n<br/>    f=f*i   'accumulate factorial<br/>next<br/>print &quot;Factorial of &quot;; n; &quot; equals to &quot;; f</pre>
<br />
<h1>Average</h1>
<br />
<h2>Arithmetic mean</h2>
<em>Average</em>, or <em>arithmetic mean</em>, 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.<br />
So, average of all values y=sin(x) in our loop:<br />

<pre class="lb">sum=0<br/>counter=0<br/>for x = 0 to 20 step 2<br/>    y=sin(x)<br/>    sum=sum+y<br/>    counter=counter+1<br/>    print x, y<br/>next<br/>print &quot;average= &quot;;sum/counter</pre>
<br />
<h2>Geometric mean</h2>
If you remember some mean other then arithmetic, it likely involves counter and some operation in a loop. For example, <em>geometric mean</em> is defined as N-th root of a product (has sense only for positive values), where N is counter.<br />

<pre class="lb">product=1   'initial for product always 1<br/>counter=0<br/>for x = 0 to 20 step 2<br/>    y=sin(x)<br/>    if y&gt;0 then<br/>        product=product*y<br/>        counter=counter+1<br/>    end if<br/>    print x, y<br/>next<br/>print &quot;geometric mean for positives= &quot;;product^(1/counter)</pre>
<br />
<h1>Min, max</h1>
<br />
<h2>Minimum </h2>
Let’s have a take on <em>minimum</em>.<br />
Reasonable approach is:<br />
<ul><li>assign first value to minimum variable</li><li>for all other values,<ul><li>compare value to minimum variable</li><li>If it is less then current minimum, we change current minimum to value.</li><li>So minimum variable always has smallest of values encountered so far.</li></ul></li><li>After the loop, this gives us smallest of all values.</li></ul>That would look something like this:<br />

<pre class="lb">x0=0: xEnd=20: dx=2<br/>minimum = sin(x0)   'first value<br/>for x = x0+dx to xEnd step dx  'start from second value<br/>    y=sin(x)<br/>    if y &lt; minimum then minimum = y<br/>    print x, y<br/>next<br/>print &quot;minimum= &quot;;minimum</pre>
It could be simplified a bit, at cost of computer working slightly more.<br />
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  <br />

<pre class="lb">for x = x0 to xEnd step dx</pre>
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).<br />
Second simplification gets rid of separate calculating first value.<br />
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.<br />
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.<br />
So our program ends up like this:<br />

<pre class="lb">x0=0: xEnd=20: dx=2<br/>minimum = 1e10   'impossible value<br/>for x = x0 to xEnd step dx<br/>    y=sin(x)<br/>    if y &lt; minimum then minimum = y<br/>    print x, y<br/>next<br/>print &quot;minimum= &quot;;minimum</pre>
In LB, you can write <br />

<pre class="lb">minimum = min (minimum, y)</pre>
instead of “if y &lt; minimum” line.<br />
<br />
<h2>argMin</h2>
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 <em>argMin</em> (from <em>argument minimum</em>). Getting it pretty straightforward: at the line where we change current minimum, we store current index:<br />

<pre class="lb">if y &lt; minimum then minimum = y: argMin = x</pre>
Interesting thing happens if we have several equal minimal values. Minimum found would be one and the same; but there are several possible argMins. <br />
Which one we’ll get, depends on our test condition. If we test for “&lt;”, argMin will return first value: if “&lt;=”, it’ll return last value.<br />
<br />
<h2>Maximum (and argMax)</h2>
As you already guessed, it’s really similar.<br />
If we change condition in the first program in “Minimum” section from &quot;&lt;&quot; to &quot;&gt;&quot;, program will return maximum. Of course, you'd better rename variable ;)<br />
In the second program, we should also change initial value. While for minimum it starts impossibly big (like &quot;1e10&quot;), here it should start impossibly small (like, “-1e10”).<br />
<br />
<h1>Mixing it together</h1>
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.<br />
Let’s take some examples.<br />
1. Count positive values. <br />
<ul class="quotelist"><li>We already did that in “Counter” section.</li></ul>2. Calculate average negative value.<br />
<ul class="quotelist"><li>Again, pretty clear: we need filter only negative values and apply “average” recipe. Single loop is enough.</li></ul>3. Calculate statistical range. <br />
<ul class="quotelist"><li>It is defined as the difference between the largest and smallest values. Calculate minimum and maximum in the same loop, when report the difference.</li></ul>4. Find minimal value above average. <br />
<ul class="quotelist"><li>That’ll take two loops:<ul class="quotelist"><li>first, we’ll find average;</li><li>in second loop, we apply filter “value &gt; average” and find minimum of what left.</li></ul></li></ul>5. Selecting best pupil from arrays of name$(..) and mark(..). <br />
<ul class="quotelist"><li>Involves finding best mark (maximum) and returning name$ from same array index (argMax).</li></ul><br />
<hr />
<img id="wikitext@@toc@@flat" class="WikiMedia WikiMediaTocFlat" title="Table of Contents" src="/site/embedthumbnail/toc/flat?w=100&h=16"/>