[editor : Carl T. Helmers Jr.] [publisher : Virginia Londoner, Gordon R Williamson] [art : Ellen Bingham, Wai Chiu Li, Christine Dixon, Holly Carmen LaBossiere, Deborah Porter] [cover : Robert Tinney] #Magazine

#Abstract

Topology is the theme of this month's cover painting, "The Seven Bridges of Königsberg" by Robert Tinney. It is a fanciful representation of a classical, topological problem made famous by the Swiss mathematician Euler, and it has a more than passing resemblance to the works of the Swiss artist M C Escher. The celebrated problem is discussed in detail by Carl Helmers in this month's editorial, and the Painting is also loosely inspired by the theme article, "A First Look at Graph Theory Applications," by Ashbrook and Zinn. Sharp-eyed readers might spot a visual reference to another famous mathematical problem hidden in the cover.

The Seven Bridges of Königsberg

#Edito

Extract : «  Covers, like editorial themes, are sometimes drawn from interesting subjects intended as themes for an issue. But divergences can occur. This month, the nominal theme for the issue is the topic of graph theory. It takes only one article to suggest such a cover theme, and the article "A First Look at Graph Theory Applications" by Michael Ashbrook and Helmut Zinn provided the initial suggestion. But our actual cover is inspired by a historical problem in mathematics which led to the definition of a much broader field: topology.

This generalization occurred as a result of trying to find a nice neat visual image that fits the topic of graph theory. In order to concoct a cover idea on graph theory, the first step is to start searching around for some theme on a diagram of nodes and interconnecting segments which is not some hackneyed abstract pun. In order to construct a visual image for a cover, I needed to find some seminal problem with dramatic visual import. This problem must define and suggest the general field of endeavor. So, I proceeded to hunt around.

A good forest in which to hunt mathematical images is an excellent four-volume set of books entitled The World of Mathematics, by James R Newman, published by Simon and Schuster in 1956, and still available at a cost of $39.95. On the covers of the four volumes we find the description "a small library of the literature of mathematics, from A'h-mose the Scribe to Albert Einstein, presented with commentaries and notes." These books present a selection of original papers by mathematicians, with introductions and commentary by the editor. As serious or recreational reading for those interested in mathematical subjects, I highly recommend it. [...]  »

TABLE OF CONTENTS

If the use of graph theory raises a question, this article will supply an answer. The authors introduce the fundamental concepts of graph theory and two methods of directed-graph storage.

[author : Michael Ashbrook and Helmut Zinn] #Mathematics #Listing #BASIC

Extract : «  What do the following problems have in common?
• Finding the shortest route between two particular cities on a complicated road map.
• Finding the shortest route between any two cities on a road map.
• Selecting a set of roads that connects all the cities on your map and has less total mileage than any other such set.
• Calculating the maximum amount of liquid that can flow through a system of interconnected pipelines per unit of time.

These four real-life problems can be interpreted in terms of graph theory and can be solved by remarkably simple and efficient programs. The problems belong to a much larger category of operations- research problems; these were selected as examples because of their comparative simplicity. Algorithms for solving such problems along with the necessary background for understanding them will be examined.

While our terminology follows that of Narsingh Deo, our programs are quite different from his. If you become interested in solving more graph-theoretic problems on your own, you will find his book a stimulating introduction. (See Graph Theory with Applications to Engineering and Computer Science by Narsingh Deo, Prentice-Hall, Inc, 1974.) [...]  »

Steve Garcia shows how he uses his computer to monitor and control a Hydrostove - a wood stove that heats water piped through it.

[author : Steve Ciarcia] #Algorithm #Electronic #Energy

Extract : «  [...] The heating system shown in figure 1 is commonly called a hydro/air system. It consists of an oil hot-water boiler and hot-air heat distribution. The oil burner heats water, which in turn circulates through a hot-water heat exchanger. A fan blows over the heat exchanger coils and circulates the hot air through the ducts to each room. Such a system combines the even-temperature, residual-heating benefits of a hot-water circulator with the pleasant, humidified, filtered warmth of a hot-air system. A third zone of baseboard heat was added when the Circuit Cellar was built. [...]  »

Part 2 of this article shows how to construct the design that was presented in the January 1980 BYTE, using the Heathkit ET-3400 microprocessor trainer.

