# Definition

* Angles measured in turns
* doubling map
Angle doubling map
    $T(r)=(2r){\bmod {1}}$
Input: proper fraction $r$ in forms
* decimal ratio ( if r is not irrational )
* decimal sequence of digits and radix
* binary sequence of digits and radix
Output: proper fraction

# Doubling map on binary fraction

Effect of doubling map d on binary representation of fraction x is to simply shift the bits of x to the left, discarding the bit that shifted into the ones place = left shift.
$x=0.b_{1}b_{2}b_{3}\dots .$
$d(x)=0.b_{2}b_{3}\dots .$
Example
* $2*{\frac {11}{31}}=2*0.01011=0.10110={\frac {22}{31}}$

# Orbits

Iteration of the map gives orbit ( sequence of angles):
* periodic ( input is a rational number with odd denominator $d=2^{p}-1$)
* preperiodic ( input is rational number with even denominator )
* aperiodic ( when input is irrational number )
All above types are infinite. Finite binary expansion has equal infinite preperiodic representation.

## periodic

Periodic orbits of angles under doubling map
Note that here chord joining 2 points z1 and z2 on unit circle means that $z_{2}=z_{1}^{2}$. It does not mean that these points are landing points of the same ray.
Some orbits do not cross :
* Period 2 orbit ( angles under doubling map)
* Period 3 orbit ( angles under doubling map)
* Period 4 orbit ( angles under doubling map)
* Period 5 orbit ( angles under doubling map)
* Period 6 orbit ( angles under doubling map)
* period 9
but some do cross:
* Period 6 orbit of 11/63 under doubling map
* Period 9 orbit of 74/511 under doubling map
Periodic orbits for angles $r={\frac {n}{d}}$ with odd denominator d
Where:
* n is numerator of the fraction = integer from 0 to (d-1)
* d is denominator of the fraction = positive integer
* p is a period = positive integer
Period 1 ( 1 orbit) for angles = ${\frac {n}{2^{1}-1}}={\frac {n}{1}}$
Period 2 ( 1 orbit) for angles = ${\frac {n}{2^{2}-1}}={\frac {n}{3}}$
Period 3 ( 2 orbits) for angles = ${\frac {n}{2^{3}-1}}={\frac {n}{7}}$
Period 4 ( 3 orbits) for angles = ${\frac {n}{2^{4}-1}}={\frac {n}{15}}$
Period 5 ( 6 orbits) for angles = ${\frac {n}{2^{5}-1}}={\frac {n}{31}}$
Period 6 ( 9 orbits ) for angles = ${\frac {n}{2^{6}-1}}={\frac {n}{63}}$, only numerators
Period = 7 for angles = ${\frac {n}{2^{7}-1}}={\frac {n}{127}}$
Period = 8 for angles = ${\frac {n}{2^{8}-1}}={\frac {n}{255}}$
Period = 9 for angles = ${\frac {n}{2^{9}-1}}={\frac {n}{511}}$
See also
* external ray for root points ( bond point) on the parameter plane:
** wake
** subwake
** island = midget = mini Mandelbrot set
* dynamic plane
** external rays that land on the parabolic fixed point . ( first angle is angle of the wake)

## preperiodic

Here denominator d of fraction r
    $r={\frac {n}{d}}$
is even:
    $d=2^{t}q$
and q is odd.
Here
* t is preperiod
Example orbits:
Preperiod 1 and period 1 for angles ${\frac {n}{2}}$
See
* Misiurewicz points on the parameter plane
* Dendrite Julia sets on the dynamic plane

## aperiodic

Compare
* Siegel disc
* Herman rings ( rational maps)

# Implementations

* integer:
** 2 integers ( numerator and denominator)
** rational number
*** mpq type from GMP library
* floating point
** double

## Forward

* Using 32bit signed int limits maximum preperiod to about 30
* Using double for fractions limits maximum number of accurate bits to about 53

### C using double numbers

* using double gives precision of 53 bits of binary number expansion (the number of bits of accuracy of double precision floating point)

### C using rational type mpq from GMP library ( arbitrary precision)

C function (using GMP library):
Compile:
run
result:

### Maxima CAS

* Maxima CAS function using numerator and denominator as an input
or using rational number as an input

### Haskell

Haskell function

### C++
## Inverse function of doubling map

