# Why does division parallelize but not continued fractions and is there an analog of multiplication to continued fractions?

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.

1. 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.

1. 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$$?

• "the continued fraction representation of $q$..." Do you mean, the continued fraction representation of $p/q$? And what does "properly defined directly" mean? – Gerry Myerson Aug 11 '19 at 2:54
• $c=[c_1,\dots,c_n]$ where $\frac pq=c_1+\frac1{c_2+\frac1{\dots+\frac1{c_n}}}$ holds. – 1.. Aug 11 '19 at 3:00
• I don't think that engages with my questions. It really looks like $c$ is the representation of $p/q$; are you sure you want to write that, no, it's the representation of $q$? – Gerry Myerson Aug 11 '19 at 3:03
• I mean we can lift it back to $r$ and get $p$ from $rq$ and can we avoid this indirect route? Is there a direct operation $c\diamond q=p$ where $\diamond$ is in $NC$? – 1.. Aug 11 '19 at 3:09
• You can do the above mod different primes in order to keep the integer sizes bounded, so that computing $p \pmod{r}$ is definitely in NC. Then, you need $O(n)$ different $r$'s. So distribute over about $O(n^2)$ processors, which is allowed. Since modular inversion is in NC, I'm sure that CRT is in NC. And this should answer your second question positively. – Dror Speiser Aug 11 '19 at 10:04