[author : John H Gibson] #Electronic

Extract : «  In part 1 is an examination of the basic principles and techniques for achieving proportional AC phase control with a microcomputer and a programmable timer. I would now like to present a completely workedout demonstration program designed to run on a Heathkit ET-3400 microprocessor trainer. This demonstration program will operate three lamp circuits, giving you keyboard control over the lamps that are to be faded on and off. In addition to the ET-3400 trainer, you will need an MC6840 programmable timer module, a 7405 hex inverter (open collector), a synchronizer (from figure 5 in part 1), and three AC phase controls [...]  »

Using linked lists to maintain sorted files is one way to deal with limited memory, large files, and additions and deletions to these files.

[author : Ted Carter] #Listing #BASIC #DataStructure #DataManagement #Book

Extract : «  In many computer applications where a large amount of information is to be stored, the need arises to sort, insert, and delete items efficiently using random-access tape or disk-based files. A common method of implementing a mailing list, for example, is to add new names to the end of the current file and to delete names by putting a blank field in place of the names to be deleted. This minimizes the number of time-consuming reads and writes to the file.

However, when this mailing list has to be printed in zip-code order, for example, the task becomes extremely slow as the number of names increases. This is because the number of file accesses increases exponentially with the number of items to be sorted. One possible solution is to actually sort the file so that it is always in order. This is impractical because it necessitates the same sort operation as before, plus a complete rewrite of the file.

With close examination of the problem, you might decide that the file should always be kept in order by inserting a new name in its proper place. This is a good idea, but requires that you must move, on the average, N/2 names (for a file of N names) to make room for the new names. Again, with large files, this may take an inordinately large amount of time.

In order to solve these problems successfully and efficiently, you need a data structure that will permit an insertion and deletion of components without having to worry about where new components fit or what happens to the empty space left by deletion. The tool needed to create such a structure is called a pointer. This is simply a number that points to the location of a desired piece of data. Using disk files, for example, a pointer to a piece of data is its actual record number on the disk file. This takes advantage of the random access capabilities of a disk file so as to directly locate and read the data using the pointer value.

Using pointers, a linked list, the simplest type of dynamic data structure, can be built. In order to build the linked list, every data record must be accompanied with a pointer to the next element in the linked list. Therefore, space must be reserved in the file for a pointer value within each data record. [...]  »

This general-purpose algorithm performs these conversions and assembler programs for the 8080 processor.

[author : Michael McQuade] #Listing #Assembly #Algorithm #Encoding

Extract : «  A problem which has confronted users of small computer systems over the years has been the incompatibility of the number representation required by output devices and that used for internal processing. Output devices used by the small systems need to receive binary-coded- decimal (BCD) or ASCII (American Standard Code for Information Interchange) data representations, while the microprocessor is most efficient when handling a straight binary number. Several solutions to the problem exist, and as would be expected, each has its own advantages and disadvantages.

Some users choose to initially store all numbers in their binary-coded-decimal representation and do all subsequent processing in this format. This has the advantage of easy and quick conversion of the numbers into the required output format. At worst, the binary-coded- decimal represented number must be converted to an ASCII format. This requires attaching a fixed 4-bit prefix to each binary-coded-decimal digit.

A disadvantage associated with this approach is that arithmetic operations take longer to perform, since the results must be decimally adjusted after each operation. Also, more memory is required to store the binary- coded-decimal form of the number than is required for its straight binary equivalent. A direct result of this increased memory requirement is the need to perform more memory-access operations to transfer the numbers into and out of the processor. Memory accesses are a very time-consuming operation.

For the users who choose a straight, binary-number representation for internal storage, the advantages of efficient memory utilization and straightforward arithmetic are gained. The question of how to convert the numbers to an acceptable output format for the display device still remains to be answered. This question basically reduces down to converting the binary numbers to binary-coded-decimal form. [...]  »

Most investors will agree that financial stability and success require an organized systematic means of assessing investments. The program written by John Lehman can output the typical information required for such a financial report.

[author : John H Lehman] #Listing #BASIC #Algorithm #Glossary #Finance

