GFA BASIC 32‎ > ‎

How To

These are How To articles I've written about GFA BASIC 32.

05 Calculating Prime Numbers

posted Aug 20, 2015, 4:50 PM by Troy Cheek   [ updated Aug 20, 2015, 4:51 PM ]

http://www.wbur.org/npr/102871918
Can you calculate prime numbers using GFA BASIC 32?  Of course you can, but only very small ones.

A prime number is an integer whose only two factors are one (1) and itself.  In other words, you can only evenly divide it (no remainder) by 1 and itself.  Zero (0) isn't prime because you can't divide it by itself (0/0 makes the universe implode).  One (1) isn't prime because you need two factors and we're already using one as part of the definition.  Trying to make one prime is like trying to take yourself as your own date to the prom.  Again, the universe implodes.  So, the first prime is two (2) followed by three (3) and it gets complicated from there.

Most of the time when I work with integer numbers in GB32, I use the Int, Int32, Integer32, Long Data Type.  All those are different ways of saying the same thing:  a 32 bit signed integral value.  32 bits means that it can hold up to 2^32 different values.  Since we need to reserve one bit to tell us the sign (positive or negative), that leaves us 2^31 different values.  Since we have to leave room for zero, the largest number we can store is 2^31-1 or 2147483647.  That's about 2 billion.  I tend to use Int32 because it was the default data type in earlier versions of GFA BASIC, GB32 math runs faster with integers, and 32 bit integers are fastest of all because GB32 is, as the name implies, a 32 bit application.

I hardly ever use Int16, Integer16, Word, Short Data Type.  I can only hold numbers up to 2^15-1 or 32767.  The Card data type is unsigned so it can store 2^16-1 or 65535, but you can't use it to store negative numbers.  Card is the largest unsigned integer data type

For larger numbers, you can use the Int64, Integer64, Large Data Type.  The largest number this data type can store is 2^63-1 or 9223372036854775807.  That's about 9 quintillion (US short scale) or 19 digits long.  This seems like a pretty big number.  In fact, names used to describe the largest number held by an Int32 or Int64 carry monikers such as MAXINT, MAX_VALUE, math.huge, and (my favorite) Big McLargeHuge.  GB32, by the way, uses _maxInt and _maxLarge.

You might consider using single or double precision floating point data types.  A double uses 64 bits to store values upwards of 10^300, which makes Int64 with 10^18 seem puny.  However, while single and double can store very large numbers, they can't store very precise numbers.  They only keep track of the 8 or 16 (approximately) most significant digits.  They can store numbers in the bazillions (imaginary large number), but they don't store the exact number down to the 10s and 1s decimal places, but instead store about so many bazillions.  If you store incredibly large number and incredibly large number plus one into double precision variables, you'll find that both are now the exact same rough approximation of incredibly large number.  This is useful in many situations, but it's no help at all in calculating prime numbers.  We're left with Int64 as our best option.

I find myself offended that my spell checker continues for flag quintillion as misspelled, even though it's a perfectly cromulent word, while accepting bazillion, an imaginary made up number, as correct.

Remember back at the start of the article when I mentioned you could only use GB32 to calculate very small primes?  You think I'm wrong, don't you?  After all, I just showed you that GB32 can handle integer numbers in the quintillion (19 digit) range.  Surely, we can calculate a very large prime, right?

Wrong.  The largest known prime is 257885161-1.  That exponent is 57 million.  This number, written out in standard decimal form, is over 17 million digits long.  If you started typing that out, hitting an average of one key per second, it would take over six months to finish.  That's what the prime number people consider a large prime.  When they speak of small primes, they mean prime numbers with less than 100 digits.  Get that?  A googol, that's 10^100 or a 1 with 100 zeroes after it, is a small number to these people.  When they say something like "here's a program for calculating primes, but it's inefficient and only good for very small numbers," they mean any number easily stored in any default variable type in any programming language you've ever heard of.

Yes, there are ways to work with integers larger than 2^63-1 in GB32, but they are beyond the scope of this article.  (Snicker.)

So, how do we work with "very small" primes in GB32?  First, make sure you're using the Int64 or Large data type for any variable that might hold a prime candidate or prime factor.

Dim n, p, i, q27b as Large

Now, let's say we want to find out if a number is prime or not.  The first thing we do is thin the herd a bit.  It just so happens that all prime numbers have a final digit, the 1s place, of 1, 3, 7, or 9.  That's not to say that all numbers which end with 1-3-7-9 are prime.  It's just that if they don't, we definitely know that they're not prime.  You see, if they end in any even number like 2-4-6-8, we know they're evenly divisible by 2, so they can't be prime.  If they end in 0 or 5, we know they're evenly divisible by 5, so they can't be prime.

Function IsPrime(p) As Boolean ' determines if candidate 'p' is a prime number
  Local t$
  t$=Right$(Str$(p))
  If t$="1" Or t$="3" Or t$="7" Or t$="9" Then
    Rem Do more detailed analysis.
  Else ' definitely not a prime
    Return False
  Endif
EndFunction

I just threw that together, so there may be some errors, but I think you get the general idea.  Now, as for more detailed analysis, the only real way to tell if a number is prime is to try dividing it by all smaller primes (up to the square root of that number) and seeing if one of the divisions comes out even.  You only have to go up to the square root of the number because, worst case, at least one of the factors has to be at most as large as the square root and is probably going to be a lot smaller.  In fact, for "very small primes" like we're working with, some programs just divide the prime candidate by a list of the first 100 or so primes (hard-coded into the program or loaded from disk) and figure that if nothing comes out even, there's a 99% or better chance that the candidate is prime and that's close enough.

