IBM Research | Ponder This | April 2009 challenges
Skip to main content

Ponder This

April 2009

<<March April May>>

Ponder This Challenge:

Design a storage system that encodes 24 information bits on 8 disks of 4 bits each, such that:

  1. Combining the 8*4 bits into a 32 bits number (taking a nibble from each disk), a function f from 24 bits to 32 can be computed using only 5 operations, each of which is out of the set {+, -, *, /, %, &, |, ~} (addition; subtraction, multiplication; integer division, modulo; bitwise-and; bitwise-or; and bitwise-not) on variable length integers. In other words, if every operation takes a nanosecond, the function can be computed in 5 nanoseconds.
  2. One can recover the original 24 bits even after any 2 of the 8 disks crash (making them unreadable and hence loosing 2 nibbles).

Clue #1 (04/06): f(x) = ((((x * c1) & c2) * c3) & c4) % c5;

Update (04/07): When you read the data, you know which two disks have failed.

Clue #2 (updated 04/24): c1 = (2792-1)/(233-1); c2 = (2816-1)/(234-1); c4 = (21088-1)/(234-1)

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

  

Challenge: 04/01/2009 @ 10:00 AM EST
Solution: 06/01/2009 @ 09:00 AM EST
List Updated: 06/08/2009 @ 11:00 AM EST

People who answered correctly:

Michael Brand (04/02/2009 04:47 PM EDT)
Eli Biham (04/16/2009 06:15 AM EDT)
Boris Nikolaus (04/30/2009 12:44 PM EDT)
Nyles Heise (04/30/2009 00:16 AM EDT)
Corey Cerovsek (05/04/2009 08:58 AM EDT)
Gary M Gerken (05/05/2009 11:48 PM EDT)
Daniel Bitin (05/06/2009 12:55 PM EDT)
Balakrishnan V (05/07/2009 02:00 PM EDT)
Dan Dima (05/21/2009 10:02 AM EDT)
Liubing Yu (05/29/2009 04:30 AM EDT)
Hongcheng Zhu (05/31/2009 10:39 AM EDT)

Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.