Extract : «  Financial analysis, as it will be used in this article, means the study and analysis of financial statements. Financial statements are the documents which are produced by an accounting system; they report the position of a firm (such as the balance sheets shown in table 1) and how well it has done over the last period (income statements). They are used both by small businesses and by major corporations. The latter are. required to make public statements in annual reports and in filings with the Securities and Exchange Commission; these statements serve as one of the primary sources of information to investors.

The program logic described in figure 1 is versatile enough to work on the financial statements of almost any company, although some statements may first need to be consolidated a bit. The basic tools used to analyze statements are ratios and percentages. These can be calculated for a firm, and then compared with both the firm's previous performance and with other firms in the same industry. In this way, a comprehensive study can evaluate the position of the firm and identify trends in performance. [...]  »

Robert Newcomb tells how to construct and program the low-cost plotting system described by Peter Lucas in the February 1979 BYTE. Robert uses a KIM-I and various electromechanical parts.

[author : Robert K Newcomb] #Electronic #Algorithm #Listing #Assembly #BASIC #Display

Extract : «  Following the suggestion of Peter Lucas in the February 1979 issue of BYTE ("Another Plotter to Toy With," page 66) I built a plotter using an Etch-A-Sketch and two stepper motors. After solving the interface problem, I connected it to an I/O (input/output) port on my KIM-1 which is equipped with a teletypewriter, 8 K bytes of extra memory, and Tiny BASIC. Photo 1 shows the result: stepper motors mounted on the Etch- A-Sketch, along with a circuit board. The KIM-1 controls the apparatus using 4 bits of an I/O port. The stepper motors can be driven by any other computer having 4 bits of transistor-transistor logic (TTL) level output available.

The Etch-A-Sketch proved to be able to draw bar graphs with excellent results, drawing an even, horizontal baseline, while accurately reproducing data from the computer's memory. I later tried geometric figures, including a parabola. Because each step is only 0.0085 inches (0.216 mm), the device gives good approximations of curves. The main limitation of my plotting system resides in the inability of Tiny BASIC to handle fractional numeric values. [...]  »

The method described by Scott Jones can be applied to a wide range of problems in business and industry as well as conflict simulations and games.

[author : Scott T Jones] #Method

Extract : «  In business, in industry, and especially in conflict simulation, problems are often confronted that involve terrain, the surface of the planet Earth. These problems can usually be expressed in terms of movement on a map. This article defines terrain as any feature on the map that affects movement. The term movement cost will be defined as the quantitative effect of the terrain on movement.

An example of a hiker traveling cross-country from one town to another town will be used. The hiker may travel one mile across level ground in 15 minutes, while requiring 30 minutes to travel one mile when the ground is sloping gradually upward. It can be said that the movement cost for the terrain called level ground is one, while the movement cost of the terrain called upward-sloping ground is two. Here the movement cost is in terms of time.

For another example, consider a construction company building a road. The cost to build one mile of roadway over solid ground might be $100,000, while the cost to build one mile of road over marshy ground might be $500,000. Thus, you can say that the movement cost is one for solid terrain and five for marshy terrain. In this case, the movement cost is expressed in terms of money.

In both examples, there is an existing problem of moving from one point to another across a terrain map while incurring the minimum movement cost. Now examine another variation of this problem. [...]  »

Building this interface solves the occasional problem of having one interface port and the need to use three or four peripherals.

[author : Stephen A Alpert] #Interface #Electronic #Book

Extract : «  Every now and then, a micro or minicomputer owner may be fortunate enough to have more than one terminal and probably a modem or two. Unfortunately, there never seem to be enough interfaces to the computer system to connect all these devices into the system at the same time. This article chronicles my local solution to the problem.

Through luck and a lot of hard work, my computer system consists of a Digital Equipment Corporation PDP-11/10 processor, a video monitor, a teleprinter, a modem and only one terminal interface. Conveniently, the video monitor, which serves as the main console, is driven directly off the processor. This still meant that there was a deficiency of one terminal interface.

After reviewing the schematic for the interface that I had, I started a design to essentially duplicate that board. A friend jokingly suggested that a design should be generated to drive several terminals at once. Taking that thought seriously, my course of action had been charted.

