Recent content on ℤ→ℤ
We develop a formula for counting the number of bags of length \(l\) containing \(d\) distinct elements drawn from \(t\) objects. The formula involves multiplication of combinations without replacement and combinations with replacement. We present alternative forms of the formula and a generator in Python. Our motivation was computing probabilities of various types of card hands, such as how many…
This year is the 60th anniversary of Joseph Weizenbaum’s article “ELIZA—A Computer Program For the Study of Natural Language Communication Between Man and Machine”. ELIZA was a natural language “engine” for running scripts of various conversational personas. The DOCTOR script became the paradigmatic example of a chatbot and ELIZA was re-implemented many times. A…
Within the history of cryptography, the tale of how Bletchley Park broke Germany’s Enigma cipher has been told many times, in both print and on screen. With so much emphasis on the “plucky Brits overcoming the odds” angle, I often wondered how secure the Allied codes were and if there was a parallel story on the Axis side. Dermot Turing (nephew of Alan Turing and writer of…
TimesSquare is a programming puzzle created by Dennis Shasha and published in the April 2026 issue of Communications of the ACM . The puzzle requires deriving missing digit values within a square matrix, given, at least, the main diagonal, the sum of all digits within the matrix, and a value called the RowCol which is a function of all the digits. The challenge is to find a sub-exponential time…
Over the past year, I’ve been acting as the treasurer for a small publishing company. I converted our books from a collection of spreadsheets to a plain text accounting ledger and wrote programs to automate balance, income, and sales reporting using a tool called Beancount. These recipes may be useful to others running businesses, particularly if they have some programming talent. Plain Text…
While the study of textbooks has proven fruitful in the study of the history of mathematics, there has been little attention to computing books and their role on the development of computer science, the computer industry, and public understanding. Working to close this gap, W. Patrick McCray has written README , a “book about books about computing.” (pg 3) The scope is “a history…
Leonardo of Pisa (c1170-1241+), better known as Fibonacci, wrote Liber Abaci to introduce and advocate the adoption of “Indian figures” (Hindu-Arabic numerals) to Italy. The book explains how to perform arithmetic and common business problems using the digits and a positional number system. Leonardo uses a composed fractions (aka composite fractions, aka linked fractions) notation to…
George Boole (1815-1864) was a mathematician best known as the progenitor of the Boolean algebra, the system of logic that acts as a fundamental layer within digital systems. Although he never gained a college degree, he spent many productive years as the chair of mathematics at Queen’s College, Cork. Desmond MacHale’s The Life and Work of George Boole is a well-written exploration of…
In 1971, three college roommates developed an educational computer game. Titled OREGON, it was a simulation of westward migration along the Oregon Trail and proved to be a hit among the students. One of the designers, Don Rawitsch, later carried a copy of the source code to his new employer, Minnesota Educational Computing Consortium (MECC). From 1975 to 1983, OREGON was MECC’s most popular…
In Fifth Edition (5e) Dungeons & Dragons ™ (D&D), druids can transform into certain Beast forms using the Wild Shape ability. Similarly, casters of the Polymorph spell can transform allies and enemies into Beasts. Players often find selecting a Beast form onerous (there are 84 forms defined in the System Reference Document (SRD) alone) as this is a multi-dimensional decision problem. We created an…
On August 15th, 1971, President Nixon declared a 90-day freeze on wages, rents, and prices. The next day, the Office of Emergency Preparedness (OEP) was charged with implementing the Freeze. OEP launched an administrative crash program, leveraging the expansive power of the federal government, and also took the risky step of developing novel software to facilitate coordination of hundreds of…
John Bridges is a software engineer that co-developed PCPaint, which in 1984 was one of the earliest digital painting programs and helped spur the use of mice within the IBM PC market. He supported the growing number of PC video developers by freely releasing the VGAKIT and TGA utilities, tools that helped developers understand and compensate for the many hardware and software quirks of the era.…
The Seymour Cray Era of Supercomputers: From Fast Machines to Fast Codes is a technical and business history of the roughly three-decades when Seymour Cray dominated the development of a class of computer called the “supercomputer”. The book covers the development of the major supercomputer models, the technical decisions and trade-offs involved, and changes to the market. The book…
As catalogs for digital marketplaces grow in size, customers have greater difficulty in finding products that meet their needs. Marketplace owners might improve product discovery by adding new categories, tags, or other searchable and filterable metadata to product descriptions. As it is often difficult to get product owners to update old product descriptions, a marketplace owner may use automated…
Connect 4 is a solved game in the m,n,k family. On a 7 column, 6 row board, players alternately drop a token into a column, attempting to establish four tokens of the same color along any row, column, or diagonal. John Tromp created a labeled dataset of all valid eight ply positions with their perfect play win results. We present a dataset that presents all sequences of plies that lead to each…
Early post-war computing can often seem alien as terminology mixed metaphors and the pioneers brought their own distinct toolsets to the field. Thus, it seems fitting that a powerful influence on computing design would come from a “Martian”: John von Neumann. During the war, von Neumann surveyed computing capabilities within the United States, which introduced him to the ENIAC and the…
Ludii is a general game system for modeling games and puzzles, although it focuses on historical and traditional games. Ludii was recently used to provide the training data for a Kaggle competition . I noticed their wishlist contained Wumpus World , a common puzzle used for AI training and education. Intrigued, I implemented and submitted a version of Wumpus World . Wumpus World in the Ludii…
MacPaint is a monochromatic raster image painting program that introduced many people to mouse-driven controls, tool palettes, and copy and paste integration with other applications. One of two launch applications for the Apple Macintosh in 1984, MacPaint is emblematic of the Macintosh’s early quirky revolutionary branding, focus on ease of use, and appeal to artistic customers. Using the…
Charles Dodgson (pen name Lewis Carroll) had difficulty remembering numbers, such as dates. He developed a cipher to help him remember numbers by embedding them in couplets or phrases. For example, the couplet “Brass trumpet and brazen bassoon, will speedily mark you a tune” encodes the specific gravity of brass (8.39) in the last four consonants: r k t n (y is treated as a vowel). In…
The new generation of code assistance tools powered by Large Language Models (LLM)s may be useful in efficiently categorizing and translating historical software corpora. In this qualitative study, we examine LLM performance in explaining and translating FLOW-MATIC programs. We also test their reliability by injecting OCR-like errors into the text. Released in 1958, FLOW-MATIC targeted business…
Chatbots Decoded: Exploring AI is a new exhibit from the Computer History Museum (CHM) opening November 20th, 2024. In development for more than a year, the exhibit covers both the history of chatbots and conversational interfaces as well as the social ramifications of the technology. While there is not an explanation for why GPUs rather than CPUs are so useful for learning or what…
From the Board Games Study Journal : Mathematical analysis of the Royal Game of Ur Despite many discoveries and proposals for rules for the ancient board game known as the Royal Game of Ur (RGU), no mathematical analysis has yet been performed investigating those rules. In an attempt to fill that gap, this paper presents an initial mathematical analysis of the RGU from an introductory point of…
I’ve given this blog a new look by switching the theme from Noteworthy to Long Form , the latter a theme of my own design. Why the change? I adopted the Noteworthy theme at the onset of this blog and maintained a branch with some fixes (primarily KaTeX support). Since it is a cliche that engineering blogs will write more about the blog’s infrastructure than actual content, I wanted to…
The mapping of integers to integers is a fair summary of the work of programming. A blog about computer science, history of computing, engineering, game theory, and other things that attract my interest. Contact / Social Links E-Mail LinkedIn GitLab GitHub Google Scholar
Many corporations and agencies allocate a certain amount of their budget towards the creation of public artwork. For instance, New York’s Metropolitan Transportation Authority (MTA) has funded nearly 300 permanent art installations since 1982 under the city’s “Percent for Art” law . If we question the effectiveness of the program, we immediately run into problems of…
In December 2022, Adobe, through the Computer History Museum (CHM), released the source code for PostScript®, version 1.0. PostScript is one of the foundational technologies of the desktop publishing revolution of the early 1980s, along with laser printers, the graphical user interface of the Apple Macintosh, and Aldus PageMaker. PostScript is a programming language and a page description format…
ZLister, a to-do list management application, is now available. ZLister allows you to create lists with entries and entries can be marked complete or incomplete (“to do”). ZLister’s user interface is designed for mobile devices, but may also be used on the desktop. ZLister does not store your data in the cloud and can run offline. Motivation and Goals For the last several years,…
I’ve started studying a larger historical code base. Within this post, I want to summarize the sort of historical questions we might ask and notes on how to approach them. Objective My objectives for studying and writing about historical source code is to understand and communicate the: Intent and purpose of the software Design, engineering trade offs, and technical decisions Significance…
Twelve states require community associations, such as homeowners associations or HOAs, to conduct periodic reserve studies. A reserve study is a financial planning tool for estimating an association’s ability to fund current and future planned maintenance costs for large projects, such as roofs, pools, and asphalt roads. An underfunded reserve may lead to special assessments. Yet, due to…
Before the widespread existence of software repositories like CPAN, NPM, and PyPI, developers seeking to reuse an existing algorithm or library of routines would either check books or journals for code, or, they just might post a classified ad: Request posted in Decuscope 1965, Vol 4/Iss 2 User groups provided catalogues of software, from mathematical algorithms to system utilities to games and…
In my post on the Method of Differences , I focused on using the technique to generate mathematical tables. As some readers noted, there are additional and interesting modern applications of the technique. This post will discuss two of them: sequences to functions , a method of analyzing sequences, and strength reduction , a compiler optimization technique. Sequences to Functions Rather than…
The “Method of Differences” is a mathematical technique for reducing the computation of polynomials to repeated addition. Once the system is setup, relatively unskilled human computers can populate dense mathematical tables. This is the “difference” in the Charles Babbage’s Difference Engine which aimed to automate the creation and printing of these tables. I have…
Although historians are usually pushed to decide questions of “who was first,” the question of impact is more interesting. Konrad Zuse has a claim to the first computer, the first high-level computer language, and the first European commercial computer sale, but his relative isolation working in Germany in the 30s and 40s limited his visibility and impact. It wasn’t until the…
For those interested in the history of tabletop roleplaying game design, Monsters, Aliens, and Holes in Ground is an excellent, near encyclopedic treatment. The author, Stu Horvath, documents major and minor game systems, how they innovated or were influenced by other game systems, and how the systems expanded with settings and adventures. Horvath covers the 1970s through the 2010s and, reading…
Shared Fantasy is an ethnographic study of fantasy roleplayers in the Minnesota area from 1977 to 1979 by Gary Alan Fine. As this predates the moral panic of the early 1980s (James Egbert disappeared in 1979; the movie Mazes and Monsters was released in 1982) and the resultant explosion in popularity of the field, it also serves as a historical artifact of the hobby’s early days. Does this…
Godot 4’s HTML5 export uses WebAssembly, WebGL, and SharedArrayBuffers. Browsers require a secure context for these features to be available, which requires sending certain HTTP headers when serving the game content. For development, there are two straight-forward ways to serve the content: Godot’s Python http server and Miniserve. Godot’s Python HTTP Server The Godot team has…
Drawing Down the Moon: Magic in the Ancient Greco-Roman World is an academic history of the perspective and practice of magic. Broad and detailed, Edmonds covers multiple types of magic, discussing the who, what, why, and how of each, and attempting to place the magic within the broader culture practice. Themes carried throughout include what counts as magic and how that magic might be embedded…
Before dice notation was adopted, early roleplaying games described dice rolls using range notation. For example, 3-18 indicated rolling three six-sided dice or 3d6 in modern notation. Converting a range to dice notation requires a little thought, so I’m going to describe a way to solve the conversion programmatically. Background Dice notation is a succinct domain specific language to…
Robinson after being elected to the Moscow Soviet, book page 103 Robert Robinson was a black machinist who accepted an offer from the Soviets to leave his job at the Ford plant to come to Russia to help train their machinists in the 1930s. Accepting the deal, he pursued his engineering career and invented many productivity improving tools, acquired a mechanical engineering degree, survived the…
The SHARE organization was organized in 1955 to share operational knowledge and computer programs for operators of the IBM 704. “Operational knowledge” included monthly availability reports and, perhaps unexpectedly, safety advice. Each site reported its own availability via a common form. Each installation was given a two-letter identifier (which, as SHARE grew to more installations,…
In the Call of Cthulhu adventure “Chateau of Blood”, the characters are faced between spending the day trapped in an ominous chateau where they will likely be attacked by monsters or attempting to navigate a treacherous mountain trail as a ferocious blizzard blows. Inspired by Hammer films , the characters are encouraged to stay inside the chateau, find clues, and face the monsters…
Slaying the Dragon: A Secret History of Dungeons & Dragons by Ben Riggs Author’s website Slaying the Dragon is a business history of TSR, focusing on the Lorraine Williams period (1985-1997). During this period, TSR recovered from the excesses of the Gygax/Blume Brothers period, launched the 2nd edition rules, novels line, and attempted pivots and expansions of their IP. However, the sales…
Slack’s business logic for showing notification periodically appears in LinkedIn posts and such. In Slack’s original post, this diagram was meant to illustrate what logic was being transferred from the multiple Slack clients to the server, but the diagram has since been taken as an example of product complexity and how development is harder than it may sound . In contrast, I think the…
Being on-call is often a necessary part of the job, particularly for engineers in a SaaS business. The burden of operations often negatively impacts morale and productivity. If we were to estimate the impact on a team, we could build a model based on incident frequency, ticket severity, time of alert versus sleeping schedules, and other operational metrics. Alternatively, we can ask the on-call…
COBOL is for Big Data. Well, sort of. Awhile back, I noticed that the COBOL SORT verb was overpowered. Rather than sorting an array of items or even sorting a file, it included a generalized ability to stream in arbitrary inputs — () => Stream[T] —, where T is a key/value pair, and process the outputs in order — SortedStream[T] => () . This power is useful if you are writing a…
“The best way to grasp the spirit of a programming language is to read example programs” as Knuth wrote in the “The Early Development of Programming Languages” 1 . Today, it is common practice to provide an example program on the front page of a programming language’s marketing site (i.e., a “hero code example” as it were). Since the objective of the…
Rosetta Code is a programming chrestomathy wiki, that is, it is a site with lots of examples of tasks completed in multiple programming languages. The site has been around since 2007 and now has 1,100+ tasks and 100,000+ code submissions over 900+ languages. To help other researchers, I’m publishing an export of the code samples as a sqlite database via DBHub.io and the source code via…
In 1986, a survey of approximate string matching algorithms found the algorithm used in the PLATO computer-aided instruction system was third place in quality (F1 score) and was an order of magnitude faster than the best performing algorithms. The PLATO algorithm used an unusual dimensional projection approach, while the competing algorithms of the day used edit distances or phonetics. However,…
Approximate string matching algorithms (ASMA) determine if two strings are the same, “close enough”, or are distinct. Spelling error detection and correction were early applications of these algorithms, and today ASMAs (or similar techniques) are used in natural language understanding applications. Hundreds of papers have been written on the subject ( 1980 survey , 2001 survey ), but…
In 1976, Los Alamos hosted the International History of Computing Conference where the pioneering efforts of computing were discussed, often by the pioneers themselves. The Computer History Museum has posted videos from the talks , which cover important machines, languages, people, institutions, and practices invented in the first 30 years of the craft. Dag Spicer, the senior curator at CHM, has…