# Transitions needed for dividing two fixed integers

Let $Q$ be the set of states of the Turing Machine, $\Sigma$ be the alphabet, and $\{L,R,S\}$ be the left shift, right shift, and stay respectively.

A transition is an element of $Q \times \Sigma \times Q \times \Sigma \times \{L,R,S\}$ which can be read as current state, current symbol, next state, next symbol, movement direction.

For a Turing Machine I'm looking to understand how many transitions, or states since they are linearly related, are needed so that when I give integer $i \ge 0$ on the tape it outputs the $i^\text{th}$ digit after the decimal point(zero indexed) of $\frac{p}{q}$ for which $p$,$q$ are coprime. Assume it is in base $c$ and you only have the characters $0,1,\dots,c-1$ and blank. I imagine this is possible to do in $O(c\log q)$ states, but my best attempts(outlined below) only give me $O(cq)$. An example where $c=2$ and $\frac{p}{q}=\frac{1}{3}$ would be I want a binary Turing machine such that when given $10$ on the tape would output the $3^\text{rd}$ digit after the decimal point of $\frac{1}{3}$ which is $0$ and when given $110111$ would output the $56^\text{th}$ digit which is $1$.

Here is my way of doing it. For the purpose of this $\text{nt}(c,q)$ is the length of the non-terminating portion length of $\frac{p}{q}$ in base $c$, this is easily verified to be the same for all coprime $p$,$q$. Also define $\text{per}(c,q)$ as the length of the periodic portion of $\frac{p}{q}$ in base $c$

My basic idea was you check if it is less than $\text{nt}(c,q)$ and if so output that digit and halt, this takes $O(c\,\text{nt}(c,q))$ transitions. If it's not smaller subtract out $\text{nt}(c,q)$ which takes $O(c\lfloor \log \text{nt}(c,q) \rfloor)$ transitions. Then test for what the result is modulo $\text{per}(c,q)$ and output the appropriate digit. This takes $O(c\,\text{per}(c,q))$ transitions. Now remember that the worst case of $\text{per}(c,q)+\text{nt}(c,q)$ is $q-1$. Therefore the final transition complexity is $O(cq)$

A second idea I had was Newton's algorithm which I think would take $O(c\log q)$ transitions. The basic idea would be to output $p$,$q$,$.1$ to the tape in base $c$, convert to unary which takes $O(c)$ transitions then do multiplication and subtraction in unary which takes $O(1)$ transitions. Would this work?

• 1. I find your question hard to follow: "the tape" - what tape? are you asking about a Turing machine? "transitions" - please define what you mean by a transition. Please edit your question to be self-contained. 2. Ignore Turing machines for the moment, and imagine a real programming language. What's the best running time you know for division? Do you know how to do it in poly-log time? Hint: any such algorithm will lead immediately to a Turing machine. – D.W. Apr 30 '15 at 21:50
• @D.W. I edited the question, hopefully it is easier to understand now. 2. Time complexity doesn't necessarily equal state/transition complexity though, at least I don't think so. – ruler501 Apr 30 '15 at 22:04

Using a Turing machine compiler I wrote I devised a program to do this in $O(c\log(q))$ transitions assuming $0 \le p < q$. More precisely it does it in $2 \lfloor \log_2(q) \rfloor +\lfloor \log_2(p) \rfloor + C$ states for some value $C$. I'm sure the value I found(~$409$) wasn't optimal.

The actual program itself is too long to include here(totaling $3584+18\lfloor\log_2(q)\rfloor + 9\lfloor \log_2(p) \rfloor$ lines) Here is the program in my pseudo language for approximating 5/9, it can be compiled with the program found here. The syntax for the language is also found there.

xn=1,4
while i decr {
xnH=xn
a=xnH
a=a,0
t=0,1
while xnH decr {
p=9,4
while p decr {
incr(a)
}
incr(t)
}
two=a
two=two,2
two=two,0
first(two)
while a decr {
decr(two)
}
xnH=xn
b=two
b=b,0
while xnH pop {
b=b,1
xn=xn,1
incr(t)
}
pop(b)
xn=xn,1
while xn decr {
p=two
while p decr {
incr(b)
}
incr(t)
}
xn=b
incr(t)
}
xnH=xn
xnH=xnH,0
while xn decr {
p=5,3
while p decr {
incr(xnH)
}
incr(p)
}
incr(xn)


xnH holds the final value(the whole thing is assumed to be after the decimal point). It shouldn't be too hard to extract out a single digit from it(in $O(1)$ states). Also as a note even for small values of i this program takes quite a long time to execute.