Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
    
You might want to check out the FiniteFields package. –  whuber Jun 30 '12 at 18:04
add comment

2 Answers

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]
share|improve this answer
    
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
2  
@BrettChampion, my initial reverseless version was for our arabian audience –  Rojo Jun 29 '12 at 23:42
1  
@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
show 1 more comment

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 = Algebra`PolynomialTimesModList[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 = 
 Algebra`PolynomialTimesModList[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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.