Random Fail


One of my common software interview questions involves the creation of a game board. Part of the problem includes the generation of random numbers. If the candidate is writing in C/C++, the typical code I see looks something like this:

srand(seed); // one time seeding of generator
// later on ...
r = (rand() % 6) + 1; // throw the dice

Plenty of people have discussed the drawbacks of rand(), but the interview problem is not focused on the random number generation itself, so I consider the code above reasonable. Recently I had a candidate use JavaScript as their language of choice. The candidate wrote:

r = Math.Floor((Math.Random() * 5) + 1); // [1...6] ?

I’m not a JavaScript expert, but I noticed a couple things right away. First, there appears to be no way to seed the generator, so it’s not reproducible. Second, Math.Random() returns a float in the range [0.0 to 1.0). In other words, the code above will never return the number 6 because Random() never generates a 1.0! Even if Random() returned values in the range [0.0 to 1.0] there would still be a big problem. Random() is a uniform generator, so it only returns precisely 1.0 on very rare occasions. Hence the distribution of numbers will look something like this, which is clearly not random:

Takeaway: getting random numbers correct is a non-trivial problem. A lot of information available on the Internet about generating random numbers is plan wrong. Beware. Test your generators to ensure that they are both random and uniform. If I was writing C++ code today that needed to throw a d6, it would look like this:

#include <random>
std::mt19937 mt(seed); // generation engine
std::uniform_int_distribution<int> ud(1,6); // distribution engine
// later on ...
r = ud(mt); // [1...6], uniformly distributed

For a hilarious 30 min excursion into the pitfalls of C/C++ rand(), see Stephan’s talk: rand Considered Harmful. You’ll never use rand() again.

Posted in C++, Computers and Internet, Game Programming | Leave a comment

A galaxy var, var away


My current project has me writing C# scripts in Unity. Cool. I haven’t written C# for more than a decade. Today I was reviewing code, and noticed this line:

foreach (var child in Children)

Nothing too exciting. Readable. Easy to understand. But as I took a second look, I realized I didn’t truly know what var is all about. Is it defining a variable? What’s the type of child? Could var be replaced with ChildType? What’s best practice? Should I be using var?

Var was introduced in C# v3.0 circa 2007. It turns out it’s the equivalent to auto in C++, which I wrote about not long ago. Var allows the compiler to determine the type automatically.

So, var defines a variable. The type of var is the type that the compiler deduces. Var could be replaced with the actual type, but best practice is to use var whenever you can, just like auto. I’ll be using it regularly from now on.

Var out.

Posted in CSharp, Game Programming | Leave a comment

Enter Swift


I’ve always been a proponent of ease of development. All things being equal, when I have a choice I will pick the easier language/tool/environment.

But all things are never equal. Developers have to consider development costs and their personal skillsets and platform install base and hundreds of other variables in their decision to build a product on a particular platform using a particular set of tools.

What wins? Install base.

Example #1: Playstation. Writing games for the original PlayStation, PlayStation 2 — and even PlayStation 3 — is incredibly challenging. The hardware is complex. The documentation is abysmal. C/C++ is de rigueur. But the PlayStation line of game consoles has sold hundreds of millions of units, and developers have risen to the challenge of making PS games, because that huge install base represents the chance of making a fortune.

Example #2: iPhone. Creating apps for iOS is no easy task. Objective-C is an obscure language that is only popular due to the runaway success of iPhones and iPods.

That’s why I was surprised at the recent announcement of Swift. Apple has no business need to create better tools or languages. Developers are not blocked creating iOS apps. Yet Apple continues to improve the Xcode development environment and now introduces a new programming language that should appeal to many developers. Fascinating.

iOS install base. Check.

Apple winning the hearts and minds of developers. Check.

Posted in Computers and Internet, Game Programming | Leave a comment

Git’n Bashed and Objective, See?


At Microsoft, the tools for my daily work included things like C++, PowerShell, and Visual Studio. I also used many internal tools with names like Source Depot and Razzle. And naturally I used the Windows platform.

It’s both a pleasure and challenge to be working with a completely new set of tools as a developer at HBO. Just in the past week alone, I’ve:

  • Programmed in Objective-C
  • Used the Xcode development environment
  • Written bash scripts
  • Managed content with git
  • Issued pull requests on GitHub
  • Configured builds on Jenkins
  • Debugged ARM code on iPad
  • Browsed with Safari and Chrome

About the only tool that is consistent between my current and previous jobs is Outlook.

It’s strange to be a novice at so many things. It’s like going back to school. My productivity is low (though growing), but my satisfaction at learning new things is immense.

There’s a lesson to be learned here.

 

Posted in C++, Computers and Internet | 1 Comment

User Experience Revisited


I started a new job this week, working at HBO. After nearly 13 years at a software company, it’s invigorating to be at a content company. The challenges are completely different. The acronyms are new. The focus is on user experience.

One of my favorite books is a collection of essays by Joel Spolsky called User Interface Design for Programmers. Although some of the examples are dated, the key concepts are still relevant.

In preparation for some work my team will be doing on UI, I’ve been reading the online version of Joel’s book. I was struck by his axiom of all UI design: A user interface is well-designed when the program behaves exactly how the user thought it would.

It reminded me of my personal pet peeve of UI design — keyboard entry. I avoid the mouse whenever I can, because (like many software engineers) I’m more efficient when my hands stay on the keyboard. Now consider most websites. They’re often designed for the mouse as the primary form of input, even for things that require the keyboard, such as user names or address forms.

