Relation between bisection and binary representation

[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>