MathGroup Archive 2005

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

Search the Archive

Re: Reducing binary representation

  • To: mathgroup at smc.vnet.net
  • Subject: [mg57175] Re: Reducing binary representation
  • From: dh <dh at metrohm.ch>
  • Date: Fri, 20 May 2005 04:43:08 -0400 (EDT)
  • References: <d6heg9$d24$1@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

Hi Torsten,
  We  start with an arbitrary integer and get its binary digits.
"Split" gives us lists of repeated digits.
We replace runs of 1's by lists of equal length with a marker 2/3 at the 
high/low order bit. Finally we "Flatten" to get a single list t1.
Bits with marker 2 must be multiplied by 2 and bits with marker 3 mark 
negative nummbers.

n = 1324;
t1 = Split[
IntegerDigits[n, 2] ] /. x : {1, (1) ..} :> ({2, Table[0, {Length[x] -
         2}], 3}) // Flatten;

 From List t1 we get a list t2 with only the not-marked bits. And a 
third list t3 with the bits we must multiply by 2.
To have space for the multiplication by 2, we expand both lists by an 
additional high order digit of 0.
Finally we multiply list t3 by bit-shift and add both lists. This gives 
the non negative numbers.

t2 = Prepend[t1 /. {2 -> 0, 3 -> 0}, 0];
t3 = Prepend[t1 /. {3 -> 0, 1 -> 0}, 0];
t3 = RotateLeft[t3] /. {2 -> 1};
t2 = t2 + t3;

 From t1  we obtain the list with only the negative numbers and pad 
again with a zero.

t3 = Prepend[t1 /. {2 -> 0, 1 -> 0, 3 -> 1},0];

Now we have the exponents of the pos.and neg. numbers and create the output

i = 0; t2 = (HoldForm[2^#] &)[i++ ]# & /@ Reverse[t2]
i = 0; t3 = (HoldForm[2^#] &)[i++ ]# & /@ Reverse[t3]
Plus @@ (t2 - t3)

Sincerely, Daniel

Torsten Coym 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
> 


  • Prev by Date: Re: Reducing binary representation
  • Next by Date: runs test for evaluation of model fit
  • Previous by thread: Re: Reducing binary representation
  • Next by thread: Re: Reducing binary representation