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