Daniel Lemire's blog

Big-O notation and real-world performance

, 3 min read

Classical Newtonian mechanics is always mathematically consistent. However, Newtonian mechanics assumes that bodies move without friction and that we stay far from the speed of light. When your car is stuck in the mud or you are running an intergalactic spaceship, frictionless Newtonian mechanics…

Should computer scientists run experiments?

, 4 min read

Jeffrey Ullman, a famous computer science professor, published an essay pushing back about the need to run experiments in computer science. Apparently, some conference reviewers gave him a hard time regarding a paper he submitted because it did not include experiments. I am in general agreement…

Fast integer compression in Java

, 2 min read

Last year, we published a fast C++ library to quickly compress and decompress arrays of integers. To get good compression, we use differential coding: the arrays of integers are sorted and instead of storing the integers themselves, we store the difference between successive integers. The…

Staying sharp requires “intellectual gardening”

, 3 min read

Gardening requires consistency. A beautiful garden is unstable. Some plants want to expand their reach and kill out the competition. Some plants are simply out of their element and need a little bit of help. Generally, there is too much competition for water, sunshine and minerals. So the gardener…

Hashing and the Birthday paradox: a cautionary tale

, 2 min read

If you meet a stranger, the probability that he will have the same birth date as yourself is probably less than 1%. It is roughly 1/365 if you make simplifying assumptions. The Birthday paradox is the observation that given a full classroom (say 60 students), it is almost certain that two students…

Meetings are like sex

, 2 min read

Meetings are like sex. Everybody thinks that they are good at it… until they ask for the truth. We never have real discussions about it: I did not want to say anything… but you know this meeting thing? You are not very good at it. Meetings are like sex in the sense that they make most people…

Why I never give straight answers

, 3 min read

There are some questions that you should never answer. This is true when you are facing justice, your angry wife, or students. Carl Zimmer, a famous science writer, complains about how students keep asking him homework questions. There is no doubt some degree of intellectual laziness mixed with a…

Three questions about e-learning in college

, 2 min read

Timothy Taylor observes that research about online instruction tells us that online teaching is just as effective as classroom teaching. The main drawback of asynchronous online teaching is the high drop-out rate. He moves on to ask three important questions about e-learning for college students.…

A criticism of computer science: models or modèles?

, 3 min read

I was recently on a review committee for a PhD proposal. The student was brilliant. His proposal sounded deep and engaging. The methodology looked scientific: build a model, program the software, gather data, compute the metrics. Yet the student’s hypothesis could never be realistically be proven…

How to be effective at open source: by programmers, for programmers

, 2 min read

Though it does not get much press, one of the great social and technological innovations of the last 30 years has been open source software. To about 90% of the population, this remains a mystery. Are the people producing open source code communists? The truth, of course, is that open source…

P equal to NP and all that

, 2 min read

One of the better known problems in Computer Science is the P versus NP problem. It is often related to the following question: do all problems for which we can check the correctness of a solution quickly can also be solved quickly. Most computer scientists believe that P is different from NP. In…

You probably shouldn´t use a spreadsheet for important work

, 1 min read

Following the Reinhart-Rogoff case, where famous scientists go formulas wrong in the Excel spreadsheet that supported their research, a lot of people commented on the adequacy of a spreadsheet tool for important work. Excel does have one tremendous benefit: it is accessible. Most people using…

Share your software early: the Reinhart-Rogoff case

, 3 min read

I like stories where prestigious professors screw up spectacularly. It reminds us that everybody gets it wrong some of the time. The Reinhart-Rogoff story is one such case. Two very reputed professors at Harvard University, Carmen Reinhart and Kenneth Rogoff, published online a working paper in…

The irony of “we are the 99 percent”

, 4 min read

David Graeber is credited as the true organizer of the Occupy Wall Street movement, a widely reported month-long demonstration against capitalism. He has also been credited the phrase “We are the 99 percent”. I have reviewed his insightful book on the history of debt and money on this blog…

Do we lose intelligence and creativity as we grow older?

, 1 min read

It was popular during the XXth century to say that most scientific discovery are done by young scientists (under 30). The implicit assumption was that the brain decayed over time, like an apple left to rot. The most recent research contradicts this unavoidable decay. While it was once believed that…

We are sentenced to permanent cognitive stretching

, 2 min read

If you want to get better at something, should remain in your comfort zone? Or should you, rather, be exposed to ideas or techniques slightly beyond your reach? It should be self-evident that the latter is the correct answer: it is called cognitive stretching. It is an essential part of…

We need to get a lot better at imagining the future

, 5 min read

We live in an era of fast changes. Ten years ago, YouTube was unthinkable, social media did not exist (Facebook was founded in 2004), we got our movies on tapes at video stores, cell phones did not have cameras, and so on. If you are reasonable, you have to expect ever greater changes in the next…

Advanced tips for dealing with your email inbox

, 1 min read

I probably receive 50 emails a day, not counting spam. Give it a week, and I could easily end up with 200 unread emails in my inbox. When that happens, it feels about the same as if I hadn’t brushed my teeth in a week. It is not only annoying, it lowers my self-esteem. When my inbox is out of…

We are getting smarter as a matter of survival

, 3 min read

A journalism student got very depressed after reading my post on genetically engineered intelligence. His feeling can be summarized by this question: if at some point in the near future, human beings or machines become orders of magnitude smarter than we are, why bother making an effort now?…