Why Sheffer's Stroke is NAND instead of NOR

As a young boy, diving into mathematics was a great release for me. I often manipulated numbers in my head, independently discovered cross-multiplication, and found the gradeschool introduction to logic fascinating. Logic, of course, one needs to understand intuitively in order to be an effective coder.

Famous science personalities were my heroes. From Newton himself playing with equations of planetary motion in his giant Principia tome, to Godel showing with marvelous simplicity that all mathematical investigation will be (hopelessly?) incomplete, to Hoffstadter's work on artificial intelligence (and from whom I first heard the word "meme"), to Feynman picking locks at Los Alamos for kicks and investigating what he found interesting with little regard to its future practical value.

These were the giants to be revered, the Atlases holding the world on their shoulders. If only we could all be like them, forgoing our petty disagreements, cults of personality, and clanishness... or so I thought. Later when I realized that the science and maths world contained all of these things, it was quite disillusioning. Yes, even the greats stepped on each other's work, stole each other's credit, and disagreed on basic notation and phraseology of important concepts, particularly as a new field was being developed.

"Sheffer's Stroke" is an example of this kind of thing. Denoted by "|" (or "pipe" as we techies call it), in modern notation it refers to the logical NAND function. a|b is true in all cases where a and b are not both true. However, Henry Sheffer explicitly refers to his proposed function as "neither-nor", false in all cases where a and b are not both false. In his 1913 paper "A set of five independent postulates for Boolean algebras, with application to logical constants", he has this to say:

(Read more)

HTML5 logic circuit builder using NAND gates

This blog entry won't serve as an introduction to Boolean Algebra or logic gates, but rather just to illustrate an HTML5 widget I wrote that lets you manipulate NAND gates. In fact, before you begin, you should understand what these tables mean:

NOR = f(a,b)    NAND = f(a,b)
a b  f           a b  f      
0 0  1           0 0  1      
0 1  0           0 1  1      
1 0  0           1 0  1      
1 1  0           1 1  0      

If that makes no sense, start with this Wikipedia article on logic gates.

In the early 20th century, the maths world went wild trying to expand on George Boole's work on logic. Ernst Schröder, Edward Huntington, and Alfred Whitehead each developed conflicting notation systems and postulate sets, each with published works that were pretty arcane. For instance:

(Read more)

Tax tables from 1998 to 2013 at a glance