When you go to a banking or credit card site, what’s the first thing you do? You enter your user name. Yet how many sites default the keyboard focus to the user name field? The number is far short of 100%.

Takeaway: when you’re designing UI, consider all your users, and behave the way the user expects.

The challenge with Joel’s axiom of UI design is that all your users are different. One good solution that I learned at Microsoft: create a small suite of user profiles and test against those profiles. For example, you might have a profile that describes a student user, a pro user, and a business user.

And if you’re developing a new website, set the initial keyboard focus to the user name field.

Posted in Computers and Internet, UI | Tagged | Leave a comment

Fun with Powers of Two


Recently I needed to know the maximum number of decimal digits in a 64-bit unsigned integer. I put together this handy table as a reference.

Value Decimal Decimal Digits
2^8 256 3
2^16 65,536 5
2^32 4,294,967,296 10
2^64 1.8 x 10^19 20
2^128 3.4 x 10^38 39
2^256 1.16 x 10^77 78

As the exponent doubles, the number of digits tends to double. If you remember than a 32-bit number has at most ten decimal digits, then it’s easy to remember that a 64-bit number has at most twenty decimal digits, and so on.

Here’s another useful trick involving powers of 1024.

n Power of 2 Decimal Think Decimal Digits
1 2^(10n) 1024 1 thousand (10^3) 3+1
2 2^20 1,048,576 1 million (10^6) 6+1
3 2^30 1,073,741,824 1 billion (10^9) 9+1
4 2^40 1.1 x 10^12 10^12 12+1
5 2^50 1.1 x 10^15 10^15 15+1
6 2^60 1.2 x 10^18 10^18 18+1
7 2^70 1.2 x 10^21 10^21 21+1
8 2^80 1.2 x 10^24 10^24 24+1
9 2^90 1.2 x 10^27 10^27 27+1
10 2^100 1.3 x 10^30 10^30 30+1
n 2^(10n) ~10^(3n) ~10^(3n) (3n)+1

Given a number that’s a power of 1024, i.e. 2^(10 x n), where n is positive integer, the maximum number of decimal digits in the equivalent value is (3 x n) + 1. For instance, for 2^20 = 2^(10 x 2) = 1,048,576, the maximum number of decimal digits is 7, because n is 2 and (3 x 2) + 1. This is true for all values of n through 97 (2^970), so this trick will be handy for a few years to come :)

Using this formula, here’s how you would quickly approximate the maximum number of decimal digits required for a 64-bit integer. Round up 64 to the nearest number divisible by 10 (70). Divide by 10 (7). Multiply by three and add 1 (7 x 3 + 1) = 22. Nice!

Posted in C++, Computers and Internet | Leave a comment

Auto Pilot


I was recently working on a small programming project, and decided to fully embrace the new C++11 keyword auto. Auto allows the compiler to deduce types. The canonical example is:

// before C++11
for( vector::const_iterator i = begin(c); i != end(c); ++i )

// with C++11
for( auto i = begin(c); i != end(c); ++i )

The compiler knows that i is an iterator based on the return type of begin(). The compiler can examine the usage of i to determine that i should either be a const or non_const iterator. The example shows two important things: 1) how much easier it is to read, and 2) how the programmer no longer has to worry about the type of c changing. If the type of c changes to a different container, or even a C-style array, the code will continue to compile correctly.

Here are a few observations from my initial experience using auto:

  • I used auto somewhat more than expected. Out of 737 lines of code, auto appears on 58 lines (8%)
  • Of those 58 lines:
    • 17 instances were for loops (29%) similar to what I showed above
for( auto i = 0u; i < len; ++i ) // common use
    • The 41 remaining instances were variable declarations (71%). Here are some examples.
// casts
auto c = static_cast<char>( tolower( letter ) );
auto p = reinterpret_cast<unsigned int*>( pData );

// typical assignments
auto len = s.length();
auto i = lower_bound( begin(c), end(c), toFind );
auto isFound = ( i != end(c) );
const auto& item = *i;
auto result = QueryPerformanceCounter( &li );
auto seconds = millisecs / 1000.0;

// typical copy constructors
auto nextItem( item );

One of my concerns was that I would miss seeing the obvious “type-ness” of variables, but that fear was mostly unfounded. The type is almost always immediately obvious. It’s certainly obvious with casts. It’s obvious when the variable name was appropriately named, such as isFound (boolean!) and len (integer!). In fact, there was only one place where I could have used auto that I chose not to — a function that established some connections between items.

void CrossConnectNodes( size_t i, size_t j )
{
    Node* pNodeI = nodeList[i];
    Node* pNodeJ = nodeList[j];

    pNodeI->CrossConnect( pNodeJ );
    pNodeJ->CrossConnect( pNodeI );
}

The Node declarations could be auto, but Visual Studio Intellisense (VS 2012) doesn’t (yet) allow you to jump to the definition of the Node class if you use the auto keyword. I suspect Microsoft will address this in the future.

I’m a fan and will be using auto on future projects. Once Visual Studio Intellisense fully supports auto, then I can completely endorse auto everywhere.

For even more recommendations on why auto is a good idea (efficiency, guaranteed initialization, and correctness), see Herb’s GotW #93.

Posted in C++ | 4 Comments