My Python Joy: A World Without Tables and Calculators? (#05)

A linked list lets you store information in a data structure that grows over time. One advantage of a linked list is that you don’t have to know in advance how long your list will become. As you find more data you want to store in the list, you simply add it to the end of the list: you append the new piece of information.

Recently, I wanted to solve a problem. The problem was how to store the results of a computation. The computation was simple: ??2 + ?? + 41, when x is a positive whole number less than 101. In other words, I wanted to compute the result of this expression starting with ?? = 1 and ending with ?? = 100. With each new ??, I also wanted to automatically store the result as the latest data entry. As you can imagine, a linked list is perfect for this.

How to Do this in Python, For x = 1 and x = 2

To test how this works, I want to calculate the result for x = 1 and x = 2. The way to tell Python to create a linked list, to calculate ??2 + ?? + 41 for ?? = 1, to store the result in the linked list, to then calculate the result for ?? = 2, and to add that result to the linked list, is like this:

linked_list = []
x = 1
while x < 3:
  result = x**2 + x + 41
  linked_list.append(result)
  x += 1
print linked_list

Since I have seven lines of code here, I first save this as a script named "alinkedlist.py". When I execute this Python script, the Python compiler will read the code and perform the following, line by line:

• Line 1 - Create an empty linked list and assign it to the variable I've created named "linked_list"
• Line 2 - Assign the value of "1" to the variable I've created named "x"
• Line 3 - Begin a while loop that will run for as long as x is less than "3"
• Line 4 - Assign the string "??2 + ?? + 41" to the variable I've created named "result", and calculate the result of this formula for the current value of x
• Line 5 - Append that result to the end of the current linked list. Since I created an empty linked list on Line 1 and x = 1 is the first calculation, its result will be the first entry in the list
• Line 6 - Increment the current value of x by 1 and then repeat the loop by returning to Line 4 (but only while x is less than "3"). Since x was previously set equal to 1, this while loop will run for x = 1, then it will run for x = 2, and then it will stop. This is because I told the compiler on Line 3 to loop only while x is less than 3
• Line 7 - Print the linked list

In my example above, I started with an empty linked list, but by running this code, the list now contains two results:

1. the result for x = 1, which is 43
2. the result for x = 2, which is 47

Thus, Python will print this on the screen:

[43, 47]

How to Do this in Python, For x = 1 to x = 100

Now that I know this works, I can create a script with the code for 0 < x < 101, which is another way of saying from x = 1 to x = 100:

linked_list = []
x = 1
while x < 101:
  result = x**2 + x + 41
  linked_list.append(result)
  x += 1
print linked_list

Now, in less time than the blink of an eye takes, Python calculates the following:

[43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601, 1681, 1763, 1847, 1933, 2021, 2111, 2203, 2297, 2393, 2491, 2591, 2693, 2797, 2903, 3011, 3121, 3233, 3347, 3463, 3581, 3701, 3823, 3947, 4073, 4201, 4331, 4463, 4597, 4733, 4871, 5011, 5153, 5297, 5443, 5591, 5741, 5893, 6047, 6203, 6361, 6521, 6683, 6847, 7013, 7181, 7351, 7523, 7697, 7873, 8051, 8231, 8413, 8597, 8783, 8971, 9161, 9353, 9547, 9743, 9941, 10141]

The first time I did this, my jaw hit the floor and my neighbors heard me scream in delight. You see, I had spent a week thinking about the problem in a way that would help me figure out what I needed to do. At the start of that week, I didn't know if I needed to use a linked list or an array; I didn't know much what a while loop or a for loop was, and less which one would be better for my situation; and I didn't yet know how to map out the problem into pseudocode so that I could then figure out the best way to implement the actual code using my particular programming language, which is Python. So by the time this all came together, I shrieked with joy when it worked. But none of this is as interesting as why I wanted to use Python to calculate this in the first place—or what I ultimately wanted to do with this linked list. Before I tell you, we need to travel back in time by 200 years.

The First Computers were Calculators

In his book The Computer: from Pascal to von Neumann, Herman H. Goldstine starts by giving some historical background on how computers came to be. As he tells it, one of the first attempts at creating a computer was in the early 1800s by a man named Charles Babbage. In Babbage's day, there was a lot of emphasis on tables:

"Since the time of Leibniz and Newton mathematicians and, more generally, what were in those times known as natural philosophers were much concerned about the production of tables either by means of mathematical calculations as in the case of tables of multiplication, of logarithms, of sines and cosines, etc.; or by means of physical measurements or observations, as in the case of tables of precipitation in a given location, or of air density as a function of altitude at a particular time, of the gravity constant at different locations on the earth, etc. These tables are the means by which scientists very early in time learned how to record their experiences so that others could benefit." (Goldstine, p. 17)

Unfortunately, as Goldstine went on to say in the paragraphs that followed, humans are good at using tables but not nearly as good at producing long tables that are error-free. We are pretty good at manipulating quantities once they're recorded in a table but pretty slow at calculating new values to add to those tables, especially if the calculation is complex. Today we have calculators and computers to help us out, but in Babbage's day, they didn't. So the earliest attempts to build computers were about eliminating the error, hassle, and time involved in manually calculating very complicated calculations.

A simle polynomial like ??2 + ?? + 41 was a test case used by Babbage in a machine he designed and tried to build called the Difference Engine. His version, and what Goldstine describes on page 18 of his book, is in the form N2 + N + 41, and in both cases, they started with N = 0, but in my example I chose to use the expression ??2 + ?? + 41 and start with x = 1.

But one problem with machines like Babbage's (and others' at the time) was that they did the job, but not so much faster than humans that it was worth the time and cost to manufacture them. These machines could calculate a lot of numbers for use in creating tables, but the time-savings weren't impressive enough. Eventually, other machines that were much, much faster than Babbage's and were more economical did come along, of course, and those were the models that became popular as calculators in a variety of fields and helped create all sorts of very long and very useful tables.