A good generic program for the "Do more detailed analysis" would look something like this:

For n = 3 to Sqr(p) Step 2
  If p mod n = 0 Then ' evenly divisible!
    Return False
  Endif
Next n
Return True

(Note:  I'm not sure the mod operator works with Large variables, as there's mention in the help file that parameters that aren't integers are converted to a 32 bit value first.  Large variables are integers, but they use 64 bits and not 32, so would they be converted?  Or does the conversion only happen to floating point values?  Must do more experimenting.  You can re-write the routine to not use the mod operator, but this way is neater.  It may not always work, but it's neater.)

This method involves dividing the prime candidate by all odd integers from 3 to the square root of the candidate, so it takes a little longer than just dividing by previously known primes, but you don't have to calculate or store any previously known primes, so it kind of evens out.  You could, of course, maintain a list of the first 100 or so primes, check all of them first, then continue with larger odd numbers.  We don't need to check even numbers because those are divisible by 2 and we've already eliminated them.

All the above is what I will call the brute force method.  I'm sure the prime number people have their own name for it.

Now we will talk about the sieve method.  There are several variations, but the basic principle is that you start with a list from 2 to the largest number you want to test.  So if you wanted to find all the prime numbers up to 100, your list would be 2, 3, 4, ... 99, 100.  The first number is prime, so print that out or move it to your prime list or whatever.  Then go through the rest of the list marking off all multiples of 2.  This will mark off 4, 6, 8, and in fact all the even numbers.  You then move to the next number on the list which hasn't been marked off, which is prime and in this case 3.  Print that out, then mark off all the multiples of 3 (which will include some of the numbers marked off by 2, but that's okay).  The next number not marked off is 5, so that's prime.  Continue until you get up to the square root of your largest number.  Any number not yet marked off the list is prime.

Coding an example of this for GB32 is left as an exercise for the reader.  (Snicker.)

The problem with implementing this method in GB32 is that you need a large array to keep track of which numbers have been crossed off the list.  At the very least, you need a boolean (true/false) array of size largest number you want to test.  We're hoping to test numbers as large as _maxLarge or 2^63-1 or 9 qunitillion.  Unfortunately, the largest boolean array I can dimension in GB32 is a bit over 2^30 or 1 billion.  So you can only use this method to calculate very small primes up to that size.  If you cheat and hard code in 2 as the first prime, your list can consist of only odd numbers, so you can raise that to 2 billion, but that's still a long way from quintillions.

The sieve process works fine if you want to know if a particular number is prime, or if you want to know all the primes smaller than a target number, but what if you want to know the first 100 primes?  Well, it turns out that the nth prime number is equal to or less than n log n.  In GB32 syntax, that would be n * log2(n).  If you use that value as your highest number in the sieve, it will generate at least n primes.  In our "very small numbers" range, it overshoots it by about 10%, but I'm told that for suitably large numbers it's quite accurate.  Also, it's supposed to be natural log and not log base 2 (log vs log2 in GB32 syntax), but that seems to generate a number about 20% too small.  Perhaps I'm using it wrong.

There's no sample code to download just yet.  I may add some in the future or you can email me your code.

04 Calculating Square Roots

posted Jul 18, 2015, 3:15 PM by Troy Cheek   [ updated Jul 18, 2015, 3:25 PM ]

Back in college, I took a Computer Sciences course called something like Numerical Methods.  The long and the short of it was that this class taught you how to use a computer program to guess at answers to questions you weren't smart enough to answer on your own.  Since you have to thoroughly understand how to solve a problem in order to program a computer to solve it for you, this knocked the difficulty down a notch or three.  You only had to understand how to solve the problem in the most general of terms, then let the computer make multiple guesses, fine tuning the answer until it was "close enough."  I grew to love "close enough."

y = 10x^3 - 111x^2 + 14x - 72  Given that equation, let's say you wanted to find some value for x such that y=42.  Once upon a time, I could do that calculation.  Heck, at one time, I could probably do it in my head.  It's a simple matter of algebra.  Or maybe calculus.  Differential equations?  Sorry.  Long time, no math.

