Re: Reducing binary representation
- To: mathgroup at smc.vnet.net
- Subject: [mg57204] Re: Reducing binary representation
- From: Maxim <ab_def at prontomail.com>
- Date: Fri, 20 May 2005 04:44:26 -0400 (EDT)
- References: <d6heg9$d24$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
On Thu, 19 May 2005 07:16:25 +0000 (UTC), 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
>
In[1]:=
f[n_] := Append[Reverse@ IntegerDigits[n, 2], 0] //.
{s___, 1, s1: (1).., 0, s2___} :>
Join[{s, -1}, 0*{s1}, {1, s2}] //
#.Array[HoldForm[2^#]&, Length@ #, 0]&
In[2]:= f[121]
Out[2]= HoldForm[2^0] - HoldForm[2^3] + HoldForm[2^7]
In[3]:= ReleaseHold[%]
Out[3]= 121
This uses the fact that ReplaceAll starts by trying the shortest matches
for BlankSequence/BlankNullSequence and Repeated/RepeatedNull, so
{0, 1, 1} /. {s___, 1, ___} -> rhs
first sets s to Sequence[0].
Things gets more complicated if there are several patterns; if we define
f2 like this (certainly a very inefficient way):
f2[n_] := Append[Reverse@ IntegerDigits[n, 2], 0] //.
{s___, 1, s1: (1).., s2___} /;
(Print[Length /@ {{s}, {s1}, {s2}}]; {s2}[[1]] == 0) :>
Join[{s, -1}, 0*{s1}, {1, s2}] //
#.Array[HoldForm[2^#]&, Length@ #, 0]&
then f2[2^5 - 1] will give the following output:
{0, 1, 4}
{0, 2, 3}
{1, 1, 3}
{0, 3, 2}
{1, 2, 2}
{2, 1, 2}
{0, 4, 1}
which shows that Mathematica tries to minimize the total length of {s, s1}
-- 0+1, then 0+2, 1+1, 0+3, 1+2, 2+1, 0+4. From what section 2.3.8 of The
Book says ("In general, Mathematica tries first those matches that assign
the shortest sequences of arguments to the first multiple blanks that
appear in the pattern.") I would expect the pattern matcher to search
through all combinations with {s} === {} first.
Maxim Rytin
m.r at inbox.ru