But back then, they didn't have linked lists.

What if We Didn't Need Tables...or Calculators?

Computers were invented in part out of the need to calculate values for storage in large tables. As a brief thought experiment, what if 200 years ago we had had computers, data structures such as linked lists, and programming languages capable of surfacing previously recorded measurements on an as-needed basis rather than us having to use the human equivalent of a LOOKUP function to visually look up data in tables? Would we have continued to create tables? Now try to imagine 200 years from now, roughly the year 2220: with 250+ years of modern computing behind us, will we continue to have and use calculators? Of course not.

Towards a World without Computational Redundancy

Consider a computer that computes the definitions of words and presents those definitions to the user. This fictitious computer is programmed with the rules and logic necessary to accept an arbitrary (real) word as input, compute the definition of that word, and display the definition as output. Notice that I first said compute the definition: in this example, the computer would be performing a computation in real time and only then showing the resulting definition to the user, on a device. This of course would be wasteful computation if the definition of a given word doesn't change. The better approach would be to agree on the definition of the word and then store that definition for future retrieval, and indeed that is what a dictionary does.

Now imagine a handheld computer that computes the result of mathematical operations and presents the result to the user. This computer accepts what you type, such as an arbitrary mathematical expression, as input; computes the result based on the numbers and operators you use and the logic it's programmed to follow; and then displays the resulting value as an output. This is of course what a calculator is used for. But every time we use a calculator, it's wasting work. Why? Because there's a higher than 99.99% probability that someone else, somewhere on the planet, at some point in time since calculators were invented, already typed that exact same expression into a calculator. For a number of expressions, there's even a high probability you yourself already used a calculator for that exact same math problem at least once before. And since the results of mathematical expressions do not change, recomputing the expression again and again requires unnecessary computation. The way around this waste is to record the computation the first time it's ever made, in a retrievable way.

What we need is a way to store the result of a mathematical computation as well as some data that explains how we arrived at that computation. The result of the computation is stored in a data object, and the instructions for how we got to the result is stored in a pointer or similar object. So with the equation 2 + 2 = 4, the "4" is stored as the result, and the "2 + 2" is encoded in the pointer. The equation 1 + 3 = 4 is represented by a separate pointer encoding "1 + 3" that also points to the "4". The expressions 22 and √16 would be each represented by their own pointers, respectively pointing at the "4". And so on.

