Social Media : Paul Senzee

Paul Senzee on Social Media

Twitter
Facebook
LinkedIn
BrandYourself
Google+
Paul Senzee's Stories

Google's Deep Dream

Google put their image recognition software into a feedback loop and produced Deep Dream.  Then they released the code into the wild.  At some later time, I want to post a bit about the theory behind deep learning, especially convolutional neural networks.

Anyhow, a good place to find Deep Dream images is reddit /r/deepdream.  Here's a google blog post describing the software.






















From that post here's an image worth 1000 words about Deep Dream:

And, since I'm an artsy-fartsy kind of guy myself, I couldn't help but make a bunch of images with it from photos I've taken.

Fibonacci Code Golf

The other day, one of my colleagues said he'd once been asked to code a function to produce the nth fibonacci number for a job interview.  We got talking about the shortest possible function to do this.

A fibonacci number is the sum of the two previous fibonacci numbers.  The first and second fibonacci numbers are defined to be 1.  That makes the third 2 (1 + 1), the fourth, 3 (2 + 1) and the fifth, 5 (3 + 2).  Cake.

1, 1, 2, 3, 5, 8, 13, 21, ..

Beautiful, Recursive and Horribly Inefficient

A clean and simple implementation in C might look like this:

int fibonacci(int n)
{
    if (n == 0) 
        return 0;
    else if (n == 1 || n == 2) 
        return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Since I'm not a golfer, and code golf and mini golf are the only kinds of golf I play, I came up with the following in (bad) C.

f(n){return n<3?1:f(n-1)+f(n-2);}

Now, this one isn't correct for 0, which should return 0, so let's revise it at the expense of four more characters.

f(n){return n<3?n?1:0:f(n-1)+f(n-2);}

That works.  Kind of.  The highest n you can pass it is 46 (returning 1,836,311,903), because after that it overflows the 32 bit signed int (which holds a maximum value of 2³¹-1 = 2,147,483,647).

Okay, but the real problem with these functions is how phenomenally slow they are.  You wouldn't be able to get much past 46 anyway without rendering your machine absolutely useless.  This is a classic recursive function, that is, a function that calls itself.  This fibonacci function itself is often used to demonstrate the elegance of many functional languages.  For example, here it is in OCaml:

let rec fib = function
  | 0 -> 0
  | 1 -> 1
  | n -> fib (n-1) + fib (n-2)

As it turns out, to calculate f(46), you end up calling f() 3,672,623,805 times!  f(47) makes 5.9 billion and f(50) makes nearly 20 billion calls.  The recursive fibonacci sequence grows in number of calls on the order of 2ⁿ, which makes it roughly equivalent to the rice and chessboard puzzle.

Ugly Lookup Table

So we need to rework it and make the shortest version that isn't super inefficient.  Since 46 in the maximum n that fits in a signed 32-bit int (and 47 unsigned), we could just make a precomputed look-up table.

int fib(int n)
{
    static int fibs[] =
      { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 
        610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 
        46368, 75025, 121393, 196418, 317811, 514229, 832040, 
        1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 
        24157817, 39088169, 63245986, 102334155, 165580141, 
        267914296, 433494437, 701408733, 1134903170, 1836311903 };
    return fibs[n];
}

That's as fast as you're probably going to get, but it's ugly and not particularly short.

Iterative and Fast

You can also do it iteratively, without any recursion at all:

int fib(int n)
{
    if (!n) return 0;
    int p = 0, q = 1;
    for (int i = 2; i < n; i++)
      { int t = p; p = q; q = t + p; }
    return p + q;
}

It's starting to get a little longer, though, so I don't bother to shove it on one line or abbreviate int fib(int n) into f(n) like with the shortest ones above.  This function can be literally billions of times faster that the first ones.

Returning to Recursion, with Memoization

But..  I've got a short recursive version that outperforms this one on the whole, especially when called more than once, because it builds up a look-up table dynamically, with a simple technique broadly called memoization.

f(n){static int m[64]={0,1,1,0};return !n||m[n]?m[n]:(m[n]=f(n-1)+f(n-2));}

Fast and short.

No Recursion, No Iteration, Just a Formula

Let's do one more.

There is a closed form calculation of the fibonacci number that requires neither iteration nor recursion.  You just calculate it and there you go.  Here is my shortest implementation of that:

f(n){double A=sqrt(5),B=A/2;return(pow(0.5+B,n)-pow(0.5-B,n))/A;}

Short.  No iteration, no recursion.  Over several calls, I figure this will be slower than the previous function, but it's way slicker.

The Book of Sand

Argentine literary genius Jorge Luis Borges ('magic realist') is one of my favorite writers. Borges unravels the many human uses of information within a universe that is mystical and mathematical at once. His work illuminates the way we, as human beings, struggle to capture meaning - any meaning - from infinite quanities of data. Borges explores ideas such as the recursivity of mirrors, points in space containing all the universe (The Aleph) and man's struggle to find meaning in endless information (The Library of Babel & The Book of Sand).

For many software developers, creation of software, while frequently mundane, is still very much an aesthetic pursuit - an art. When a piece of software is 'beautiful' it is so in the same way that a Borges short story is beautiful, and in a very different way than a Dostoevsky short story is beautiful (which is the gut-wrenching, depth-of-human-suffering-and-existential-torment sort of way) or in the way a Hemingway story (the depth-of-human-suffering-but-don't-actually-ever-say-it sort of way) is.

A Prediction from 2007

In 2007, I wrote a post called --

Xbox 360, PS3 Games Unplayable on Future Hardware?

Where I concluded that, due to technical reasons detailed in that post --

.. I suspect that far more Xbox 360 and PlayStation 3 games will be unplayable on future hardware than Xbox and PS2 games on the 360 and PS3.

Unfortunately, I was right, as we've known since before the new hardware was released nearly a year and a half ago.  The Xbox One and PS4 are capable of playing exactly zero binaries built for their predecessors.

But just because we saw it coming doesn't make it any less painful.  Once our older machines die, how will we play those games we love?

Java-Style Properties Files in C++

(Originally posted Feb 28, 2008)

Need to handle Java-style properties files in C++? I've decided to post some of my own personal library of code on this blog. This is one of those occasionally useful things.

propertyutil.h
propertyutil.cpp

If you fix any bugs, extend the code or anything else, send back your changes if you don't mind. ;)

Core Plot Tutorials

Handy references for Core Plot, which I use for making charts in iOS apps.

• Core Plot Tutorial
• Pie Chart at Ray Wenderlich
• Comparing charting/graphing libraries
• Core Plot itself on github

Surge of Video Game Nostalgia

When I was a wee lad in the mid 1980s, Compute! magazine would run ads like this.  Box cover art is what sold it back then, I'm telling you.

My Apps

(More to say, more coming..)

Ideas Are Cheap

Ideas Are Cheap, Execution is Worth Millions

This has been on my mind lately regarding mobile app ideas.  Or as Thomas Edison most famously put it,

"Genius is one percent inspiration, ninety-nine percent perspiration."  

These days it seems like 99.999% perspiration.

Cuervo

“¡Puta!”—whore—her brother called, laughing, from the incandescent doorway against the sunset as his house in Taxco, Mexico came into her view.  Miriam and Juan had come from Huejutla in a bus called Mi Burro, a hard trip because she was thirty-five weeks and looking way past due. 

Days later, in the square, the baby kicked explosively, dropping her to her knees with a rush of warm water down her legs.  The child was born with articulated tar-colored bony tumors on its back and stank like old fish in the May sun before the rains start.  An inhuman smell.  “¡Dios mío!” the midwife said, crossing herself, “a very bad omen.”  That was late All Saints Day or early Day of the Dead.  They claimed the holier of the two days for luck.

“I kill it,” said her brother.  “It's a demon or changeling.  Or we go to the witchdoctor.  What a curse, this jorobado, this—hunchback.” 

Miriam took the child while the others slept, hobbling off, bleeding some, and holed up in a barn they'd seen on the road in.  Juan found her there. 

“We keep the child,” she said. 

“We can't even take care of ourselves.  Leave it, amor, we return to Huejutla.” 

She shook her head.  “We keep him.” 

He covered his face, then ran his hands through his hair.  “Está bien.” 

“He isn't yours,” she said, now crying. 

“I know.” 

“He's a monster's child.  I don't betray you, not willingly.” 

“'tá bien.” 

“I don't.  I want you to know, but we must keep the baby.” 

He was silent.  “What shall we call it?” 

“Jesús.” 

“No.  Not for this one, it is blasphemy.” 

“He needs a lucky name.” 

Those years they traveled the volcanic sierra, hiding the child, finally settling in Popocatépetl's skirts in a poor pueblo of flower fields at Zaragosa's edge called Omexochitla.  They worked hard, earning fine farmland for marigolds, a field alongside an aqueduct. 

One afternoon, the priest found the boy in the chapel bell tower.  “A climber, ¿eh?  What's on your shoulders, under the burlap?” 

The boy stepped back, almost falling.

The priest held out his hands, palms forward.  “No importa.  What's your name, boy?”

When Jesús was sixteen, well-dressed men came to speak with Juan.  The three pulled up their marigolds and planted poppies.  Soon, they weren't so poor, but the pueblo sweat fear.  Juan saw this too and he burned the poppies in their fields.   One night the well-dressed men returned to burn up Miriam and Juan in their beds.  

Now, in these troubled times, all the pueblo's fields grow poppies. 

*   *   *

The nearby city of Zaragosa reels in the cartel's coming, with crooked high-rise casinos and murders moving down from the north, in from Veracruz, up from Oaxaca.  In the churchyard, cartel capo Pablo Vargas talks with other men under a bright waxing moon.  

A silent hulk in a hooded duster watches, perched above the highest bells of the massive Zaragosa Cathedral on the saffron-tiled cupola.  Vargas swings the rear car door open and the jorobado atop the cathedral shakes, violently unfolds immense iridescent black wings, and leaps after him into the night air. 

The black Mercedes speeds down the Heroes of the Cinco de Mayo.  The driver looks up again, but sees nothing now. 

“Pull over at the Oxxo,” Vargas says.  He runs in to the convenience store while the driver scans the sky. Vargas returns and they pull out onto the boulevard.  

 “There it is!  You see that bird?  It's huge. ”

“What bird?  A raven or something?” 

It flashes again at the top edge of the windshield, a black silhouette against the indigo sky, this time bigger than a man.  

“¿Que diablos?”  What the hell?  The driver accelerates.  The bird drops something featureless and elliptical—“¿Que..?” 

The windshield and steering wheel splinter from the flying manhole cover.  It shatters his arm.  He pushes it off in spite of the pain, but bone pierces the skin and he passes out with a heavy foot on the pedal.  Vargas leaps forward for the remnant of the wheel, yanking it hard to avoid oncoming cars.  A street shrine falling from above impales the roof head-first and the Virgin's steel halo slices Vargas' flank.  The weaving Mercedes slams through the guardrail and plunges into the Anáhuac River. 

In Omexochitla, another cartel is moving in.  At the next sunset, armed men spray fields with kerosene as if it were insecticide.  Finally, one plucks a wilted poppy, applies a glowing cigarette tip to its petal and tosses the flaming flower into the field. 

Vargas limps from a warehouse by the river and hails a taxi.  He studies the driver’s hat, a fur ushanka outlined in darkness.   The taxi pulls onto the highway. 

“Kavork, is that you?” 

In a Slavic accent came, “A philosophical question.  I often ask it to myself.” 

“You gonna kill me?” 

Nothing. 

“Don't piss on my body like you did on Lopez.” 

Kavork laughs.  “A sublime moment.  I thank you for the reminder.”  The doors clicked broken-off locks.   Vargas shakes his door and withdraws a gun, pointing into the back of the driver’s head.  

“A hundred thirty kilometers per hour, my friend.  You want another accident already?” 

“That was you?  Why do you work for Los Equis?” 

In one fluid motion, Kavork grabs the gun, bounds over the driver's seat and pummels Vargas with a riveted steely hand, hammering like a steam piston.  A metallic bladder at the wrist, like a birthday balloon, inflates and deflates with each blow.  The car careens on.  Kavork hammers Vargas even as the taxi crumples into and under an oncoming eighteen-wheeler. 

*   *   *

Jesús returned to an Omexochitla alight in the dark with flames.  From atop the aqueduct he landed below to watch.  A young woman in black approached the hunchback. 

“Who can save us?” she asked, startling him.  His wings flared and she gasped at his silhouette, back against the flaming fields, wings spread.  “¿Miguel? ¿Gabriel?”  She crossed herself. 

“Jesús,” he said. 

She gasped again.  “But not with wings—” 

And then the rains burst, running down her face and over the course of the night, quenching the fires in the fields.