MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • 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