Sunday, October 24, 2010

Efficient enumeration of all integers with a given pop count

Population count is the number of '1' bits in the binary representation of an integer.

The basic trick we employ is to get the next higher number with the same number of 1-bits, which we borrow from the Hacker's Delight (whole book). Below is a Java implementation of all 4 version of the snoob function.

public static int snoob1(int x) {
int r = x + (x & -x);
return r | ((x ^ r) >>> (2 + Integer.numberOfTrailingZeros(x)));

public static int snoob2(int x) {
int s = x & -x, r = x + s;
return r | ((x ^ r) >>> (33 - Integer.numberOfLeadingZeros(s)));

public static int snoob3(int x) {
int r = x + (x & -x);
return r | ((1 << (Integer.bitCount(x ^ r) - 2)) - 1);

public static int snoob4(int x) {
int s = x & -x, r = x + s;
return r | (((x ^ r) >> 2) / s);
We utlize this formula to implement the method below, where the width parameter is added for convenience.
public static void printAllIntegersOfWidthAndPop(int w, int n) {
if (n <= 0 || n > w || w > 32) return;
int x = (1 << n) - 1, g = x << (w - n), c = 0;
while (true) {
String s = Integer.toBinaryString(x);
while(s.length() < w) s = "0" + s;
System.out.println(++c + "\t" + s);
if (x == g) break;
else x = snoob*(x);
It is easy to figure out there will be Choose(w, n) such numbers. We know where the sequence starts and since we also know where it stops, we don't need to compute this number.

If you'd like to learn how to find the number of leading/trailing zeros or the pop count or learn about more cool bit twiddling hacks you can consult the book above (which the java.lang.Integer implementation of these methods is based on) or this magnificent web page.

Saturday, July 17, 2010

Generating combinations in lexicographical order using Java

Below is a Java port of the algorithm by James McCaffrey as presented in the MSDN article Generating the mth Lexicographical Element of a Mathematical Combination.

Please do take into consideration that this implementation only uses int as Java does not allow array indexing with long. This means that the valid input range is more restricted. Watch out for overflows!

* Based on the Combinadic Algorithm explained by James McCaffrey
* in the MSDN article titled: "Generating the mth Lexicographical
* Element of a Mathematical Combination"
* <>
* @author Ahmed Abdelkader
* Licensed under Creative Commons Attribution 3.0
* <>
public class Combinations {
/** returns the mth lexicographic element of combination C(n,k) **/
public static int[] element(int n, int k, int m) {
int[] ans = new int[k];

int a = n;
int b = k;
int x = (choose(n, k) - 1) - m; // x is the "dual" of m

for (int i = 0; i < k; ++i) {
a = largestV(a, b, x); // largest value v, where v < a and vCb < x
x = x - choose(a, b);
b = b - 1;
ans[i] = (n - 1) - a;

return ans;

/** returns the largest value v where v < a and Choose(v,b) <= x **/
public static int largestV(int a, int b, int x) {
int v = a - 1;

while (choose(v, b) > x)

return v;

/** returns nCk - watch out for overflows **/
public static int choose(int n, int k) {
if (n < 0 || k < 0)
return -1;
if (n < k)
return 0;
if (n == k || k == 0)
return 1;

int delta, iMax;

if (k < n - k) {
delta = n - k;
iMax = k;
} else {
delta = k;
iMax = n - k;

int ans = delta + 1;

for (int i = 2; i <= iMax; ++i) {
ans = (ans * (delta + i)) / i;

return ans;
The code below produced the output that follows:
public static void main(String[] args) {
int n = 5, k = 3;
int total = choose(n, k);
for(int i = 0; i < total; i ++) {
for(int x : element(n, k, i))
System.out.print(x + " ");

0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

Monday, June 21, 2010

G/G/1 Queue Model Simulation in Java

In this post, we present an object-oriented design and implementation of an event-driven G/G/1 queue model simulation using Java. The lecture notes on Computer System Analysis by Raj Jain were very helpful and are highly recommended. In particular, we would like to reference the introductory lectures on Simulation Modeling and Queueing Theory.

Please note that this implementation is provided as a guide/starting point and is not, by any means, complete. We preferred a simple design while keeping in mind where you may wish to extend it.

Update: Download the Eclipse project here.

An event-driven simulation operates by generating and processing events through time. For our queue model, we have two types of events: arrivals and departures or service completion. It is also necessary to determine which events should happen first.

public class Event implements Comparable<Event> {
protected double time;
protected int code;


public int compareTo(Event e) {
return, e.time);
While the design will not make any assumptions about the interarrival or service time distributions, we still need a suitable way to represent them and a couple of concrete implementations for testing.
public abstract class Distribution {
public abstract double generateRV();

public class UniformDistribution extends Distribution {
double a, b;


public double generateRV() {
return a + rand.nextDouble() * (b - a);

public class ExponentialDistribution extends Distribution {
double lambda;


// Generating exponential variates.
public double generateRV() {
return -1/lambda * Math.log(rand.nextDouble());

public class NormalDistribution extends Distribution {
double mu, segma;


public double generateRV() {
return mu + rand.nextGaussian() * segma;
Now, we should be ready to implement the queue class. We preferred to keep the queue simple by moving data collection into a separate arbitrary observer.
* @author Ahmed Abdelkader
* Licensed under Creative Commons Attribution 3.0
* <>
public class GG1Q {
protected Distribution arrivalDistribution;
protected Distribution serviceDistribution;
protected double t;
protected PriorityQueue<Event> eventQueue = new PriorityQueue<Event>();
protected int customers;
protected QueueObserver observer;


public void run(double duration) {
eventQueue.add(new Event(t + arrivalDistribution.generateRV(), Event.ARRIVAL));
while(t < duration) {
Event e = eventQueue.poll();
t = e.time;
switch(e.code) {
case Event.ARRIVAL:
eventQueue.add(new Event(t + arrivalDistribution.generateRV(), Event.ARRIVAL));
if(customers == 1)
eventQueue.add(new Event(t + serviceDistribution.generateRV(), Event.SERVICE));
case Event.SERVICE:
if(customers > 0)
eventQueue.add(new Event(t + serviceDistribution.generateRV(), Event.SERVICE));
if(observer != null)
observer.stateChanged(this, e);

We define the observer interface and implement two sample observers: one for estimating the queue length PDF and the other for the waiting time CDF. A composite observer allows more than one observer to collect data of a single run.
public interface QueueObserver {
void stateChanged(GG1Q q, Event e);
void printStats();

public class CompositeQueueObserver implements QueueObserver {
protected ArrayList<QueueObserver> observers = new ArrayList<QueueObserver>();

public void addObserver(QueueObserver observer) {

public void stateChanged(GG1Q q, Event e) {
for(QueueObserver observer : observers)
observer.stateChanged(q, e);

public void printStats() {
for(QueueObserver observer : observers)

public class QueueLengthQueueObserver implements QueueObserver {
protected TreeMap<Integer, Integer> lengthFrequencies = new TreeMap<Integer, Integer>();
protected int total;

public void stateChanged(GG1Q q, Event e) {
if(e.getCode() != Event.ARRIVAL) return;
Integer length = lengthFrequencies.get(q.getLength());
if(length == null) length = 0;
lengthFrequencies.put(q.getLength(), length + 1);

public void printStats() {
for(int length : lengthFrequencies.keySet())
System.out.println(length + "\t" + 1.0*lengthFrequencies.get(length)/total);

public class WaitingTimeQueueObserver implements QueueObserver {
protected ArrayList<Double> waitingTimes = new ArrayList<Double>();
protected int arrivalIndex, serviceIndex;
protected HashMap<Integer, Double> arrivalTimes = new HashMap<Integer, Double>();

public void stateChanged(GG1Q q, Event e) {
switch(e.getCode()) {
case Event.ARRIVAL:
arrivalTimes.put(arrivalIndex++, e.getTime());
case Event.SERVICE:
waitingTimes.add(e.getTime() - arrivalTimes.get(serviceIndex++));

public void printStats() {
if(waitingTimes.size() == 0) return;
double acc = 0;
for(int i = 1, j = 0; i <= 10; i++) {
while(acc < i/10.0 && j < waitingTimes.size()) {
acc += 1.0/waitingTimes.size();
System.out.println(waitingTimes.get(j-1) + "\t" + i/10.0);
The following test program produced the output below:
public class Main {
public static void main(String[] args) {
GG1Q q = new GG1Q(new ExponentialDistribution(100.0/3600), new UniformDistribution(1, 10));
QueueObserver observer = new QueueLengthQueueObserver();

Queue length PDF:
1 0.47058823529411764
2 0.23529411764705882
3 0.058823529411764705
4 0.058823529411764705
5 0.11764705882352941
6 0.058823529411764705

Wednesday, April 28, 2010

GeoTraffic & GeoKeywords: Google Analytics custom reports for fun and profit

I've been using Google Analytics for 2 years to track the traffic on this blog. It's really interesting to see which posts receive more attention and what traffic sources and keywords generated how much traffic on any one day. This is specially important to me since the majority of the traffic to my blog comes from search engines a.k.a. google (organic).

However, when you really look into the traffic tracking thing, you'll find that the default reports which come out-of-the-box with Google Analytics don't help answer certain questions. This is more evident on a modest personal blog than it would be for a hot website like stackoverflow, for example. For your blog, you'd actually want to know who visited the blog. I mean, you'd like to push the limits of anonymity.

The main missing information in the default Analytics reports have to do with location. While you're able to know how many visits were generated from each country in addition to some useful statistics like the average time on website and pages/visit, there is still something missing.

I wanted to be able to answer these 2 critical questios:
1) Where does the direct traffic come from? and which pages are requested?
2) Who is searching for what?

Thanks to the Google Analytics team, we are now able to create our own custome reports to project the data whichever way we want. Once I found out, I created 2 custom reports to answer my 2 questions.

For the first question, the GeoTraffic report is the answer. The main dimension would be the Source. Next, we drill down towards: Country/Territory -> City -> Page. The main metric is Pageviews, then Pages/Visit and Avg. time on page.

For the second question, the GeoKeywords report is the answer. This time, the main dimension is the Country/Territory then we drill down to: Keyword -> City. For this report, I preferred the main metric to be Avg. time on page then Pages/Visit and Unique Visitors.

Now, I'm able to answer my questions, and I've been mainly interested in the first one: where the direct traffic comes from. The reason for that is that I've been waiting for something. I may talk about that later. I guess you're going to find it useful ;)

Friday, February 5, 2010

Introducing Google App Engine - All in One

Google App Engine lets you run your web applications on Google's infrastructure e.g. GFS and BigTable. App Engine applications are easy to build, easy to maintain, and easy to scale as your traffic and data storage needs grow. With App Engine, there are no servers to maintain: You just upload your application, and it's ready to serve your users... more docs. An alternative introduction is available on Wikipedia.

I compiled a list of videos that should get your engines up and running on this exciting web framework:

Campfire One - Introducing Google App Engine:

  1. Pt. 1 (9:10)
  2. Pt. 2 (12:34)
  3. Pt. 3 (13:19)
  4. Pt. 4 (7:44)
  5. Pt. 5 (5:55)
  6. Pt. 6 (8:04)
  1. Google App Engine - Early Look at Java Language Support (7:38)
  2. Overview of Google Web Toolkit (4:10)
  3. Getting Started with App Engine in Eclipse (5:07)
Google I/O 2008:
  1. Google I/O 2008 - Working with Google App Engine Models (1:00:32)
  2. Google I/O 2008 - Building Quality Apps on App Engine (48:43)
  3. Google I/O 2008 - Engaging User Experiences with App Engine (45:32)
  4. Google I/O 2008 - Python, Django, and App Engine (57:09)
Google I/O 2009:
  1. Google I/O 2009 - A Preview of Google Web Toolkit 2.0 (1:00:53)
  2. Google I/O 2009 - App Engine: Now Serving Java (55:00)
  3. Google I/O 2009 - Groovy and Grails in App Engine (1:00:14)
  4. Google I/O 2009 - Java Persistence & App Engine Datastore (1:09:32)
  5. Google I/O 2009 - ThoughtWorks on App Engine for Java (1:04:18)
Check out the project homepage and the developer's guide for more and subscribe to the Google App Engine Blog.

Thursday, January 28, 2010

Auto-formatting phone number UITextField on the iPhone

In this post, we'll use our PhoneNumberFormatter to implement an auto-formatting phone number text field in an attempt to mimic the behavior of iPhone's native apps, like Phone and Contacts.

So, let's call the text field in question myTextField. We start by calling addTarget on the text field to make it call the autoFormatTextField method in our view controller whenever it gets updated, either by the user or some other piece of code. If your view is ready, you should declare the handler as an IBAction and bind through IB. The method would then update the contents of the text fields to the formatted string returned by the formatter. If we do it that way, we'll also need to use a semaphore to prevent the method from being called endlessly.

The implementation outline would be:

// declarations

UITextField *myTextField;
int myTextFieldSemaphore;
PhoneNumberFormatter *myPhoneNumberFormatter;
NSString *myLocale; //@"us"

// init semaphore
myTextFieldSemaphore = 0;

// bind events programatically, skip when using IB.
[myTextField addTarget:self

// handle events
- (void)autoFormatTextField:(id)sender {
if(myTextFieldSemaphore) return;
myTextFieldSemaphore = 1;
myTextField.text = [phoneNumberFormatter format:myTextField.text withLocale:myLocale];
myTextFieldSemaphore = 0;
Update: As pointed out in the comments, for newer SDKs you may need to bind to UIControlEventEditingChanged. Thanks for your feedback!
//bind events

[myTextField addTarget:self

Saturday, January 23, 2010

On the Fairness of Reservoir Sampling

Reservoir sampling is a family of randomized algorithms for randomly choosing K samples from a list of S items, where S is either a very large or unknown number.

A very elegant algorithm titled Algorithm R by Alan G. Waterman, is summarized as follows:

Fill up the 'reservoir' with the first k items from S
For every item S[j] where j > K
Choose an integer r between 0 and j
If r < K then replace element r in the reservoir with S[j]
One very interesting discussion with a friend led me to this problem. In this post we are going to prove that at all times, the probability of each processed item to be in the reservoir is the same for all items. In other words, after each iteration and when the algorithms terminates, all processed items will have the same probability of being included.

To initialize the reservoir, the first K items are included. At this point of time, each item is included by a probability of 1.

Later on, to process item number A, where A > K, we include it by a probability of K / A. (1)

For any of the K items in the reservoir, it will remain in the reservoir after item A is processed only in 2 cases:
1) Item A does not get included. This has a probability of ( A - K ) / A = 1 - K / A
2) Item A gets included but it does not replace the item in question, i.e. it can replace any of the other ( K - 1 ) items in the reservoir. This has a probability of ( K / A ) * [ ( K - 1 ) / K ] = ( K - 1 ) / A

So each of the K items remains in the reservoir by a probability of 1 - K / A + ( K - 1 ) / A = 1 - 1 / A

This is the same as the probability of A not replacing our item. Since the probability of A replacing any one item is 1 / A. The complement is directly found as 1 - 1 / A

Now, let P( A, B ) be the probability of item A still being included in the reservoir after item B is processed, where B >= A. Without loss of generality, we may assume that B is the next item to be processed.

For item A to remain in the reservoir after item B is processed, item A must have been included up to the point where B is to be processed. Equivalently, item A was still included after item (B - 1) was processed. In addition, for A to remain in the reservoir B must not replace it

From the discussion above, it follows that:
P( A, B ) = [ 1 - 1 / B ] * P( A, B - 1 )

Which can be expanded as:
P( A, B ) = [ 1 - 1 / B ] * [ 1 - 1 / ( B - 1 ) ] * ... * [ 1 - 1 / ( A + 2 ) ] * [ 1 - 1 / ( A + 1 ) ] * p( A, A )

But from (1):
P( A, A ) = K / A

As a result:
P( A, B ) = [ 1 - 1 / B ] * [ 1 - 1 / ( B - 1 ) ] * ... * [ 1 - 1 / ( A + 2 ) ] * [ 1 - 1 / ( A + 1 ) ] * K / A

[ 1 - 1 / ( A + 1 ) ] = A / ( A + 1 )

P( A, B ) = [ 1 - 1 / B ] * [ 1 - 1 / ( B - 1 ) ] * ... * [ 1 - 1 / ( A + 2 ) ] * [ A / ( A + 1 ) ] * K / A
P( A, B ) = [ 1 - 1 / B ] * [ 1 - 1 / ( B - 1 ) ] * ... * [ 1 - 1 / ( A + 2 ) ] * K / ( A + 1 )

P( A, B ) = [ 1 - 1 / B ] * [ 1 - 1 / ( B - 1 ) ] * ... * K / ( A + 2 )

We can see that this recurrence reduces to:
P( A, B ) = K / B

This is the same as the probability of item B being included. In addition, P( A, B ) is not a function of A, it only depends on B, which is the number of elements processed so far.

This means that for the next item to be processed it will have the same probability of being included as all the items that were processed before it. By maintaining this property, when the algorithm terminates, all items will have the same probability of being included in the reservoir, regardless of the size of the list.

Friday, January 22, 2010

Locale-aware phone number formatting on the iPhone

iPhone developers often find themselves trying to stick to the standards set by Apple. Most of the time, doing so is facilitated by the SDK and the results are better. Sometimes though, it's not easy at all, mainly because some APIs are not open.

One example is phone number formatting. The Contacts application utilizes an auto-formatting UITextField for phone number entry. Many business applications would make use of such functionality but it's not provided by the current SDK.

I've been through that and was not happy about the task. After procrastinating for a while, I thought of a solution and later on, I actually implemented it, and it worked well for me. I wished I could make it into the sought after NSPhoneNumberFormatter, but I was done with the task. I thought I should share it with fellow iPhone developers. I hope many will be able to use it right away as-is, and it would be great if someone could finish the job and make the formatter.

I acquired the predefined localized phone formats from the UIPhoneFormats.plist. I was mainly interested in the us locale, but I kept the implementation generic. The main idea is to build some sort of a finite state machine (FSM) for the phone format and use it to process the input string. The FSM will both validate and add formatting characters to the string as needed. If the whole input could be processed successfully, then it is a valid format and the output is returned.

The problem that I didn't solve yet, is when the string can be matched to more than one format. I had to manually sort the formats from the most restrictive to the least restrictive, so the one that comes first is always selected. This hack was okay for US formats, but there was nothing I could do with the last 3 UK formats since, to me, they are essentially the same. I guess this can be worked around somehow.

I'll post the code here, and will try to add more comments later. Please feel free to add your comments or ask for clarifications.

Update 02/14/2010: I'm so glad to have habermann24 join in and create his phoney ruby lib. If your Ruby/Rails application deals with phone numbers, you got to check it out!

Update 09/08/2010: Check out libphonenumber: Google's common Java, C++ and Javascript library for parsing, formatting, storing and validating international phone numbers. The Java version is optimized for running on smartphones. You'll need to look for the Update++, check out the comment below by +SpoofApp.

Update 08/15/2011: Updates on libphonenumber: New development of the library will be presented in the 35th Internationalization and Unicode Conference in a session titled: libphonenumber - The Swiss Army Knife of International Telephone Number Handling. See session description for details.

Update 02/06/2015: libphonenumber on Github by Google Internationalization (i18n).


//  Created by Ahmed Abdelkader on 1/22/10.

// This work is licensed under a Creative Commons Attribution 3.0 License.

#import <Foundation/Foundation.h>

@interface PhoneNumberFormatter : NSObject {
//stores predefiend formats for each locale
NSDictionary *predefinedFormats;

Loads predefined formats for each locale.

The formats should be sorted so as more restrictive formats should come first.

This is necessary as the formatting code processes the formats in order and
selects the first one that matches the whole input string.
- (id)init;

Attemps to format the phone number to the specified locale.
- (NSString *)format:(NSString *)phoneNumber withLocale:(NSString *)locale;

Strips the input string from characters added by the formatter.
Namely, it removes any character that couldn't have been entered by the user.
- (NSString *)strip:(NSString *)phoneNumber;

Returns true if the character comes from a phone pad.
- (BOOL)canBeInputByPhonePad:(char)c;


//  Created by Ahmed Abdelkader on 1/22/10.

// This work is licensed under a Creative Commons Attribution 3.0 License.

#import "PhoneNumberFormatter.h"

@implementation PhoneNumberFormatter

- (id)init {
NSArray *usPhoneFormats = [NSArray arrayWithObjects:
@"+1 (###) ###-####",
@"1 (###) ###-####",
@"011 $",
@"(###) ###-####", nil];

NSArray *ukPhoneFormats = [NSArray arrayWithObjects:
@"+44 ##########",
@"00 $",
@"0### - ### ####",
@"0## - #### ####",
@"0#### - ######", nil];

NSArray *jpPhoneFormats = [NSArray arrayWithObjects:
@"+81 ############",
@"001 $",
@"(0#) #######",
@"(0#) #### ####", nil];

predefinedFormats = [[NSDictionary alloc] initWithObjectsAndKeys:
usPhoneFormats, @"us",
ukPhoneFormats, @"uk",
jpPhoneFormats, @"jp",
return self;

- (NSString *)format:(NSString *)phoneNumber withLocale:(NSString *)locale {
NSArray *localeFormats = [predefinedFormats objectForKey:locale];
if(localeFormats == nil) return phoneNumber;
NSString *input = [self strip:phoneNumber];
for(NSString *phoneFormat in localeFormats) {
int i = 0;
NSMutableString *temp = [[[NSMutableString alloc] init] autorelease];
for(int p = 0; temp != nil && i < [input length] && p < [phoneFormat length]; p++) {
char c = [phoneFormat characterAtIndex:p];
BOOL required = [self canBeInputByPhonePad:c];
char next = [input characterAtIndex:i];
switch(c) {
case '$':
[temp appendFormat:@"%c", next]; i++;
case '#':
if(next < '0' || next > '9') {
temp = nil;
[temp appendFormat:@"%c", next]; i++;
if(required) {
if(next != c) {
temp = nil;
[temp appendFormat:@"%c", next]; i++;
} else {
[temp appendFormat:@"%c", c];
if(next == c) i++;
if(i == [input length]) {
return temp;
return input;

- (NSString *)strip:(NSString *)phoneNumber {
NSMutableString *res = [[[NSMutableString alloc] init] autorelease];
for(int i = 0; i < [phoneNumber length]; i++) {
char next = [phoneNumber characterAtIndex:i];
if([self canBeInputByPhonePad:next])
[res appendFormat:@"%c", next];
return res;

- (BOOL)canBeInputByPhonePad:(char)c {
if(c == '+' || c == '*' || c == '#') return YES;
if(c >= '0' && c <= '9') return YES;
return NO;

- (void)dealloc {
[predefinedFormats release];
[super dealloc];


Testing against a web server that doesn't respond, aka infinite delay

I wanted to simulate the situation when the server doesn't respond, without changing much. A friend of mine suggested I use any of the unassigned IPs on our LAN. Exactly what I was looking for! The request timed-out and I was able to see how my application would act in this case. We may also add an entry in the hosts file to name this black-hole-server, so it can be used later as needed. The hosts file will also enable us to override the DNS look-up and route the requests to the black hole, in case the host name was hard-coded/fixed in a binary, and we don't want to/can't modify the code.

Thursday, January 14, 2010

Daniel Pink on the surprising science of motivation - TEDTalks

A friend of mine recommended this video and I liked it so much I shared it immediately with other friends. As some of them were very busy to watch the whole thing, they asked for a summary. And since the topic was still active on my mind, I decided to do it for them and later I decided to make it available to everybody on this blog.

I have to emphasize that this text is based entirely and solely on this great talk. It is a mere attempt to provide a text version and summarize the main ideas, and I have to say it doesn't come close to the quality of the talk or the performance of the speaker.

A case for rethinking how we run our businesses.

Scientists of human behavior questioned the power of incentives. These contingent motivators: If-you-do-this then you-get-that, work in some circumstances but for a lot of tasks they actually either don't work or often do harm. This is one of the most robust findings in social science and also one of the most ignored.

There's a mismatch between what science knows and what business does.

Our business operating systems, the set of assumptions and protocols beneath our businesses, how we motivate people, how we apply our human resources. It's built entirely on these extrinsic motivators. Around carrots and sticks. This is actually fine for many 20th century's tasks. But for 21st century's tasks, that mechanistic, reward-and-punishment approach often doesn't work, and often does harm.

If-then rewards work really well for unsophisticated tasks, where there's a simple set of rules and a clear destination. Rewards by their very nature, narrow our focus. Concentrate the mind. That's why they work in so many cases. But for real problems, we don't want to narrow our focus and restrict our possibilities. For example, to overcome what is called functional fixedness.

Routine, rule-based, left-brained work, certain kinds of accounting, certain kinds of computer programming has become fairly easy to outsource, fairly easy to automate. Software can do it faster, low-cost providers around the world can do it cheaper. So what really matters, are the more right-brained, creative, conceptual kinds of abilities.

Think about your work. Are the problems you face the kind of problems with a clear set of rules and a single solution? No. The rules are mystifying. The solution, if it exists at all, is surprising and not obvious. If-then rewards, don't work in that case. This is not a feeling. This is not a philosophy. This is a fact, a true fact.

Too many organization are making their decisions, their policies about talents and people., based on assumptions that are out-dated, unexamined and rooted more in folklore than in science. If we really want high performance on the definitional tasks of the 21st century the solution is not to do more of the wrong thing: to entice people with the sweet carrot or threaten them with the sharper stick. We need a whole new approach.

The good news about all this is that the scientists who've been studying human motivation have given us this new approach. It's an approach built much more around intrinsic motivation. Around the desire to do things because they matter, because we like it, because they're interesting, because they're part of something important.

That new operating system for our businesses revolves around 3 elements: autonomy, mastery and purpose.
Autonomy: the urge to direct our own lives.
Mastery: the desire to get better and better at something that matters.
Purpose: the yearning to do what we do in the service of something larger than ourselves.

Today, we're going to talk only about autonomy.

In the 20th century, we came up with this idea about management. Management didn't emanate from nature, it's like: it's not a tree, it's a television set. Somebody invented it. And it doesn't mean it's going to work forever. Traditional notions of management is great if you want compliance. But if you want engagement, self-direction works better.

Let me give you an example of some kinds of radical notions of self-directions. You don't see a lot of it, but you see the first stirrings of something really interesting. Because what it means is: paying people adequately and fairly, absolutely, getting the issue of money out of the table, and then giving people much of autonomy. The 20% time, done famously at Google, where engineers can work 20% of their time on anything they want. They have autonomy over their time, their tasks, their teams, their techniques: radical amounts of autonomy. And at Google, as many of you know, about half the new products in a typical years are burst during that 20% time like: Gmail, Orkut and News.

Another more radical example of autonomy: something called the results only work environment or ROWE. In a ROWE people don't have schedules. They show up when they want, they don't have to be at the office at a certain time or any time. They just have to get the work done. How they do it, when they do it, where they do it is totally up to them. Meetings in these kinds of environments are optional. What happens? almost across the board: productivity goes up, worker-enga worker-satis turn-over goes down.

Autonomy, master, and purpose. These are the building blocks of a new way of doing things.

Now, some of you might look at this and say: mmm, that sounds nice but it's Utopian. And I say nope. I have proof. In mid 1990's Microsoft started an encyclopedia called Encarta. They deployed all the right incentives. They payed professionals to write and edit thousands of articles. Well compensated managers oversaw the whole thing to make sure it came on-budget and on-time. Few years later, a new encyclopedia get started. A different model. Do it for fun. No one gets payed a cent, or a euro or a yen. Do it because you like to do it. Now if you had, just 10 years ago, if you had gone to an economist, any where, and said: hey, I have these 2 different models for creating an encyclopedia, if they went head to head, who'd win? 10 years ago, you couldn't not find a single sober economist on planet earth who'd predicted the Wikipedia model.

Intrinsic motivators vs. extrinsic motivators. Autonomy, mastery and purpose vs. carrots and sticks. And who wins?

To wrap-up (17:20)

There's a mismatch between what science knows and what business does. And here's what science knows:
1) Those 20th century's rewards, those motivators, we think are the natural part of business: Do work, but only in a surprisingly narrow band of circumstances.
2) Those if-then rewards, often destroy creativity.
3) The secret to high performance isn't rewards and punishments, but this unseen intrinsic drive. The drive to do things for their own sake. The drive to do things because they matter.

And here's the best part. We already know this. The science confirms what we know in our hearts. So, if we repair this mismatch between what science knows and what business does. If we bring our notions of motivation into the 21st century. If we get past this lazy, dangerous, ideology of carrots and sticks, we can strengthen our businesses, we can solve a lot of our real problems and maybe, maybe we can change the world.