Using your Head is Permitted

February 2009 riddle

This month's riddle returns (for the last time, I promise) to the computational model first introduced in the December 2008 riddle, checking out how much further it can be over-exerted. The same warning message applies as in last month's riddle:

Spoiler alert: The following description contains hints regarding the solutions of the riddles of the last two months. If you still mean to tackle those other riddles, you may want to hold on before you continue to this one.

As a reminder, the solution to the December 2008 riddle had, at its core, the ability to pack the data from many integers into a single integer. For example, if we have an array of x[0], ..., x[n-1] non-negative integers, we can encode all of it into a single integer as the sum of x[i]*2i*width, once an appropriate value of width is chosen. For a person knowing n and width the information in the sum is equivalent to the information in the entire array.

The December solution demonstrated that certain actions, such as addition, subtraction and element-by-element comparison, can be "vectorized" in this representation. That is to say, if we have two integers, "A" and "B", encoding the arrays "a[i]" and "b[i]", respectively, with both encodings using the same known value of width and both arrays having the same size, n, then in O(1) time we can calculate the integer encoding the array such that its i'th element is:

  • a[i]+b[i] (for the vectorization of addition)
  • a[i]-b[i] (for the vectorization of subtraction)
  • a[i]≥b[i] (for the vectorization of greater-or-equal comparison)
The January riddle expounded on this topic by first demonstrating that arrays are not needed in the computational model at all, and second adding further actions that can be vectorized. These included forward and backward array look-up, all comparators and the assignment of a constant value to all array elements.

This leaves only a handful of operations that can be done in O(1) on a single integer that we still haven't shown to be vectorizeable. Part 1 of this month's riddle deals with all remaining operations (except conditional jumps).

Part 1:

Given integers "A" and "B" as described above, show that it is possible to calculate in O(1) the integer encoding the array whose i'th element is
  1. a[i]<<b[i] (for the vectorization of left shift)
  2. a[i]>>b[i] (for the vectorization of right shift)
  3. a[i]*b[i] (for the vectorization of multiplication)
  4. a[i]/b[i] (for the vectorization of integer division)
  5. a[i]%b[i] (for the vectorization of modulo-taking)

Part 2:

Consider the integer encoding the array whose i'th element equals "a[i]!" (that is, the array whose elements are the factorial of the input elements).

Can this value be calculated in O(1)? Prove impossibility or show an algorithm that does this.

To appear on this month's solvers' list, answer either or both parts of the riddle. A separate list will be kept for each part.

In all parts and sub-parts you may assume, for convenience, that all values of "a[i]" and "b[i]" are positive and that the "width" value of "A" and "B" is large enough to return the desired output encoded in the same "width" without overflows.

List of solvers:

Both Parts:

Hongcheng Zhu (21 February 20:24)

Part 1 only:

Bin Jin (19 February 22:44)

Part 2 only:

Omer Angel (14 February 11:40)

Elegant solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page