How to multiply small integers while Markus human

“Hi, there,” cried Pippi, waving her big hat. “Did I get here in time for pluttifikation?”

Pippilota Delicatessa Windowshade Mackrelmint Efraim’s Daughter Longstocking,
as reported by Astrid Lindgren

He had bought a large map representing the sea,
Without the least vestige of land:
And the crew were much pleased when they found it to be
A map they could all understand.

“What’s the good of Mercator’s North Poles and Equators,
Tropics, Zones, and Meridian Lines?”
So the Bellman would cry: and the crew would reply
“They are merely conventional signs!

“Other maps are such shapes, with their islands and capes!
But we’ve got our brave Captain to thank:
(So the crew would protest) “that he’s bought us the best—
A perfect and absolute blank!”

Charles Lutwidge Dodgson,
writing as Lewis Carroll

Outline

  1. People don’t really know much about integers
  2. Various other matters
  3. Some animals have funny names
  4. Assorted topics
  5. Nonetheless, we somehow manage to get things done
  6. Possible cynical rant
  7. Therefore, formal methods will always be playing catchup, and our software will continue to be buggy as all get out.
  8. Profit!

With quizzes and whatnot as needed.

Ground rules

All I want is a room somewhere
Far away from the cold night air
With one enormous chair
Oh, wouldn’t it be loverly?

Lots of chocolate for me to eat
Lots of coal makin’ lots of heat
Warm face, warm hands, warm feet
Oh, wouldn’t it be loverly?

Audrey Hepburn
singing lyrics written by Alan Jay Lerner and Frederick Loewe
while portraying George Bernard Shaw’s character
Eliza Doolittle

Our friends the Integers

Experiment 0: Even odds

Experiment One: Good times

wombat dog
proboscis monkey cat
aardvark cow
mongoose horse
kakapo robin
aasvogel goldfish
blobfish hawk
ocelot salmon
meerkat parrot
aye-aye tiger
axolotl squirrel
pink fairy armadillo beaver

Reminder of why we’re looking at all this

I. We’re using a lot of power…

  • A low-power CPU (Atom): ~10 Watts (excluding memory, I/O, etc.)
  • A modern server CPU: ~100 Watts (excluding memory, I/O, etc.)
  • A server: ~400 Watts
  • A Monte Carlo cluster: ~40,000 Watts
  • A human brain: ~10 Watts

II. …to produce mediocre results.

Every program can be made at least one line shorter, and contains at least one bug. Therefore, every program can be reduced to a single line of code, which still doesn’t work.

Alan Cox, Edsger W. Dijkstra, Bill Gates, Donald Knuth, Samuel Langhorne Clemens (writing as Mark Twain), and Abraham Lincoln

A heuristic is an algorithm in a clown suit. It’s less predictable, it’s more fun, and it comes without a 30-day, money-back guarantee.

Steve McConnell, in “Code Complete”

Roger Corman: Stanley, you can’t polish a turd.
Stanley Kubrick: Sure you can. You just have to freeze it first.

Apocryphal conversation in an editing studio

The Vermin only teaze and pinch
Their Foes fuperior by an Inch.
So, Nat’ralifts obferve, a Flea
Hath fmaller Fleas that on him prey,
And thefe have fmaller yet to bite ’em.
And fo proceed ad infinitum

“On Poetry: a Rapsody” by Jonathan Swift, writing as NULL

In section 6.2.1 of his ‘Sorting and Searching,’ Knuth points out while the first binary search was published in 1946, the first published binary search without bugs did not appear until 1962.

Jon Bentley, misquoting Donald Knuth

Sally can work.

See Sally work.

Work, work, work.

Three sentences from Zerna Sharp’s “Dick and Jane” series.

It had been no part of his plans to come whizzing down off the rail into this singularly soup-like water which tasted in equal parts of oil and dead rats; but, now that he was here he was prepared to make the best of the situation.

This dialogue has been set down as though it had been as brisk and snappy as any cross-talk between vaudeville comedians, but in reality Uncle Donald’s peculiar methods of conversation had stretched it over a period of nearly three minutes: for after each reply and before each question he had puffed and sighed and inhaled his moustache with such painful deliberation that his companion’s nerves were finding it difficult to bear up under the strain.

One of the suits of armour which had been familiar to him in his boyhood loomed up in front of him, and with the sight came the recollection of how, when a mere child on his first visit to Windles, playing hide and seek with his cousin Eustace, he had concealed himself inside this very suit, and had not only baffled Eustace through a long summer evening but had wound up by almost scaring him into a decline by booing at him through the vizor of the helmet.

Three sentences from P. G. Wodehouse novels

C’est ne Norman Rockwell

Experiment II: To err is human

WAH

We met at Starbucks. Not at the same Starbucks. We saw each other at different Starbucks across the street from each other.

Parker Posey playing Meg Swan uttering a line written by Christopher Guest and/or Eugene Levy

Experiment 1,2,3: + – x

Multiplying Number Chains
Memory holds Math facts & rules Math facts & rules + game rules
Goal is Answer to multiplication Chain to target
Misapplication leads to Wrong answer Erroneous chain
Variations Different bases Complex targets, different ops
Wilder variations Non-place value systems Monotonic planning problems
Problems come in different sizes Larger numbers Larger goals
Some problems have cute answers 111111 × 9 65536
Where analogy breaks down Unique right answer length vs. ops cost, side goals
Possible to recognize right answer Sort of (not minimal)
Perfect algorithm is known Sort of

Experiment 1002: Multiply with this

Inputs:

  • A & B, arbitrary precision integers (bignums) represented as strings

Output:

  • C, their product, in the same format

Assume the language supports:

  • Integers (say, 64-bits)
  • The usual control structures
  • Generous string operations (subscripting, length, concatenation, regular expression mapping, etc.)
  • Garbage collection

Multiplying Number Chains Programming
Memory holds Math facts & rules Math facts & rules + game rules language semantics & limitations
Goal is Answer to multiplication Chain to target Code that does what we need it to
Misapplication leads to Wrong answer Erroneous chain Buggy code
Variations Different bases Complex targets, different ops Different languages
Wilder variations Non-place value systems Monotonic planning problems Hardware, other types of processing
Problems come in different sizes Larger numbers Larger goals Harder problems
Some problems have cute answers 111111 × 9 65536 Duff’s device
Where analogy breaks down Unique right answer length vs. ops cost, side goals Many answers, some better by various criteria
Possible to recognize right answer Sort of (not minimal) Only stochastically in many cases
Perfect algorithm is known Sort of No