The creation of this quad terminal interface involves ideas applicable to almost any sort of processor that uses memory addressed IO. That is, the processor contains no special IO instructions, but instead addresses specific memory addresses to communicate with the status registers and buffers of the peripheral devices. This tradeoff means that the devices look like memory and the processor can therefore be equipped with additional instructions at the loss of memory space. [...]  »

Some programming languages are more appropriate to a particular application than others. This comparison will help you choose the right language from the many possibilities.

[author : Robert A Morris] #Languages #BASIC #Fortran #ALGOL #Pascal #APL #Book

Extract : «  The time is not far off when microprocessor users will begin the serious use of high level languages other than the BASIC supplied for many current machines. There are many projects hither and yon to implement contemporary languages in microcomputer form, and the emergence of 16 bit processors will probably accelerate this trend. Indeed, even now microcomputer users have a practical way to use high level languages: using the personal computer as an intelligent interactive editing terminal and sending source code over telephone lines to be compiled and executed by a large remote time- sharing computer. For many such tasks, the connection time (the charge levied by the big computer operators for merely listening to your terminal) is a substantial fraction of the total cost. But this lime is short compared to the data entry time, which will be entirely on the user's own system.

Unfortunately, most information about languages is gleaned from people who have a stake in a particular language due to a greater familiarity with it. Different languages are appropriate for different tasks. Multilingual ability is as useful in the computer world as it is in the human world. To this end I would like to describe the differences and similarities between major general purpose programming languages, and offer opinions about how these differences might affect your choice of a high level language.

A number of the conclusions I draw can be attributed to questions of style, and many whose personal programming styles are different might take issue or even umbrage at what I offer. Nevertheless, I claim the critical reviewer's prerogative to offer opinion, and hope only that it is clearly identified. One precaution to the novice and to the initiate: In comparing programming languages, I assume that the specific choices are equally well implemented. Unquestionably the worst version of language A may be far harder to use than the best version of language B, even if in principle the opposite is the case. [...]

I will discuss essentially three languages: BASIC, FORTRAN, and ALGOL (together with PL/I). I'll also take a cursory look at Pascal and give a brief description of APL together with the reasons for not including it in this survey. These languages are fairly standardized so that if one has learned them on one machine, there is very little relearning necessary for another. Indeed, aside from minor punctuation differences, one rarely encounters machine dependent features of these languages except for input and output (IO). Thus it is often practical to transport programs from one machine to another with very little rewriting except for the IO, but in some circumstances this can be substantial.

Many BYTE readers know BASIC already, but I will describe it so that a broader audience might be reached. In some of the following examples I have abused programming language punctuation in the interest of comprehensibility. [...]  »

The feature provided here will give your BASIC package the control where a particular piece of information will appear on a line when you are performing input and output routines.

[author : William D Roch] #Listing #BASIC #Programming

Extract : «  If your BASIC interpreter has a PRINT USING capability, you should have no trouble printing reports or other similar output. If not, then you are at an apparent impasse with the standard BASIC output that left-justifies everything at fixed positions on a line, an approach that has many limitations.

The routines in listing 1, lines 9000 to 9997, solve this problem and produce a formatted output. Also included are routines for reading an unformatted string and placing the fields in numerical or string arrays, and a routine for establishing arrays for a formatted input record. In addition, lines 100 to 927 are a test program that can be used to get the feel of how these routines work.

Why Format Records?

There are several advantages to working with formatted string records:
• The position of each field in a record is always constant.
• Only one variable name is needed to input, read or print. Counting fields when there is more than one record type involved is no problem — you need only check a record type code and break up the record with the proper format statement.
• Records may be created and changed with one string type editor rather than an individual program or modification for each set of records.
• Most business type applications use formatted records. [...]  »

Gasuse

String Comparator for Horizon

Some Example Plots

Introduction to Code Tightening

Mining the Skip Chain for Extra Bytes of Code

Audio Meter for Your TRS-80

Algebraic Identities Are Not Numerical Identities

#Book

Extract : «  Let's Talk LISP by Laurent Siklossy, Prentice-Hall, Englewood Cliffs NJ, 1976,237 pages, hardcover, $14.20 [...]

Godel, Escher, Bach: An Eternal Golden Braid, Douglas R Hofstadter, Basic Books, New York, 1979, 742 pages plus notes and references, hardcover, $18.95 [...]  »