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>
• 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 @@
>       {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

```

• Prev by Date: Re: Reducing binary representation
• Next by Date: Re: Reducing binary representation
• Previous by thread: Reducing binary representation
• Next by thread: Re: Reducing binary representation