Later, we could create an application capable of finding the object assigned to the value of "4" and also locating the four pointers that would exist at that point in time:

• 2 + 2
• 1 + 3
• 22
• √16

Note that these pointers act as strings stored in the column of a table:

Expression | Result
2 + 2      | 4
1 + 3      | 4
2**2       | 4
sqrt16     | 4

Here is that same table with pointers:

Pointers   | Result
---->      | 4
---->      | 4
---->      | 4
---->      | 4

In this would-be system, every time a calculator is used to perform an original computation that evaluates to "4", a new pointer is created. If the number of pointers grows to be very large, which of course it will given the number of mathematical paths available to every real number, a dedicated data structure can be used as a repository representing "all the ways to compute the value of 4": 0 + 4, 1 + 3, 2 + 2, -1 + 5, -2 + 6, 5 - 1, 8 / 2, ?64... The thing to do is to either make this grow organically over time as more people compute something new that evaluates to "4", or to model all those pathways using computers. Though I'm using "4" as an example so far, really this data structure would link every number to every other number, as it should, because all numbers are mathematically connected by the relationships established by the operations encoded in the relevant computational pointers.

A world in which every computation that has been performed once by anyone anywhere in time was appended to an existing list or repository of computations (along with some data on how each of those computations was performed) would reduce the need for calculators to near zero as time progressed. How to tell if a particular pointer already exists—if a specific computation has already been performed—is the stuff of data structures far more complex than what I'm discussing in this post, but a blockchain might work for a portion of that task due to the way it makes use of Merkle trees, or perhaps another data structure optimized for searching for membership will do.

In any case, this brings me back to the expression (the polynomial) ??2 + ?? + 41.

Calculating Two Polynomials using Linked Lists

Let's say that I want to multiply two linked lists together. Speaking more accurately, let's say that I want to multiply the values stored inside two linked lists and to produce a third linked list to store the results. The first linked list stores the calculations of ??2 + ?? + 41 for 0 < x < 101. The second linked list stores the calculations of ??2 + ?? + 41 for 100 < ?? < 201. The third linked list stores the ten thousand values resulting from multiplying the one hundred results from the first linked list by the one hundred results from the second linked list.

How would I do that?

I'd ask Python to do the following:

linked_list1 = []
x = 1
while x < 101:
  firstresult = x**2 + x + 41
  linked_list1.append(firstresult)
  x += 1

linked_list2 = []
y = 101
while y < 201:
  secondresult = y**2 + y + 41
  linked_list2.append(secondresult)
  y += 1

linked_list3 = []
for i in linked_list1:
    for j in linked_list2:
        thirdresult = i * j
        linked_list3.append(thirdresult)

print linked_list1
print linked_list2
print linked_list3

When I execute this Python script, my terminal displays three bracketed lists:

[43...10141] - this includes 100 results, from 43 to 10,141

[10343...40241] - this includes 100 results, from 10,343 to 40,241

[444749...408083981] - this includes 10,000 results, from 444,749 to 408,083,981

In total, Python performs these 100 + 100 + 10,000 = 10,200 mathematical computations in just a few hundred milliseconds. That is absolutely incredible.

Here would be the table of expressions (before pointers) resulting in each of the values shown above (43...10141...10343...40241...444749...and 408083981):

Expression                                  | Result
(1**2 + 1 + 41)                             | 43
(100**2 + 100 + 41)                         | 10,141
(101**2 + 101 + 41)                         | 10,343
(200**2 + 200 + 41)                         | 40,241
(1**2 + 1 + 41) * (101**2 + 101 + 41)       | 444,749
(100**2 + 100 + 41) * (200**2 + 200 + 41)   | 408,083,981

In the next post, I'll explain the Python code above, especially the nested for loop used for the third list. I'll also continue pulling on this thread about a future without calculators.