3
$\begingroup$

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

Improve this question
$\endgroup$
8
  • $\begingroup$ "the continued fraction representation of $q$..." Do you mean, the continued fraction representation of $p/q$? And what does "properly defined directly" mean? $\endgroup$
    – Gerry Myerson
    Commented Aug 11, 2019 at 2:54
  • $\begingroup$ $c=[c_1,\dots,c_n]$ where $\frac pq=c_1+\frac1{c_2+\frac1{\dots+\frac1{c_n}}}$ holds. $\endgroup$
    – Turbo
    Commented Aug 11, 2019 at 3:00
  • 1
    $\begingroup$ 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$? $\endgroup$
    – Gerry Myerson
    Commented Aug 11, 2019 at 3:03
  • 1
    $\begingroup$ 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$? $\endgroup$
    – Turbo
    Commented Aug 11, 2019 at 3:09
  • 1
    $\begingroup$ 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. $\endgroup$
    – Dror Speiser
    Commented Aug 11, 2019 at 10:04

0

Reset to default

You must log in to answer this question.