Re: Reducing binary representation
- To: mathgroup at smc.vnet.net
- Subject: [mg57199] Re: [mg57142] Reducing binary representation
- From: DrBob <drbob at bigfoot.com>
- Date: Fri, 20 May 2005 04:43:58 -0400 (EDT)
- References: <200505190708.DAA13043@smc.vnet.net>
- Reply-to: drbob at bigfoot.com
- Sender: owner-wri-mathgroup at wolfram.com
Here's a solution, so long as the numbers don't get too large: Clear@f f[n_] := Module[{binary = IntegerDigits[n, 2], mod, s, k}, mod = Last@binary; s = Select[Distribute[Append[Table[Range[-1, 1], {Length@binary}], If[mod == 0, {0}, {-1, 1}]], List], FromDigits[#, 2] == n &] /. {0, x__} -> {x}; k = Min[Tr /@ Abs /@ s]; s = Select[s, k == Tr@Abs@# &]; #.(2^HoldForm /@ Range[Length@# - 1, 0, -1]) & /@ s ] f@121 ReleaseHold@% {2^HoldForm[0] - 2^HoldForm[3] + 2^HoldForm[7]} {121} Notice the solution isn't always unique: f[207] ReleaseHold[%] {-2^HoldForm[0] + 2^HoldForm[4] + 2^HoldForm[6] + 2^HoldForm[7], -2^HoldForm[0] + 2^HoldForm[4] - 2^HoldForm[6] + 2^HoldForm[8], -2^HoldForm[0] - 2^HoldForm[4] - 2^HoldForm[5] + 2^HoldForm[8]} {207, 207, 207} For larger numbers, it's probably possible to devise a recursive procedure that takes further advantage of our knowledge of the last binary digit. Bobby On Thu, 19 May 2005 03:08:09 -0400 (EDT), Torsten Coym <torsten.coym at eas.iis.fraunhofer.de> wrote: > Hi MathGroup, > > I want to reduce the number of coefficients in the binary representation > of arbitrary integer numbers. I managed to convert an integer number > into a sum of powers of two in the following way: > > In[7]:= > ToBinary[x_, n_] := Plus @@ > Sequence[MapThread[Times, > {Table[(HoldForm[2^#1] & )[i], {i, n - 1, 0, -1}], > IntegerDigits[x, 2, n]}]] > > In[8]:= > ToBinary[121, 10] > > Out[8]= > HoldForm[2^0] + HoldForm[2^3] + HoldForm[2^4] + > HoldForm[2^5] + HoldForm[2^6] > > The sum of adjacent powers of two can be reduced as follows: > > In[9]:= > Sum[2^i, {i, k, j}] > > Out[9]= > 2^(1 + j) - 2^k > > I now want to apply that to the binary number representation, so that > 121 will become > > 2^7-2^3+2^0 > > but I cannont figure out how to do this. If I release the Hold[] > Mathematica just evaluates all the terms containing "2" to get "121", > which is not what I want ;) > > Unfortunately I have no idea how to tackle this kind of problem. Any > suggestion would be appreciated. > Thank you. > > Torsten > > > > -- DrBob at bigfoot.com
- References:
- Reducing binary representation
- From: Torsten Coym <torsten.coym@eas.iis.fraunhofer.de>
- Reducing binary representation