Every angle α ∈ R/Z measured in turns has:
* one image = 2α mod 1 under doubling map
* "two preimages under the doubling map: α/2 and (α + 1)/2.". Inverse of doubling map is multivalued function.
In Maxima CAS:
Note that difference between these 2 preimages
    ${\frac {\alpha }{2}}-{\frac {\alpha +1}{2}}={\frac {1}{2}}$
is half a turn = 180 degrees = Pi radians.
Images and preimages under doubling map d :
| $\alpha$ | $d^{1}(\alpha )$ | $d^{-1}(\alpha )$ |
| ${\frac {1}{2}}$ | ${\frac {1}{1}}$ | $\left\{{\frac {1}{4}},{\frac {3}{4}}\right\}$ |
| ${\frac {1}{3}}$ | ${\frac {2}{3}}$ | $\left\{{\frac {1}{6}},{\frac {4}{6}}\right\}$ |
| ${\frac {1}{4}}$ | ${\frac {1}{2}}$ | $\left\{{\frac {1}{8}},{\frac {5}{8}}\right\}$ |
| ${\frac {1}{5}}$ | ${\frac {2}{5}}$ | $\left\{{\frac {1}{10}},{\frac {6}{10}}\right\}$ |
| ${\frac {1}{6}}$ | ${\frac {1}{3}}$ | $\left\{{\frac {1}{12}},{\frac {7}{12}}\right\}$ |
| ${\frac {1}{7}}$ | ${\frac {2}{7}}$ | $\left\{{\frac {1}{14}},{\frac {4}{7}}\right\}$ |

# Q&A
## analysis

* find expansion type
* find preperiod and period
* convert decimal fraction to binary expansion
* format the expansion

## How to find expansion type

Binary expansion of decimal fraction

## How to find preperiod and period ?

* Period and the doubling map
How to find the period of angle under doubling map
* visual
* numerical
** read period from denominator of decimal fraction ( reduced rational fraction m/n )
** find period/preperiod in the binary expansion ( binary sequence)
*** string matching algorithms, for instance, naive or brute-force search, Knuth-Morris-Pratt algorithm
*** discrete Fourier transform
** read it from the itinerary of angle under doubling map
Period of binary expansion of reduced rational fraction m/n is equal to the multiplicative order of 2 modulo n:
$Period_{2}(m/n)={ord}_{n}(2)$
* orbit of angle 5/31 under doubling map

### Haskell version

Haskell version
Conversion from an integer type (Int or Integer) to anything else is done by "fromIntegral". The target type is inferred automatically

## conversion

* Convert binary fraction to decimal ratio
* convert decimal fraction to binary
* knowledgedoor calculators

### Can all decimal fractions be converted exactly to binary?

Not all. Only those for which denominator is a power of 2 ( finite ) have exact decimal representation. "In every other case, there will be an error in the representation. The error's magnitude depends on the number of digits used to represent it."

### decimal to binary
## precision

What number type precision do I need for computing doubling map?
* "the doubling map loses one bit of precision with every iterate."
* storing the angle as an exact rational (e.g. mpq_t using libgmp), allows it to be accurate for more than 53 iterations (the number of bits of accuracy of double precision floating point). Convert to double only when needing to do sin and cos for finding the target point. Double is plenty accurate for target point. Claude Heiland-Allen

# See also

* binary fraction

# References

* ↑ On Combinatorial Types of Periodic Orbits of the Map x↦kx (mod Z). Part I: Realization Authors: Carsten L. Petersen, Saeed Zakeri
* ↑ chaos_and_doubling map by Mark McClure
* ↑ doubling map by Mark McClure
* ↑ Programowanie w systemie UNIX: GMP in polish wikibooks
* ↑ lavaurs' algorithm in Haskell with SVG output by Claude Heiland-Allen
* ↑ SYMBOLIC DYNAMICS AND SELF-SIMILAR GROUPS by VOLODYMYR NEKRASHEVYCH
* ↑ math stackexchange question: period-of-a-finite-binary-sequence
* ↑ lavaurs' algorithm in Haskell with SVG output by Claude Heiland-Allen
* ↑ binary-fraction calculator by Davide Borchia
* ↑ Chaos and Fractals by Mark McClure. 2.11 A few notes on computation
* ↑ fractalforums.org : parameter-external-ray-using-newton-method