# decompose a number (less than 255) in a sum of powers of 2

Is there a built in function that would take a number and decompose it into a sum of powers of 2? The numbers will be non negative less than 256.

For what it's worth I'm trying to understand a paper on RAID 6, which uses some Galois field in calculating the second parity (in this case) byte. There's a rule for mulitplying by 2, which is unusual in iteself, at least to me. It seems that in order to generalize mulitplication to any two bytes I would have decompose those bytes into powers of 2 and mulitply them like polynomials. Then in this case, mod them by 255.

I can write a function to do the necessary decomposition, but I thought that there might be a built in function.

-
You might want to check out the FiniteFields package. –  whuber Jun 30 '12 at 18:04

IntegerDigits works

Try

powers = IntegerDigits[204, 2]


{1, 1, 0, 0, 1, 1, 0, 0}

Now, if you want that formatted as a sum of powers of two, you have to hold it. For example

Total@MapIndexed[#1 Defer[2]^(First@#2 - 1) &, Reverse@powers]


2^2 + 2^3 + 2^6 + 2^7

EDIT

Nicer code, given that your numbers go up to 255

pow2[num_]:=Inner[#1 2^Defer[#2] &, IntegerDigits[num, 2, 8], Range[7, 0, -1], Plus]

-
Meh, powers, Reverse@powers, what's the difference? :-) –  Brett Champion Jun 29 '12 at 23:39
@BrettChampion Reverse@The@Powers@That@Be[] –  belisarius Jun 29 '12 at 23:40
@BrettChampion, my initial reverseless version was for our arabian audience –  Rojo Jun 29 '12 at 23:42
@belisarius The[Powers[That[Be[]]]] -- apparently they're immune to being reversed. (I'm not surprised, really.) –  Brett Champion Jun 29 '12 at 23:42
Thanks very much! –  Mitchell Kaplan Jun 30 '12 at 1:22

This isn't directly an answer, and I'll delete it if it is off target. But you might want to use some non-System context functionality for taking polynomial-mod-2 products. Specifically this works with integer lists of coefficients. I'll show an example below.

In[1110]:= SeedRandom[1111];
vals = RandomInteger[2^8 - 1, 2]
intlists = Map[Reverse[IntegerDigits[#, 2]] &, vals]

Out[1111]= {19, 234}

Out[1112]= {{1, 1, 0, 0, 1}, {0, 1, 0, 1, 0, 1, 1, 1}}


Now we'll take the polynomial product and see what we recover when we convert the corresponding list to an integer, working in base 2.

In[1134]:= intproduct = Times @@ vals
polyprod = AlgebraPolynomialTimesModList[Sequence @@ intlists, 2]
FromDigits[Reverse[polyprod], 2]

Out[1134]= 4446

Out[1135]= {0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1}

Out[1136]= 3998


3998 != 4446 so we do not get the product of the original inputs. No surprise, really, because the polynomial multiplication does not allow for carries. To show that it is (plausibly) doing the correct thing, we can use a much bigger modulus, large enough to avoid overflows in this example (that is, nothing will get clipped from the modulus). When we conver that result back to an integer, we do recover the product of the original pair.

In[1137]:= polyprodbiggermod =
AlgebraPolynomialTimesModList[Sequence @@ intlists, 10]
FromDigits[Reverse[polyprodbiggermod], 2]

Out[1137]= {0, 1, 1, 1, 1, 2, 2, 3, 1, 1, 1, 1}

Out[1138]= 4446


Whether this Algebra context "list polynomial" manipulation functionality is useful will depend on your actual needs. I wrote this because I'm guessing it is, but that is just a guess.

-