What Numerical Methods taught us was to set up a program that tries a guess for the value of x and sees what the resultant value of y comes out.  Using that result, we refine the guess for x and try again.  Assuming the results are what we call "convergent" (meaning they're getting closer to the answer instead of farther away or "divergent") we will eventually get an answer which, if not exact, is close enough for jazz.  Either the solution we get is arbitrarily close to y or the last couple guesses for x were close enough to each other that there really isn't much point continuing.

The solution for the above equation is left as an exercise for the reader, mainly because I have no idea how to do it.  I'm going to focus on calculating square roots.  A square root is a number which, when multiplied by itself, equals a target number you're aiming for.

Now, GFA BASIC 32 has a perfectly good function for calculating square roots.  It's called Sqr(), and has an identical sister called Sqrt().  This is different from some languages where Sqr() actually gives you the square of a number instead of the square root.  In GB32, that function is called Square().  The main point of this article is that we're going to ignore all these built-in functions and program one for ourselves.

Now, there are a couple of "approved" ways to calculate a square root.  These involve fancy formulas or methods that nobody remembers and you have to look up every time you want to use them.  If you're going to do that, you might as well look up the square root itself or at least look up the syntax for the Sqrt() command in your language of choice.  Instead, let's focus on a method that uses our basic understanding of what a square root is, which is a number that when multiplied by itself equals our target number.

Two common methods for doing this are called "bracketing" and "successive approximation."  Bracketing is when you know the answer is in some range, say higher than one number but definitely lower than another, and you keep refining the low and high values, bracketing them in, until you get the right answer or your lower and upper brackets are so close as to be effectively the same number, which is your answer.

If you're looking for the square root of 25, well that's easy.  It's easy to remember that 5 time 5 equals 25.  And 6 times 6 is 36.  The square root of 30 is tougher, but since we know the square roots of 25 and 36, it's easy to see that the square root of 30 is somewhere between 5 and 6.  To get our initial low and high bracket numbers for square roots, we can do something like this:

Dim lo, hi, med, tar, tmp As Double
Dim i%
tar = 30
For i% = 0 To tar + 1
  If i% * i% < tar Then lo = i%
  If i% * i% > tar Then hi = i% : Exit For
Next i%
Print "Calculating the square root of "; tar; " somewhere between "; lo; " ("; lo * lo; ") and "; hi; " ("; hi * hi; ")"

In this example, we dimension a lot of variables as floating point double precision.  I normally work solely with integers when I can, since GB32 works faster with integers, but square roots are often fractional by nature.  In this case, we start at 0 and work our way up to just larger than the target value, checking each number to see if the square of the number is less than or larger than our target.  We set the lo and hi ends of our brackets appropriately, and exit out when we're done.  Now, if you know anything about square roots, you might think that going larger or even anywhere near as large as the target value is a bit extreme, since the square root is always much smaller than the square.  However, if you start looking for the square roots of numbers in the range 0>x>1, also know as fractions or decimal numbers, you'll find that the square roots are actually larger than the squares.  Sqrt(0.25) -> 0.5, for example.  Now, to do the actual bracketing.

For i% = 1 To 40
  med = (lo + hi) / 2
  tmp = med * med
  Print "Step "; i%, lo, med, hi, tmp
  If tmp > tar Then
    hi = med
  Else
    lo = med
  EndIf
  If lo NEAR hi Then Exit For
  If tmp NEAR tar Then Exit For
  Delay .25
  DoEvents
Next i%

I've limited this to 40 iterations, but you'll probably find your answer quicker than that.  I picked 40 because it pretty much fills the window I was using for output, and if you haven't found an answer in the first 40 or 50 iterations, you're probably doing something wrong.

Knowing that lo is too low and that hi is too high, we pick what we hope is a better guess by taking the average of the two values, which we'll call med.  Our first run through, we know that 5 is too low and 6 is too high, so we'll guess 5.5, which is actually pretty close at 30.25.  It's still a little high, so we set the high end of our bracket to this value and try again.  Looking between 5 and 5.5, we guess 5.25, which squares to 27.56, which is a little low, so we look between 5.25 and 5.5, and continue.

Notice the use of the NEAR operation.  In GB32, it's used to compare floating point variables.  Because GB32 uses a temporary 64 bit floating point number for internal calculations, which is many more bits than those used to store single or double precision variables, it's sometimes hard to get floating point math to generate exact matches.  NEAR checks floating point variables or calculations "only" out to 10 or 12 significant digits.  This is generally "close enough."

This method is fairly easy to understand, but is also fairly inefficient.  It takes about 35 steps to calculate a NEAR value, and each step is not always closer to the answer than the previous one, especially in the first few steps.  In math terms, the method is convergent, but not quickly convergent.

Successive approximation is a technique where you guess at an answer, check it, and use how close it is to fine tune your next guess.  How do we turn our knowledge of square roots into a successive approximation?  Well, we know that a root times a root equals the square.  If we divide both sides of that equation by the root, it turns out that a root equals the square divided by the root.  If we were again looking for the square root of 30 and guessed 5, then x=30/5, x=6.  5 and 6 aren't the same, but we know the root we're trying to calculate is somewhere in between, so we can guess (5+6)/2=5.5 for our new approximation.  x=30/5.5, x=5.45, which refines to 5.47 for our next guess.  Very quickly, we converge on an answer.

For i% = 0 To tar + 1
  If i% * i% >= tar Then old_app = i% : Exit For
Next i%
Print "Calculating the square root of "; tar; " somewhere near "; old_app; " ("; old_app * old_app; ")"
For i% = 1 To 40
  new_app = (tar / old_app)
  new_app = (new_app + old_app) / 2
  tmp = new_app * new_app
  Print "Step "; i%, new_app, tmp
  If old_app NEAR new_app Then Exit For
  old_app = new_app
  Delay .25
  DoEvents
Next i%

This might be a little harder to understand than the bracketing method, but it's the same general principle.  We're using the results of our last guess to refine the next guess.  Or, as known in math circles, approximations.  In this case, we're dividing the square by an approximated root.  If our approximation was exact, the answer we'd get would be the exact root.  We assume it isn't, and that the real answer is somewhere between our approximation and our calculated root, so we average these two numbers and use the average as our next approximation.

This sequence converges rapidly and generally takes less than 10 steps.  Only 5 in this example.  Again, we use NEAR to compare our old approximation to our new one.  If they're NEAR enough, we know we've found our answer out to 10 or 12 significant digits, which is close enough for government work.

Useless Info:  This writer independently derived the bracket method shown above in a 7th grade science class when a problem called for a square root and I had left my calculator at home that day.  The science teacher, who was also my great aunt, was not impressed and demanded that I use the method taught in math class which vaguely resembles long division.  I protested that the long division method wasn't taught in math class and luckily the rest of the class backed me up.  The teacher left the room for a few minutes, probably checking this with the math teacher, and returned ranting about how they'd changed the math curriculum without telling her.  She spent the rest of the class ignoring the science assignment and teaching us how to "correctly" calculate square roots without a calculator.

This writer independently derived the division method shown above in a college level numerical methods class when the instructor decided that the bracket method didn't count as successive approximation.  The division method received a passing grade, but included a notation that I'd used Newton's method wrong.

Newton's method, which it turns out Newton neither invented nor probably ever used, is also known as the Babylonian method, and uses the same division and averaging of approximations, just rewritten slightly, but mathematically identical.  The difference being that I can quickly derive the division method from the definition of square roots, while I always have to look up the Newton method.

The reader is encouraged to download examples of all three methods and to try them out with other target values.  Suggested values include very large (12345678), very small (0.0005), your birth year (1967), the current year (2015), and important dates from history (1492, 1776, 2525).  The reader is also encouraged to un-comment the lines which set standard default starting values instead of the calculated ones to see how many extra iterations this requires.

03 Saving Screen Shots

posted Jul 8, 2015, 1:00 PM by Troy Cheek   [ updated Jul 8, 2015, 1:00 PM ]

The other day, I created what I thought was a pretty nifty image with a GB32 program.  I wanted to save that image.  I didn't know how.

Sure, you can (almost) always grab a screen shot by hitting the Print Screen key on your keyboard, assuming your keyboard has that key, but that key hasn't actually printed the screen in so long that I forgot what version of MS-DOS it last worked in.  I never did find a use for Sys Req.  Regardless, hitting Print Screen nowadays copies the screen to the clipboard.  You can then load up Paint or your graphics manipulation program of choice and select the Paste command or shortcut.  You can then edit and save the image as usual.  That's the official way to do it.

However, that doesn't help you if you want to save multiple screenshots or save screenshots under program control.  Or if, as in my case, you want to save a screenshot 25 times a second while a program is running so you can later stitch the images together into a video.  For that, you need something special.

SavePicture Win_1.Image, "filename.bmp" will save an image of window # 1 in uncompressed bitmap format.  You can do the same for any other window or form.  These files are pretty large, but hard disk drives are cheap and you probably won't run out of room unless you do like I did and try to save a few thousand of them to a RAM disk.  Most graphics programs still know how to load and save bitmap files.

If you want to save only part of the screen, it's a little more complicated.  Check this out:

Local h As Handle, pic As Picture
Get 50, 50, 150, 150, h
Set pic = CreatePicture(h, False)
SavePicture pic, "filename.bmp"

The first line defines a couple of variables as special types.  A handle is a special type of variable that points GB32 to a certain section of memory.  In reality, it's just a 32-bit integer.  A picture is similar, but GB32 recognizes that it's image data.

The Get command should be called Grab, because that's what it does.  In the above example, it grabs a section of screen with the upper left corner at coordinates 50,50 and lower right corner at 150,150 saving the results to the handle h.  You can also use Get to save the image to a string variable, but that's for another article.

Set pic establishes that our picture variable pic is now associated with a picture created from the data pointed to by the handle.  In other words, it makes pic a certain type of picture.

SavePicture saves that picture in bitmap format as previously discussed.  The whole process is a little more convoluted than necessary because Get doesn't use the same picture format as SavePicture, but it gets the job done.

What if you want to save a bunch of images as the program is running?  I've got you covered!

Rem Save Screen
Mode StrSpace 0 : Mode Date "/"
OpenW # 1
Win_1.AutoRedraw = True
fn% = 0 : ntimer% = 0
Do
  Rem Stuff that outputs graphics to window # 1, like these random lines
  Line Rand(_X), Rand(_Y), Rand(_X), Rand(_Y), Rand(_C)
  SaveScreen(25)
  DoEvents
Loop Until Win_1 Is Nothing
CloseW # 1

Proc SaveScreen(frames%)
  Global fn%, ntimer%  ' set these to 0 before calling first time
  Local t$
If oTimer < ntimer% Then Return
  Inc fn%
  t$ = Str$(fn%)
  t$ = String$(4 - Len(t$), "0") + t$
  t$ = "z:\temp" + t$ + ".bmp"
  SavePicture Win_1.Image, t$
  ntimer% = oTimer + 1000 / frames% - 1
EndProc

This procedure should be called fairly regularly, so put it in your main program loop, or at least the loop that's creating the graphics you want to save.  The first thing it does is check to see if a certain amount of time has passed and return back to the main loop if that time hasn't.  The amount of time depends on how many frames per second you're aiming for.  If you want 25 frames per second, this procedure will run every 40 ms.  It will take around 10 ms.  At the end of the procedure, it sets a new timer goal.  oTimer is one of many timers in GB32.  This one counts in milliseconds, of which there are 1000 in every second.  1000 divided by frames per second equals the number of milliseconds before the next event, so we set that as the next target.

Note that we set this timer at the end of the procedure.  That way the main loop runs for 40 ms, we take 10 ms or however long we need to save the picture, then the main loop runs for another 40 ms.  This slows down execution of the main loop a little, but it keeps the timing the same as if the save procedure isn't there.  If we set the timer at the start of the procedure, it would run every 40 ms regardless of how much time the procedure took for itself, which would leave less time for the main loop, which might lead to unexpected results.

The t$ and the string manipulation just let us build a valid file name, in this case the path "z:\" plus file stub "temp" plus a 4-digit file number plus the extension ".bmp" to create a series of file names like "z:\temp0001.bmp", "z:\temp0002.bmp", "z:\temp0003.bmp", and so on.  Drive Z: is my RAM disk, so you'll need to change that before you run this program.

We use global variables for the file number and timer so that the procedure can remember their values between calls.  The official way to do this is to keep track of the values in the main loop and pass them to the procedure through the parameters like we did frames per second.  This clutters up the main loop, though

There are a few important things about the main program that need to be pointed out.  StrSpace affects the conversion of numbers to strings.  GB32 defaults to putting a space before and after the number.  I prefer no spaces, so I set this to 0.  This allows the file name we generate to not have any extra spaces in it.

The second important thing is setting Win_1.AutoRedraw = True.  You may think that's not really necessary if you're not planning on minimizing the window or whatever, but it's actually vital to the whole SavePicture command because the Win_1.Image that we're saving is actually the backup that AutoRedraw uses to restore the window.

Uncompressed bitmaps are very large, and not every graphics program can use them, so you may want to save them in a different format.  Unfortunately, SavePicture only works with bitmaps.  There are ways to convert the bitmap files after you save them, but that's the subject of another article.

02 Counting CPU Cores

posted Jul 7, 2015, 4:06 PM by Troy Cheek   [ updated Jul 7, 2015, 5:06 PM ]

There may come a time when you need to find out how many CPUs or cores or hyper-threads the computer your program is running on can use.  In this day and age, even cheap home systems may have more than one CPU, each CPU may have more than one core, or each CPU may be divided into two or more hyper-threads.  Or some combination.  According to the cute little sidebar gadget over in the corner of my screen, my computer has 8 CPUs.  As I know I only have one and only one (1) physical CPU, I figure I have 8 cores, or maybe 4 cores each capable of hyper-threading.  Or I'm confused and mixing my terms again.  For the rest of this article, I'm just going to refer to these as cores.

The point is that I recently discovered that GB32 (easier to type than GFA BASIC 32) can create multiple concurrent threads.  In this usage, a thread is a procedure or subroutine of a GB32 program that runs separately from and parallel to the main program.  I wrote a program where the main thread created pretty pictures and saved screen shots 25 times a second in uncompressed bitmap format (I'll show you how to do that in my next article).  This was so I could create a video later.  Unfortunately, uncompressed bitmap files are quite large.  I'd have to stop every so often when memory or the disk drive filled up and compress or convert the files.  This took time and really slowed down the creation of those pretty pictures.  I spawned a second thread which converted the BMP files into PNG (Portable Network Graphics) files at the same time the main thread was creating the BMP files (I'll show you how to do that in a future article).  Because the two tasks were running in different threads, the execution of which Windows divided among the 8 cores in my computer, the task completed in roughly half the time.  Even though I have 8 cores, I only created 2 threads because that was the extent that the task could be parallelized.  But what if you wanted to create more threads?

In most cases, especially if your computing task takes a lot of horsepower, you don't want to create more threads than you have cores.  Windows will try to distribute the load equally across cores.  While a single core can handle more than one task at a time (even a single core computer can run a multitasking operating system like Windows), if each task needs a lot of CPU cycles, Windows might spend more time shuffling the tasks around among the cores than actually letting the cores do any processing.  So, if you're dividing your high-power task into threads, you probably want to make sure that you don't create more threads than cores.  (If your task doesn't take a lot of horsepower, you don't have to worry about how many threads you're creating, but if it doesn't take a lot of horsepower, why are you dividing up the task in the first place?)

I know I have 8 cores in this computer, so it's easy for me to program for that.  You might know that your computer has 4 cores and think that you can program for that.  We're both wrong.  The programs we write might be run on another computer some day in the future.  We need a way to determine the number of cores inside the program we're writing.  Luckily, I know how to do that.

I freely admit that the following code is ripped from a sample program included with my GB32 distribution.  It's called HardwareInfo.G32 in the folder System.  Internally, it's called Systeminfo and was created by Georg Veichtlbauer, a programmer for GFA back in the day.  It shows all sorts of information about your computer, but unfortunately most of it is useless because the values it's testing for are outdated.  It think it was written back around 1999, so just imagine how much computers have changed since then.  About the only thing that still works is the Windows version information and the number of processors.  This is the code that counts processors:

' Copied from Systeminfo - (c) Georg Veichtlbauer
Local anzeige$, n&, Proz%

Declare Sub GetSystemInfo Lib "kernel32" (lpSystemInfo As SYSTEM_INFO)
Type SYSTEM_INFO
  wProcessorArchitecture As Card
  wReserved As Card
  dwPageSize As Long
  lpMinimumApplicationAdress As Long
  lpMaximumApplicationAdress As Long
  dwActiveProcessorMask As Long
  dwNumberOfProcessors As Long
  dwProcessorType As Long
  dwAllocationGranularity As Long
  wProcessorLevel As Card
  wProcessorRevision As Card
End Type
Dim sInfo As SYSTEM_INFO
~GetSystemInfo(sInfo)
Proz% = sInfo.dwNumberOfProcessors
anzeige$ = "Anzahl der Prozessoren: " + Str$(Proz%) + Chr$(13)
Message anzeige$, "Prozessor Info", MB_ICONINFORMATION | MB_TASKMODAL, n&

It's a mouthful, and not just because some of it is in German.  In spite of the best efforts of a grandfather and two college professors, my German is terrible.  But I think I have the general idea.

Local just defines some variables.  Anzeige means display, so this string is just the information we want to display later.  Proz is short for processors, so this variable will contain the number of processors once we determine that.  It's a Long aka Int32 aka can count numbers higher than 2 billion.  Imagine a computer with 2 billion cores.  I want one of those!

Declare Sub GetSystemInfo Lib "kernel32" means that we're going to load kernel32.dll which is a runtime load of a dynamically linked library.  The kernel32.dll is part of windows, and basically this command creates a way we can access functions/procedures/subroutines in this program and use them as if they were built-in GB32 commands.  In this case, we're going to access GetSystemInfo, which returns a complicated data structure defined by...

Type creates a data structure, in this case defined by many different variables of different types.  Most of the information it returns is meaningless for us right now, but dwNumberOfProcessors sound like something we can use.

Dim as well all know by now dimensions or declares a variable type.  We make sInfo the type of variable we just Typed.

We call GetSystemInfo which returns all that data in the variable sInfo.  We can access the information inside sInfo by adding a period and the name of the sub-variable within, in this case assigning a value to the variable Proz.

The other two lines just make the data prettier and display it in a message box.  We could have just as easily printed it to the screen in a window or simply used it internally.  The important thing is that, thanks to Georg, we have the information now.

Use it responsibly.

01 Simple Maze Generator

posted Jun 28, 2015, 6:58 AM by Troy Cheek   [ updated Jun 30, 2015, 7:24 AM ]

After the ultra-simple "Hello, World!" program, another program programmers like to program early on to learn a language is a maze generator.  There are a lot of ways to generate a maze that is both "complete" and "perfect."  Complete in this sense means that the entire area of the maze is filled in.  No voids or missing areas.  Perfect means that there is always one and only one path from any one place in the maze to any other.  No loops or walled off areas.  I personally like a few loops, but that's just me.

One way to do this is employ a DFS or depth first search.  Start somewhere and pick a random neighbor that hasn't been visited yet.  Move there and pick another random neighbor.  If you find yourself in a dead end with no unvisited neighbors, backtrack until you find an open area and try again.  When you've backtracked all the way back to your starting point, you're done.  I suppose it's called depth first search because you go as deep as you can into the maze before you backtrack and try other options.

The hard part of the DFS algorithm is the backtracking.  In order to implement that, you have to use recursion, a stack, a list of visited cells, or leave breadcrumbs in the maze itself.  I prefer the last method because it takes the least memory, is probably easiest to implement, and it was the first method I was exposed to way back in the ancient 1980's.  For this article, I wondered if there was another way.  It turns out, there is.  I found I could use simple iteration.  I had an old C college instructor I would irritate by pointing out that I could implement simple iteration for problems that he insisted required the use of recursion.  I like iteration.

Repeat
  done% = True
  For y% = 1 To my% - 1 Step 2 : For x% = 1 To mx% - 1 Step 2
      If maze(x%, y%) > 0 Then
        d% = Rand(4)
        For i% = 1 To 4
          Inc d% : If d% > 3 Then d = 0
          nx% = x% + dx%(d%) * 2 : ny% = y% + dy%(d%) * 2
          If nx% > 0 And nx% < mx% And ny% > 0 And ny% < my% Then
            If maze%(nx%, ny%) = 0 Then
              maze%((x% + nx%) / 2, (y% + ny%) / 2) = 255
              maze%(nx%, ny%) = 255
              x% = nx% - 2 : y% = ny%
              done% = False
              Exit For
            EndIf
          EndIf
        Next i%
      EndIf
  Next x% : Next y%
Until done%

This is the heart of the code.  By the time your program has reached this point, it's already dimensioned an array for the maze% of size mx% by my%.  I use the value 0 for the solid rock out of which the maze will be carved and 255 for the open paths.  It's also picked a random starting point and carved out that first cell.  What this program does is iterates (cycles through all possible values) through the maze and finds a cell that's been carved out.  Like the depth first search described above, it then picks an unvisited neighbor and carves a path to it.  When it carves itself into a corner, however, it doesn't backtrack.  Instead, it goes back to iterating through the maze until it finds another "jumping off" point and starts all over.  When the program can iterate through the entire maze without finding a jumping off point, it knows that it's done.  Here's a breakdown:

The routine is wrapped in a REPEAT UNTIL loop.  This simply means that the routine will repeat until a certain condition is met, in this case that the variable done% is found to be set to true or at least a non-zero value.  In fact, we immediately set done% to true.  Why doesn't the routine exit immediately?  Well, the value of done% isn't checked until the end of the loop, so the routine will execute at least once.  Once in the routine, if certain conditions are met done% is given the value of false or zero.  The loop continues!

Next we have a FOR NEXT loop.  Actually, we have two of them, one nested inside the other.  This is the part that does the iteration.  x% and y% values cycle through so that the entire maze% is covered.  In this case, x% and y% values go from 1 to 1 less than the size of the maze in steps of 2.  So, if the size of the maze% is 10, x% and y% values will both go 1,3,5,7,9.  The values at 0 and the max size of the maze are never visited because we need solid walls around the maze.  For each x% and y%, we check to see if there's an opening in maze%(x%,y%), meaning any value higher than the 0 we decided is solid rock.  If not, we just iterated to the next x% and y%.

If we find an opening, we pick a random direction d%.  We have another FOR NEXT loop where i% goes from 1 to 4.  This is so we can try all 4 directions.  Once inside this loop, d% is incremented (we add 1) and if it goes higher than 3, wraps back around to 0.  This lets us check all 4 possible d% values but start at a random direction so the maze doesn't turn out the same every time.

For each direction, we generate new x% and y% values called nx% and ny% based on delta values held in the arrays dx% and dy%.  For example, dx%(1)=-1 and dy%(1)=0 would mean that for direction d%=1, we'd move one space up and no spaces over, or North.  We multiply these delta values by 2 because we want to leave rock walls between our maze paths.  Next, we check to make sure that nx% and ny% are still within the confines of our maze.  It would be no good to generate a maze if we carved paths outside of it.

If the new area we're looking at is solid rock, or maze%(nx%,ny%)=0, it's time to carve a path to it.  We set the new location to 255 or carved path.  If we add the old location coordinates and the new location coordinates together and divide by two, that gives us the cell in between, which we also set equal to 255.  We've just carved a new pathway.

Now, in order to keep moving down this path, we need to update our x% and y% coordinates to our new nx% and ny%.  That way, next time around in the iteration, the routine will look at the end of our new pathway and not somewhere else.  Since x% will be incremented by 2 when we reach the end of this segment, we'll set x% to 2 less than nx% (x% = nx% - 2) so when we reach the Next x% statement, it will put x% back to the value we want.

Once that's done, we have to tell the routine that we're not done yet by setting done% to false.  Since we've found a new path and don't need to check other directions this time, we can exit out of the i% FOR NEXT loop with the command EXIT FOR.

Eventually, the routine will iterate through all possible x% and y% values.  If it found one or more new paths to carve, done% will be false and it will iterate them all again.  Eventually, the maze will be completely filled in.

The program attached at the bottom of this page includes a lot more than just this routine, including code to display the maze as its being generated.  This code will be discussed in a later article.  In the mean time, feel free to play around with it.  Might I suggest first changing the value of the SLEEP command to make the maze generate slower or more quickly.  Take it out altogether and see that, on my system at least, the maze generates so fast it seems to spring forth fully formed.  Not too bad for a clumsy, inefficient, iterative approach!

00 HELLO, WORLD!

posted Jun 28, 2015, 6:58 AM by Troy Cheek   [ updated Jun 29, 2015, 8:59 AM ]

In computer terms, a "Hello, World!" program is the equivalent of clocking in at work and turning the lights on.  All you've really proven is that you've shown up.  Whether you can do any actual work or not is still to be seen.  In computer land, this is an important first step.  It shows that both you and the computer are working properly.  If you can't get "Hello, World!" or some equivalent to show up on the screen of your computer (or some other display on some other device), then how can you do anything that's actually productive?  What are we paying you for, anyway?

I am not exaggerating in saying that a piece of hardware I once put together failed this test.  I forget the exact results, but it was something along the lines of "HELLA WARLD."  It turned out the keyboard was set up wrong.

In GFA BASIC 32, which is what this page is talking about, a "Hello, World" program is pretty darn simple.  I'm going to assume that you've tracked down and installed GFA BASIC 32 as explained on the main page.  Open it up (GfaWin32.exe) and type the following line:

print "Hello, World!"

That's all there is to it.  To test your program, click on the "Run" icon or hit F5.  GFA BASIC 32 should open up a window, display "Hello, World!" and return control to the editor.  You might also want to try to compile the program and try it outside of the editor.  Along the top line of the editor, pull down "Project" and select "Compile" or just hit CTRL-E.   You can then run the resulting EXE file by double clicking it.

Now, if you played with the window that opened up, you may have noticed something.  As soon as you minimized, maximized, or just resized the window, your beautiful "Hello, World!" disappeared.  If you tried running and compiling the program, you probably noticed that the window opened and closed so quickly that you couldn't tell if "Hello, World!" appeared or not.  What's the big deal?

Well, it turns out that while putting something on the screen is pretty easy, actually doing anything with it takes a little setup.  That's why my version of "Hello, World" for GFA BASIC 32 looks something like this:

Rem HELLO, WORLD!

Mode StrSpace 0 : Mode Date "/"
Auto

OpenW # 1
Win_1.AutoRedraw = True
Win_1.Caption = "GFA-BASIC 32 - HELLO, WORLD! - Troy H. Cheek"
Win_1.SetFont SYSTEM_FIXED_FONT
Win_1.PrintScroll = True
Win_1.Sizeable = False
Win_1.MaxButton = False
SizeW # 1, 1280, 720
SizeW # 1, 1280 + (1280 - _X), 720 + (720 - _Y)
Win_1.Center Screen.hWnd
ClearW # 1

Print "HELLO, WORLD!"

Do : Sleep : Until Win_1 Is Nothing
CloseW # 1

That's a lot of code just to say "hello."  That's because it's not "just" hello, but also makes sure the hello message sticks around.  I also use code like this as a basic starting point for any new project.  It's complicated, but don't worry.  I'll go through it with you line by line.

The REM at the top is a simple remark.  In BASIC, remarks are ignored.  I always start a program with a remark reminding whoever is looking at the code of what the program is called, what it does, who wrote it, etc.  Also the GFA BASIC 32 editor will show the first line of code in the status bar at the bottom, reminding you of what program you're working on.  By the way, I will sometimes write BASIC keywords in ALL CAPS, at least when I first use them.  That's a habit I got into a lot time ago working with a BASIC that only accepted ALL CAP keywords.

The MODE statements set some behaviors the way I want them.  By defaut, GFA BASIC 32 acts a bit like Visual Basic and certain C dialects in some respects.  This is for compatibility, so that code written for one language can be more easily converted to the other.  Which is fine and all, but some of the behaviors are contrary to what I expect after working with older versions of GFA BASIC and other languages.  STRSPACE sets the behavior when converting numbers into letters.  To a computer, the number 12345 is different than the text "12345" written on the screen.  The default is to pad the new text with spaces at the beginning and end, so it comes out something like "_12345_" where those underscores are actually blank space.  I don't like that, so I turn it off by setting this option to 0.  We don't do any numeric conversions in this program, but it turns up where you least expect it.  If we were printing a number to the screen instead of "Hello, World" we might have unexpected spaces.  DATE sets how dates are displayed.  As an American, I'm used to seeing dates in the form of MM/DD/YYYY.  In Germany, where GFA BASIC originates, they apparently like DD.MM.YYYY.  I don't, so I change it.

AUTO is a command that automatically declares variables for you.  I'm used to older BASICs where you didn't have to explicitly declare that variable A was an integer, variable B was a byte, variable C was a string, and so on.  I just have to remember to use the right type modifier for the variables, A% being an integer, B& being a byte, C$ being a string.  As long as I cast it right the first time I use it, GFA BASIC 32 will keep track of it for me and add it to the Auto line.  I like to check the Auto line after I add a new block of code.  If I suddenly see misspelling of a BASIC keyword among my list of variables, I can be pretty sure that I typed something wrong and that my program won't run.

OPENW, strangely enough, opens a window with the specified number.  I don't know if Windows (the operating system) can actually support this many windows (the thing on your screen), but GFA BASIC 32 lets you use numbers 0-511.  I'm tempted to write a program to try to open 512 windows just to see that happens.  (EDIT:  It bogs down your computer and it takes forever to close them all, but you can open at least 512 windows in Windows.)  This window is where all our text and graphic output will go unless we open another window and tell the program to output it there.

We set AUTOREDRAW for window 1 to true so that if we minimize or maximize or make other changes to the window, the program will know about it.  The default window behavior will take care of most of it, but sometimes the program will have to redraw the window.  That usually takes more work than I'm willing to do, so I take steps to avoid it.  More on that in a second.

CAPTION lets us define what will be displayed in the title bar at the top of the window we just opened.  We could also set that with TITLEW.  In fact, when it comes to windows and dialog boxes and forms, there are often multiple ways of doing things.  I like to set the caption to something descriptive in case I have multiple GFA BASIC 32 windows open and don't want to have to flip through them to find what I'm looking for.

https://sites.google.com/site/stessential/development/gfa-basic
I like to SETFONT to a fixed width because it reminds me of my early programming days.  For some reason, proportional fonts just don't look like "code" to me.

PRINTSCROLL sets the behavior when you print something at the bottom of the window.  Does it print at the bottom and make the rest of the test scroll up, or does it get printed somewhere below the bottom of the window and disappear forever?

SIZEABLE controls if you can grab an edge or corner of the window and use that handhold to change the size or shape of the window.  This is one of the cases where autoredraw can't help us, so I like to disable it so the program doesn't have to manually redraw the screen.

MAXBUTTON controls if the maximize button is active.  This counts as a change in the size and shape of the window, so I disable it.

SIZEW changes the size of the window, and I often like a size of 1280x720.  It's still HD (suck it, haters!) but is small enough on my 1920x1080 screen that I can see around it or move it aside if I need to see something else.  My video camera works best at 720p and I do all my video editing at that resolution, so it makes sense to use that for projects that I might be taking screenshots or video of.

Notice that we have two SIZEW commands.  The first attempts to set the window size to 1280x720.  This succeeds, but it turns out that those dimensions mean the window as a whole including the title bar at the top and borders all around.  That makes the area useable for text and graphics slightly smaller.  Exactly how much smaller depends on what gadgets and doo dads your particular version of Windows and your individual settings put there.  GFA BASIC 32 does have a way to determine how much space those gadgets and doo dads will take up on a window, but I always have to look it up.  It's actually easier for me to attempt to size the window, see how close I get, and do a little math to fix things.  _X and _Y are shut cuts that tell you how many pixels wide and high your usable window space is.  So, if we try to open a window 720 pixels tall but actually get one only 700 pixels tall, we know that on our next attempt we can open one 740 pixels tall to get the desired results.

CENTERW centers the window within the specified object.  In this case, we call the handler (h) for Windows itself (Wnd), so we basically tell it to center the window on the Windows screen.  We can still move it around if we want to or minimize it if it's in the way; we just can't resize or reshape it because we'd have to manually redraw the screen and we haven't covered that yet.

CLEARW clears the window.  This probably isn't necessary because we haven't put anything in the window yet, but with all the resizing and moving and option setting, it's possible some garbage got in there, so it's best to clean it before we use it.

PRINT.  We used it.  Finally.  "Hello, World!"

The DO LOOP UNTIL is there so that the window hangs around long enough for us to check it out.  Without it, the program would just end.  In this case, the program will SLEEP until the window becomes "nothing" or goes away, probably because the user clicked on that little red X in the upper right corner.

The program ends with CLOSEW.  This probably isn't strictly necessary because we just waited around until the only window we opened was closed by the use.  However, having this here reminds me that I need to clean up before exiting the program.  The days when you could just end a program with the END statement are over.  The programmer has to remember to close open windows, flush and close open files, release memory blocks and other resources that have been reserved, cancel sounds that are playing, reset custom color palettes, and generally behave like a well-meaning guest and put the house back the way he found it.

And that concludes discussion of the "Hello, World!" program.  That was a lot of lines of code for something so simple, and we didn't even use most of it, but it will act as a starting point for future projects.  I hope you enjoyed this article.  Please tune in next week for more about GFA BASIC 32.

1-6 of 6