Passing integers by reference can be expensive…

In languages like C++, you can pass values to functions in two ways. You can pass by value: the value is semantically “copied” before being passed to the function. Any change you made to the value within the function will be gone after the function...

Faster threshold queries with cache-sensitive scancount

Suppose that you are given 100 sorted arrays of integers. You can compute their union or their intersection. It is a common setup in data indexing: the integers might be unique identifiers. But there is more than just intersections and unions… What...

Nearly Divisionless Random Integer Generation On Various Systems

It is common in software to need random integers within a range of values. For example, you may need to pick an object at random in an array. Random shuffling algorithms require such random integers. Typically, you generate a regular integers (say a...

21 open problems in Artificial Intelligence

Peter Turney has come up with a list of 21 (important) open problems in the field of Artificial Intelligence. I am not aware of any such list anywhere, so this might be an important contribution. For comparison, Wikipedia as a list of open problems...

Bounding the cost of the intersection between a small array and a large array

Consider the scenario where you are given a small sorted array of integers (e.g., [1,10,100]) and a large sorted array ([1,2,13,51,…]). You want to compute the intersection between these two arrays. A simple approach would be to take each value in...

AVX-512: when and how to use these new instructions

Our processors typically do computations using small data stores called registers. On 64-bit processors, 64-bit registers are frequently used. Most modern processors also have vector instructions and these instructions operate on larger registers...

Technological aging

We are all familiar with biological aging. Roughly speaking, it is the loss of fitness that most animals undergo with time. At the present time, there is simply not much you can do against biological aging. You are just not going to win any gold...

I still don’t have the multiplication tables memorized

I read this on slashdot:I have a PhD in math, and I still don't have the multiplication tables memorizedNow I know I am not the only one!In other news, I

Should our kids use pencils or keyboards?

In Montreal, most kids have to write on paper using a pencil. They have paper dictionaries. My kids have spent an enormous amount of time learning to write in cursive using pencils, and no time at all (in school) learning to touch type with a...

Faster remainders when the divisor is a constant: beating compilers and libdivide

Not all instructions on modern processors cost the same. Additions and subtractions are cheaper than multiplications which are themselves cheaper than divisions. For this reason, compilers frequently replace division instructions by multiplications....

Asking the right question is more important than getting the right answer

Schools train us to provide the right answers to predefined questions. Yet anyone with experience from the real world knows that, more often than not, the difficult part is to find the right question.To make a remarkable contribution, you need to...

Rethinking Hamming’s questions

Richard Hamming is a famous computer scientist. In his talk You and Your Research, Hamming recounts how asked researchers three questions which I paraphrase: What are the important problems of your field? What important problems are you working on?...

Fast Bounded Random Numbers on GPUs

We often use random numbers in software in applications such as simulations or machine learning. Fast random number generators tend to produce integers in [0,232) or [0,264). Yet many applications require integers in a given interval, say the...

Science and Technology links (December 1st 2018)

Autism affects about 1% of the population and four times as many males as females. In older highly educated people, drinking 2 cups of coffee a day is associated with a reduced mortality rate of 22%. (This does not mean that drinking coffee makes...

AVX-512 throttling: heavy instructions are maybe not so dangerous

Related Posts: Innovation as a Fringe Activity Science and Technology links (March 17, 2017) By how much does AVX-512 slow down your CPU? A first…