All the basic arithmetic operations $\times,+,/,-$ can be parallelized. However continued fraction representation of a rational number is not parallelized. The process of Euclid's algorithm looks similar to division. In division we keep the divisor same and repeat by adding $0$s after the decimal. In Euclid's algorithm we change the divisor with remainder and dividend with divisor and repeat. Division has a period that could be very long (https://math.stackexchange.com/questions/377683/length-of-period-of-decimal-expansion-of-a-fraction) while continued fraction terminates in logarithmic steps. Despite this division is in $NC$ (https://en.wikipedia.org/wiki/NC_(complexity)#Problems_in_NC) while the short hand notation is difficult to parallelize.
- Is there a mathematical reason why this should be the case? I am not asking this would show $GCD$ is in $NC$ as an obstacle.
Secondly given $p,q$ coprimes we can form $r=\frac pq$ where $r\in\mathbb R$ is a decimal representation of $\frac pq$. Now given $r$ and $q$ we can find $p$ by multiplication.
- Is there a similar operation for $c$ the continued fraction representation of $\frac pq$ that is
a. properly defined directly
b. properly defined in $NC$
and gives $p$ from $c$ and $q$?