1
$\begingroup$

If you want to convert a rational number into its continued fraction, what is the circuit depth of this process, in terms of the total number of bits of input?

I was reading through some notes which mentioned that the work being done while computing the continued fraction is basically the same as the work being done while computing a GCD. Are their circuit depths similar?

notes

$\endgroup$
6
  • 1
    $\begingroup$ Is your question assuming that the Euclidean algorithm has the optimal circuit depth for computing the GCD? Is that known? If not, it might be important to distinguish "optimal circuit depth for the Euclidean algorithm" vs "optimal circuit depth for computing the GCD". $\endgroup$
    – D.W.
    Commented Feb 6, 2020 at 23:09
  • $\begingroup$ @D.W. No, I was just stating that a valid answer could be of the form "yes this problem does reduce to GCD and also here is the best known depth for GCD". $\endgroup$ Commented Feb 7, 2020 at 0:15
  • $\begingroup$ Let me state it differently, then: the notes you point to don't say that the work is the same as done while computing a GCD, exactly. They say it is the same as the work that is done while using the Euclidean algorithm to compute a GCD. (There are other ways to compute a GCD.) It seems likely that the optimal circuit depth for computing the continued fraction is the same as the optimal circuit depth for implementing the Euclidean algorithm (you should be in a position to check if that's right), which is at least the optimal circuit depth for computing the GCD. Dunno if that helps. $\endgroup$
    – D.W.
    Commented Feb 7, 2020 at 2:11
  • $\begingroup$ What notion of circuit are you interested in? $\endgroup$ Commented Feb 7, 2020 at 3:51
  • $\begingroup$ @YuvalFilmus ANDs, ORs, and XORs with constant fan-in. Circuits you would imagine making when designing actual hardware. $\endgroup$ Commented Feb 7, 2020 at 11:44

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.