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:
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[
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 - 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)
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 whosei'th element is
- a[i]<<b[i] (for the vectorization of left shift)
- a[i]>>b[i] (for the vectorization of right shift)
- a[i]*b[i] (for the vectorization of multiplication)
- a[i]/b[i] (for the vectorization of integer division)
- a[i]%b[i] (for the vectorization of modulo-taking)
## Part 2:Consider the integer encoding the array whosei'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 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 __riddlesbrand.scso.com__.
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.

Enjoy!