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 webmaster.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: webmster@us.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 webmaster.