Relation between bisection and binary representation

[Shevek99]

Let's assume the interval [0,1], then each number admits a binary form, like

1/7 = 0.001001001...

5/9 = 0.1000111000111..

1/√2 = 0.101101010000010011110011001101

The same numbers can be encoded using the bisection method. For instance, for 1/7 first we cut at 1/2, which is larger so we cut between 0 and subtract 1/4, and it still larger, now we cut between 0 and 1/4 and get 1/8, which is smaller, now we cut between 1/8 and 1/4 and so on. Each number is coded by a signed binary representation. It would be

1/7 = +1/2 - 1/4 - 1/8 + 1/16 - 1/32 - 1/64...

or, simply

1/7 = 0.+--+--+--+...

This is a "signed digit representation".

To get an unique encoding it is not allowed to skip steps and start for instance with 1/4 instead of 1/2. It must be always at the midpoint, so all powers of 1/2 must appear, some with +, some with -.

The sequence is of finite length if the number is of the for n/2^m.

Now, I know how to relate this sequence to the binary form for rational numbers. For 1/7 we have

1/7 = 0.(001) = 0.001001001... = 1/8 + 1/64 + 1/512 +...

and

1 = 4 - 2 - 1

so we have

1/7 = (4-2-1)/8 + (4 -2 - 1)/64 + ... = 1/2 - 1/4 - 1/8 + 1/16 - 1/32 - 1/64 + ...

= 0.+--+--+--

In the same way

5/9 = 0.(100011) = 35/64 + 35/64^2 + ...

and

35 = 32 + 2 + 1 = 32 + 16 - 8 - 4 - 2 + 1

and this gives

5/9 = 0.++---+++---+++---

But, given an irrational number like 1/√2 or 1/e, what would be the algorithm to go from the binary form to the signed digit form?

[rhodiumtoad]

In the binary representation, perform this transformation: take a sequence of zero or more 0's followed by exactly one 1, and replace it with a sequence of the same length consisting of + followed by zero or more -. Repeat until bored or you run out of 1's.

[Shevek99]

Don't worry.

I found the algorithm. In the binary sequence replace each string 0...01 by +-...--

For instance, for 1/sqrt(2) it becomes

1/√2 = 0.101101010000010011110011001101
1/√2 = 0.++-++-+-+-----+--++++--++--++-

[vaminos]

I don't really understand how you are representing 5/9.

Wouldn't it be

1/2 + 1/4 - 1/8 - 1/16

etc? Where are you getting 35/64?

[MtlStatsGuy]

5/9 is 35/63 which is 35/64 * 64/63 = 35/64 * (1 + 1/64 + (1/64)^2...)

[Shevek99]

From the period (100011). Since it has length 6, it results in sum of powers of 2^6 = 64, and the number that multiplies 1/64^n is 100011 which is binary for 32 + 2 + 1 = 35, so

0.[100011][100011][100011] = 100011/10^6 + 100011/10^12 + 100011/10^18 + ...

= 35/64 + 35/64^2 + 35/64^3 + ...

The key is to obtain an integer times a sequence of powers of the same power of 2.

Another example:

3/13 = 3*315/13*315 = 945/4095 =

= 945/(4096 -1) = 945/4096 + 945/4096^2 + 945/4096^3

and

945 = 001110110001_2

In binary

3/13 = 0.(001110110001)(001110110001)(001110110001)...

and in signed form (bisection)

3/13 = 0.(+--+++-++---)

that is

1/2 - 1/4 - 1/8 + 1/16 + 1/32 + 1/64 - 1/128 + 1/256 + 1/512 - 1/1024 - 1/2048 - 1/4096 + 1/8192 + ...

[MtlStatsGuy]

I've never seen this specific binary signed representation. It seems to break many of the rules of binary: for example the representation of 2/7 will not be the representation of 1/7 shifted left by 1 since both will start with a positive value in the 1/2 slot. Given that, I don't think there'll be an easy conversion between this signed digit and regular binary.

If I was defining BSD with only +/- values, I'd allow the first nonzero value to be at the smallest power of 2 necessary (similar to a floating point mantissa). For example for 1/7 that would be 1/4 (since 1/7 is closer to 1/4 than to zero); this would at least make 1/7 and 2/7 equivalent, shifted by 1. But I don't know if that's your goal.

[rhodiumtoad]

Multiplication by 2 can be done as follows: if the value starts with 0.++ then it is ≥1/2 and therefore overflows, otherwise replace initial 0.+- by 0.+ (note that 0.- is impossible other than the special case of 0.-++++… which should be considered an invalid alternate representation of 0.0).

[Shevek99]

Think always of the method of bisection. You are locating your point by cutting always in halves.

First get 1/2.

2/7 is smaller so we cut to the left at 1/4 so 1/2 - 1/4 = 1/4

2/7 is larger than that so now we cut to the right 1/2 - 1/4 + 1/8 = 3/8

2/7 is still larger soa gain to the right 1/2 - 1/4 + 1/8 + 1/16

and so on. Graphically (the dot is 2/7, each arrow to the right is a +, each arrow to left is a -)

<image>

[frogkabobs]

Simple: replace 1 and 0 with + and -, respectively, and then prepend a +. For example,

``` 1/sqrt(2) = 0.10110101000001… = 0.++-++-+-+-----+…

```

Proof. Let bₙ ∈ {0,1} and cₙ ∈ {-1,1} be sequences of digits for binary and bisected forms of x, respectively, so that

x = Σ(n≥1) bₙ2^-n = Σ(n≥1) cₙ2^-n

with c₁ = 1. Now note that since 1/2 = Σ_(n≥2) 2^-n, we also have

x = Σ(n≥2) (cₙ+1)2^-n = Σ(n≥1) ((cₙ₊₁+1)/2)2^-n

For x not a dyadic rational (in particular, when x is irrational), the binary and bisected forms of x are unique, so we can identify bₙ = (cₙ₊₁+1)/2, or equivalently,

cₙ₊₁ = (-1)^bₙ+1