The form below is the result of combing through PDF files from irs.gov to get an accurate picture of how federal payroll withholding tables changed through the years. I later tacked on tax tables to compare with the payroll tables to see how they lined up (which they do pretty well... with a couple exceptions that I'll get to). I've populated data from the years 1998 to 2013, and added a simple HTML5 interface for charting the results.

Choose a salary from the slider (if you don't see a slider control, the charts won't work with your browser - the HTML5 "range" input type currently only works in Webkit browsers and Opera), and then click married or single, to see the chart for that salary.

The code makes some basic assumptions for the sake of simplicity. First, the salary is taxable income, after other deductions such as 401k, social security, etc. Second, the tax line adjusts the salary down by the standard deduction (twice that for the "married" category, assuming "married filing jointly" is the filing status), where the withholding line does not. This appears to be the intent of the descrepencies between withholding and tax tables, that is, separating what your employer knows about you from what the government does. Your employer doesn't know about your mortgage interest, whether you'll file joint or separately, whether the child tax credit applies to you, how much you spent for college tuition, or any of the hundreds of other deductions or credits you'll talk to Uncle Sam about. They know what you contribute to 401k, how many dependants you intend to claim, and that's about it.

(Read more)

¿Hola?

So Scout and I stopped into the grocery store to buy a couple extra things for her lunch. We got to the checkout area, and decided to use a real lane instead of self-serve, since cashiers are much nicer to me when I have Scout in tow. (When I'm alone, it's self-serve only, unless the guy who looks like he just got out of prison is on duty at my local Kroger, he's alright.)

"Do you have your Kroger card?"

"No, but here, let me type in the number." I grabbed the giant rubber stylus, and poked at the "Alt ID" button, heard the reassuring click... and then nothing. So I poked at it a couple more times, and noticed that the button on the opposite side was occasionally gaining focus, and the language kept switching back and forth between Spanish and English.

"Oh, looks like your touch-screen is misaligned..." she mashed some buttons on the register, "...or something, you should probably shut this lane down until that gets re..."

"Try it now," she interrupted. Poke, poke, poke... Hello, Hola, Hello. Same thing.

(Read more)

Manhandling Gentran for fun and profit

About 10am on Wednesday, an instant message window pops up on my workstation, from my buddy and coworker Jim. "Hey, you see all those Gentran errors?"

"Ah crap," I thought, "there goes my day."

I work as a software developer, but in a specialized role: my group writes software to support a production electronic commerce and energy trading system, fitting it with new regulatory requirements, feeds to new vendors, retrofitting logging and administrataion solutions, and our current nightmare, making our code compatible with new vendor frameworks, and migrating it en masse. (Vendor lock-in, in my opinion, is the biggest scam played out on American businesses, and 9 years of bellyaching about that in my job has netted me very few victories.)

In short, I write code, but for the purpose of keeping an enterprise integration system running. In my group, we rotate who is assigned for "production support", where you try to work on your coding tasks as you can, but when there are any hiccups in the system, you're suddenly in a system admin role instead, complete with (justifiably) panicked business users worrying about the status of their million dollar wire transfer, or avoiding regulatory fines for processing data late, etc.

(Read more)

Pufftygraph, an HTML5 Spirograph with touch-driven gears

First, thank you, now defunct Kenner, for the most excellent Spirograph toy. I had a Kenner 401 Spirograph set as a boy, and I fondly remember the joy of trying to drive the gears with a pen, and watching as the hidden shapes were revealed.

About a year back, I did some searches for online spirograph apps, thinking little Scout, then 6 years old, would enjoy it. I found some nice sites talking about how hypotrochoid math works, a complete listing of the gear ratios of one of the Kenner 401 set with close-up images of each gear, and several Flash, java, and HTML5 apps to draw hypotrochoids with given gear ratio inputs. However, nowhere did I find an app that showed the gears move as you drew, which as far as I was concerned was the main draw.

I decided that was a perfect excuse to brush up on my HTML5 animation skills, and within a few days I had code that would draw actual gears that followed mouse movements or touch gestures, drawing a hypotrochoid in its wake. I added the necessary elements to let it function as a smartphone web app, posted it here, and showed it to my daughter Scout, who thought it was a fun enough idle amusement for a minute or two, but since it could only make the one shape, didn't have much replay value.

I shelved the code and moved onto other things, but late this year I returned to the app and spruced it up some, and presented it to Scout under the title Pufftygraph ("Puff" is one of her nicknames) as one of her official Christmas presents. She and her mom enjoyed playing with it while Christmas cookies were in the oven, and it seemed to be a big hit with both of them. Here's an example of a drawing it can produce now:

(Read more)

iPhone multi-touch events and braille-like input

Below is a quick demo of me "typing" a short phrase and some numbers using a modified version of my Blind Input iPhone web app. This is a proof of concept app that doesn't integrate into the phone's other text entry forms, and is arguably more difficult to learn than braille. In case it appears I've solved some great accessibility problem, Siri and the iPhone's native accessibility features has me beat in spades, and my app is only an interesting idea I wanted to experiment with.

(Read more)

The math behind HTML5 context transforms

If you've drawn widgets with HTML5 canvases, you've no doubt come across such methods as ctx.translate(x, y), ctx.scale(x, y), and ctx.rotate(radians). These are all convenience methods for ctx.transform(a, b, c, d, e, f), which applies a generic affine transform to the canvas. Consulting the specs will show that the a-f variables refer to this transformation matrix:

If this looks incomprehensible, it might help to express the matrix in basic Algebraic terms:

 x' = ax + cy + e, and
 y' = bx + dy + f

(Read more)

Simple Javascript RGB/HSV converter

This is a simple and straightforward converter between RGB and HSV values, with RGBs from 0 - 255 and HSV values with hue from 0 - 359 and S/V from 0 - 1. I wrote it for an as yet unfinished HTML5 red-eye correction tool, but I'll be unable to devote much time to side-projects until after the holidays, so I thought I'd put this up now in case someone found it useful.

Enjoy!

function getHSV(r, g, b) {
  var h, s, v, max, delta;

  // v (value) is the highest of the RGB values scaled to [0-1]
  max = Math.max(r, Math.max(g, b));
  if (max == 0) return [0, 0, 0];
  v = max / 255;

  // delta is the difference between the largest and smallest of RGB
  delta = max - Math.min(r, Math.min(g, b));
  if (delta == 0) return [0, 0, v]; // No delta = grey, only v is significant

  // s (saturation) is delta divided by max
  s = delta / max;

  // h (hue) is a number in degrees describing the color's angle on the hsv color wheel
  if      (r == max) h =     (g - b) / delta;
  else if (g == max) h = 2 + (b - r) / delta;
  else if (b == max) h = 4 + (r - g) / delta;

  // convert hue to degrees
  if (h < 0) h += 6;
  h *= 60;

  return [h, s, v];
}

function getRGB(h, s, v) {
  var quadrant, max, mid, min, fraction;
  max = Math.round(v * 255);
  if( s == 0 ) return ([max, max, max]); // Greys

  // Quadrant is between 0 and 5, where 0, 2, and 4 are red, green, and blue
  h /= 60;
  quadrant = Math.floor(h);

  // fraction is distance away from quadrant representing hue's primary color
  fraction = (quadrant % 2 == 0) ? (1 - h % 1) : h % 1;

  // min and mid are the smaller two RGB colors in the final return array
  // We don't know what primary colors they represent...
  min = Math.round(max * ( 1 - s ));
  mid = Math.round(max * ( 1 - s * fraction ));

  // ...until we check what quadrant we're in
  switch (quadrant) {
    // reds
    case 5: return [max, min, mid];
    case 0: return [max, mid, min];
    // greens
    case 1: return [mid, max, min];
    case 2: return [min, max, mid];
    // blues
    case 3: return [min, mid, max];
    case 4: return [mid, min, max];
  }
}

Internet Explorer rendering issue fixed

I noticed today that viewing this site in IE blew things up. This was due mainly to putting javascript source for HTML5 canvas operations above the fold in a couple of blog entries.

I fixed that, so the page should look normal to IE users... however, you're missing out. Use an HTML5-capable browser instead to get the full gist of what I've been working on lately. And also the cool pacman banner.

In other news, Adelaide turns one year old on Sunday! Here she is with her sister Scout, the person who has given Liberty and I the most help with the baby, and who is possibly the most loving and patient sister a baby could have. I love them both more than I can say... but I'll keep trying anyway.

Counting Squares

NPR's "Science Friday" posted a square-counting puzzle on their Facebook page yesterday, and a friend of mine challenged me to write a program to count them, hopefully coming up with the same answer (40) that we did with a manual count.

My first pass is a generalized (more or less) solution where different sized boards can be created with arbitrary horizontal or vertical lines. It's not the most solid thing I've ever written, doesn't take user inputs or validate the hardcoded input, but it illustrates a simple, brute-force attack of the problem.

This requires an HTML5-capable browser (Chrome, Firefox, Safari), and should start counting 5 seconds after loading.

(Read more)

Dear Scout

So Scout's father moved to California, and this weekend I flew her out to see him, where she'll stay until just before school starts. Combine missing a girl I love with my recent dive into cryptography, and the natural outcome is, of course, to write her a letter - in secret code!

When I was in high school, I had the idea to write a substitution cipher using symbols for letters. My code consisted of squares, circles, triangles, stars, horizontal, vertical, and diagonal lines, plus and equals signs, and some other unique but easy to draw symbols that the intervening 25 years has wiped from my memory. I used it to write a letter of no particular consequence to my friend Rachel (actually she was my friend Bill's friend, who I poached for purposes of odd geeky stuff like inventing strategy games to play and reviewing her early short stories), and she decoded it with little effort, predictable given her intelligence. What made it pretty straightforward to decode was context. I had formatted the letter like a letter, complete with spaces between words, and the encoded greeting "Dear Rachel" which let her immediately translate the 7 letters a, c, d, e, h, l, and r. Since "a" was included, a lone "I" was easy to translate, and then the rest could be filled in with a style akin to Sudoku, filling in words that were mostly complete already, and adding the newly translated letters to other words.

I wanted to do something like that for Scout, but I thought of a symbol set that would be both easy to write a program for, and comprise 26 letters and 10 digits: pairs of dice. Each die face could have a value of 1 through 6, giving 36 possibilities for a pair. I didn't want the code to be as easy as iterating through the alphabet and replacing 1.1 with a, 1.2 with b, etc., but at the same time I didn't want it to be so complex as to be off-putting for a 7 year old. It eventually ocurred to me that "Dear Scout" was an even better greeting than Rachel's, as it had no overlapping letters. If I kept the cipher alphabetized, but pulled "Dear Scout" to the beginning of the cipher, then the greeting would look like this:

(Read more)

Encryption, part 2: Elgamal and the Discrete Logarithm

In my quest to better understand the mechanics of encryption, I've found the Elgamal method the hardest to get my head around. The problem was not that the underlying math is difficult, it was that I didn't know some of the background terminology (cyclic group, congruence class, group isomorphism), the various explanations online all used different variables, and made references to "mathy" things it was supposed the reader was already familiar with. Lastly, the articles on discrete logs and Elgamal encryption on my go-to site for techie info, Wikipedia, were a hot mess, mistaking modular multiplicative inverse for division, and leaving out crucial middle steps (how to get from "collect underpants" to "profit", as it were). The whole affair really shook my faith in using Wikipedia as a trusted source for tech info.

A relatively simple explanation is this: You and your buddy both have a secret that combines to form an encryption key. To encrypt a message, multiply the key by the message value, divide by a modulus, and the remainder is your ciphertext. To decrypt, multiply the ciphertext by the key's inverse, and, again, divide by the modulus, and the remainder is the original message. Fin.

There is, naturally, some math involved, most of it geared around how to build the secret key so only you and your buddy know it, without either of you revealing your part of the secret. Let's start with some of the basic terminology, then get into the mechanics of building the encryption key.

(Read more)

RSA encryption and the other Sun Tzu

Background

Before we get started on how exactly RSA works and how it's related to Chinese mathematicians, it's important to have a basic comprehension of modular arithmetic, totients, and the "modular multiplicative inverse". None of these are very difficult, but they aren't commonly talked about, so here's a quick refresher:

Modulus

In simplest terms, what you're looking for in a modular problem is the remainder of a division. Dividing 7 by 3 gives 2 with a remainder of 1. Expressed as a modular equation, 3 is the modulus, and 7 and 1 are congruent. The equation can be expressed like this:

7 ≡ 1 (mod 3)

(Read more)

Four ways to construct a pentagon

There are animations of the 4 compass and straightedge construction techniques at the bottom of this entry, but they require an HTML5 capable browser. (I suggest Chrome, but the animations should work with a modern Firefox, Safari, or Chromium... but let me know if they don't.)

Also included are animations of the first 6 "problems" in book 1 of Euclid's Elements, as a preview of a larger project I'm working on, and two variations on creating a heptadecagon (a seventeen-sided polygon).

Over the last few weeks I've been spending what free time I have obsessing over the odd mathematics of Argand diagrams, complex roots, and how they relate to constructing regular polygons with a compass and straightedge. I found, among other things, that I had forgotten quite a bit from my trig and geometry classes from 25 years ago.

(Read more)

Compass and Straightedge geometry meets HTML5

This is a proof of concept build of an HTML5 engine to perform classical Greek compass and straightedge calculations, as described in this Wikipedia article. In brief, an initial set of points can be created, and then points can be connected by lines, circles can be drawn with one point as center and another as one point in the circumference, and finally the points where circles and/or lines intersect can be added as new points. With those simple rules, angles and line segments can be bisected, and certain regular (equilateral) shapes can be created.

I have created a rudimentary language to describe the adding of points, lines, and circles, and finding their intersections, which I discuss briefly after the demo below. Without further ado, choose a sample "program" to run to bisect an angle or create a regular shape. If you're a fan of Gauss, be sure to check out the heptadecagon.

(Read more)

Animated prime number machine

This uses the HTML5 canvas architecture, so no IE8 or less; sorry. I have only tested it with Google Chrome, so it may not work in other HTML5-capable browsers. If you find this to be the case, please leave feedback with any errors you see, and what browser version you're using, and I'll see what I can do to get it working for you.

The principle of the prime number machine is of rolling coins and elevators. I created this because I thought it would be neat to have a way for prime numbers to be produced by a set of mechanical rules rather than with pure mathematical methods. Here is a basic description of the rules:

If a coin rolls into an empty box, it creates an elevator with the height shown on the coin, and a new empty box appears.
If a coin hits the top or bottom of an existing elevator, it bounces off with no effect.
The coin's number increments after each cycle
The elevators go down a floor during each cycle until the top car is flush with the ground line, then they begin going back up to where they started.

This results in two basic phenomena: All new elevators correspond to prime numbers. When a coin does not have a prime number on it, all of the elevators corresponding to the coin's prime factors have a car flush with the ground.

Enjoy!

(Read more)

Encounters with the police

The cops have had an awful lot of bad press lately, for example the interactions with OWS protestors such as this one, and this sobering article from the Sarasota Herald-Tribune, or this report of a former marine killed in his home by a SWAT team who erroneously thought he was a drug dealer. And erroneously thought their team member who tripped had just been shot.

My personal encounters with law enforcement have been qualitatively different. I have interacted with the police 26 times, and although that number seems large, none of them ended in an arrest, and in only two seemed like good material for an episode of Cops. In rough order of occurrence (I'm approximating my age on a few of these), they are:

(Read more)

Think of the children!!

No seriously, think of the children. And not the bounty.

About a month ago, I listened to an NPR story on "All Things Considered" on my drive home from work, which concerned Native American children in South Dakota being declared "neglected" in high numbers, and being removed from their families and put up for adoption. The implication is that the South Dakota government was using a financial incentive as an excuse to go all Captain Pratt on the natives, killing the Indian and saving the man, by means of placing their kids in white homes. The text version of the NPR story is available here.

(Read more)

Tinkering with Calculus

A little document I whipped up on Google Docs after dusting off a calculus book:

(Read more)

Adelaide

Adelaide Lenora Allerding
October 14, 2011 4:20am
6lbs 12oz, 19.5"

(Read more)

Designing a Notes iPhone web app

"A pedagogical decision hides behind every design decision" -Dan Meyer

For the last few weekends, I've been coding in the early mornings while my wife sleeps beside me, working on a replacement for the broken built-in Notes app on her iPhone. My replacement is usable and stable at this point, and I'm just putting the final polish on the code to remove duplication, improve comments, delete orphan code, etc.

The tools I used to design this are the same as the diet tracker app I wrote for her to track her protein and calcium during her pregnancy: handwritten JavaScript, and Google's appspot.com webserver to properly serve the cache manifest's content type. This was initially going to be a quick hack to learn the API for Web SQL Databases, so I could retrofit database support in the diet tracker, but along the way I learned a lot about designing an HTML Notes application, which was more involved than I anticipated.

This post recounts some of the lessons I learned, and the decisions I made between competing solutions that each had pluses and minuses. Some screenshots of the current product are available below the fold.

(Read more)

Emulating iPhone rotating buttons with HTML5 canvases

This is a quick proof of concept tested with Chrome and Safari (which might also work in Firefox... testers?). I'm using timeouts and HTML5 canvas operations to spin buttons, and some DOM tomfoolery to add and remove rows to the document's body. The end result is an approximation of some iPhone settings screens that make you unlock delete buttons before you can remove items.

Enjoy!

(Read more)

HTML5 Web Databases in Chrome, round 1

New fact of life: To keep up with modern web programming, you need to get your head around asynchronous callbacks. To illustrate, here is a quick script I wrote to experiment with Chrome's JavaScript calls into it's SQLite implementation:

(Read more)

Rage against the Pitocin-Cesarean Complex

(and how I wrote my first iPhone web app)

"So I got me a pen and a paper and I made up my own little sign. I said thank you Lord for thinking about me, I'm alive and doing fine." - Five Man Electrical Band

Before rambling about my latest tinkerings, I have a small announcement: My wife and I decided to have a baby. She asked me not to make a big deal about it online, not post a broadcast "guess what?!?!" message on Facebook, and in the spirit of that I won't make flowery pronouncements here about the joys of fatherhood, or starting over at 40, or any of the hundreds of other things I would otherwise go on at length about. But there it is: I'm in love with a woman I think the world of, and at the beginning of January, with our third wedding anniversary near us and neither of us having one foot out the door or buyer's remorse, we decided to stop using birth control and try to have a baby.

By the end of the month, Liberty was pregnant.

(Read more)