Skip to main content
MathOverflow

Return to Answer

edited body
Source Link
Glorfindel
Glorfindel
  • 2.8k
  • 6
  • 28
  • 38

There is a simple algorithm because the minimal path from $A$ to $B$ using these operations must have a very constrained form.

First, an optimal sequence of $x+1$ and $x-1$ operations from $a$ to $b$ has clearly length $|a-b|$, i.e., it cannot mix operations of different singssigns.

Second, in an optimal path, no $x^2$ operation precedes any $\sqrt x$ operation. Indeed, if there were a subsequence $a,a^2,\dots,b^2,b$, where the $\dots$ are $x\pm1$ operations, we can replace it with just a sequence of $x\pm1$ operations. This shortens the sequence as $$2+|a^2-b^2|\ge2+|a-b|>|a-b|.$$

Third, if the optimal path contains a sequence of $x\pm1$ operations followed by $\sqrt x$, say a subsequence $a,\dots,b^2,b$, then WLOG $b^2$ is the nearest square to $a$. Indeed, let $b'=\lfloor\sqrt a\rceil$, where $\lfloor x\rceil:=\lfloor x+\frac12\rfloor$, and replace the subsequence with $a,\dots,b'^2,b',\dots,b$. This does not increase the sequence, as $$|a-b^2|\ge|a-b'^2|+|b-b'|:$$ if $a-b^2$ and $a-b'^2$ have the same sign, we have $|a-b^2|=|a-b'^2|+|b^2-b'^2|$. If, say, $b'^2<a<(b'+1)^2\le b^2$, we have $$\begin{align*} |a-b^2|&=|b^2-(b'+1)^2|+|(b'+1)^2-a|\\ &\ge|b-(b'+1)|+|b'^2-a|+1=|b-b'|+|b'^2-a|, \end{align*}$$ as $|b'^2-a|<|(b'+1)^2-a|$.

Thus, the optimal path from $A$ to $B$ looks as $$A_0,\dots,A_1^2,A_1,\dots,A_2^2,A_2,\dots,A_n,\dots,B_m,B_m^2,\dots,B_{m-1},B_{m-1}^2,\dots,B_0,$$ where $A_0=A$, $A_{i+1}=\lfloor\sqrt{A_i}\rceil$, $B_0=B$, $B_{j+1}=\lfloor\sqrt{B_j}\rceil$. The length $c_i$ of the subpath from $A$ to $A_i$ is given by $c_0=0$, $c_{i+1}=c_i+1+|A_i-A_{i+1}^2|$, and likewise, the length $d_i$ of the subpath from $B_i$ to $B$ is $d_0=0$, $d_{i+1}=d_i+1+|B_i-B_{i+1}^2|$, thus the total length is $l=c_n+d_m+|A_n-B_m|$.

We can compute the optimal length $l$ by calculating the sequences $A_i$ and $B_j$ as above, until reaching $A_N=1=B_M$, and then $$l=\min\{c_n+d_m+|A_n-B_m|:n\le N,m\le M\}.$$ Note that $N=O(\log\log A)$ and $M=O(\log\log B)$. We can further simplify the expression by noting that we do not have to consider all pairs $(n,m)$, but only those where $A_n$ and $B_m$ are neighbours in the sequence obtained by sorting $\{A_n:n\le N\}\cup\{B_m:m\le M\}$. Indeed, if, say, $A_n<B_k<B_m$, then $$B_m-A_n=(B_m-B_{k+1})+(B_{k+1}-B_k)+(B_k-A_n)\ge d_k-d_m+(B_k-A_n)$$ as $B_{k+1}-B_k>|B_{k+1}-B_k^2|$.

It follows that we can compute the optimal length with the following simple algorithm:

c := 0, l := |A - B|
while l > c do:
    if A < B then swap(A,B)
    A' := ⌊√A⌉
    c := c + 1 + |A-(A')^2|
    A := A'
    l := min (l, c + |A - B|)
output l

This computes the result with $O(\log\log A+\log\log B)$ arithmetic operations of total bit-complexity $O(M(\log A)+M(\log B))=O(\log A\log\log A+\log B\log\log B)$, where $M(n)=O(n\log n)$ is the complexity of $n$-bit multiplication.

There is a simple algorithm because the minimal path from $A$ to $B$ using these operations must have a very constrained form.

First, an optimal sequence of $x+1$ and $x-1$ operations from $a$ to $b$ has clearly length $|a-b|$, i.e., it cannot mix operations of different sings.

Second, in an optimal path, no $x^2$ operation precedes any $\sqrt x$ operation. Indeed, if there were a subsequence $a,a^2,\dots,b^2,b$, where the $\dots$ are $x\pm1$ operations, we can replace it with just a sequence of $x\pm1$ operations. This shortens the sequence as $$2+|a^2-b^2|\ge2+|a-b|>|a-b|.$$

Third, if the optimal path contains a sequence of $x\pm1$ operations followed by $\sqrt x$, say a subsequence $a,\dots,b^2,b$, then WLOG $b^2$ is the nearest square to $a$. Indeed, let $b'=\lfloor\sqrt a\rceil$, where $\lfloor x\rceil:=\lfloor x+\frac12\rfloor$, and replace the subsequence with $a,\dots,b'^2,b',\dots,b$. This does not increase the sequence, as $$|a-b^2|\ge|a-b'^2|+|b-b'|:$$ if $a-b^2$ and $a-b'^2$ have the same sign, we have $|a-b^2|=|a-b'^2|+|b^2-b'^2|$. If, say, $b'^2<a<(b'+1)^2\le b^2$, we have $$\begin{align*} |a-b^2|&=|b^2-(b'+1)^2|+|(b'+1)^2-a|\\ &\ge|b-(b'+1)|+|b'^2-a|+1=|b-b'|+|b'^2-a|, \end{align*}$$ as $|b'^2-a|<|(b'+1)^2-a|$.

Thus, the optimal path from $A$ to $B$ looks as $$A_0,\dots,A_1^2,A_1,\dots,A_2^2,A_2,\dots,A_n,\dots,B_m,B_m^2,\dots,B_{m-1},B_{m-1}^2,\dots,B_0,$$ where $A_0=A$, $A_{i+1}=\lfloor\sqrt{A_i}\rceil$, $B_0=B$, $B_{j+1}=\lfloor\sqrt{B_j}\rceil$. The length $c_i$ of the subpath from $A$ to $A_i$ is given by $c_0=0$, $c_{i+1}=c_i+1+|A_i-A_{i+1}^2|$, and likewise, the length $d_i$ of the subpath from $B_i$ to $B$ is $d_0=0$, $d_{i+1}=d_i+1+|B_i-B_{i+1}^2|$, thus the total length is $l=c_n+d_m+|A_n-B_m|$.

We can compute the optimal length $l$ by calculating the sequences $A_i$ and $B_j$ as above, until reaching $A_N=1=B_M$, and then $$l=\min\{c_n+d_m+|A_n-B_m|:n\le N,m\le M\}.$$ Note that $N=O(\log\log A)$ and $M=O(\log\log B)$. We can further simplify the expression by noting that we do not have to consider all pairs $(n,m)$, but only those where $A_n$ and $B_m$ are neighbours in the sequence obtained by sorting $\{A_n:n\le N\}\cup\{B_m:m\le M\}$. Indeed, if, say, $A_n<B_k<B_m$, then $$B_m-A_n=(B_m-B_{k+1})+(B_{k+1}-B_k)+(B_k-A_n)\ge d_k-d_m+(B_k-A_n)$$ as $B_{k+1}-B_k>|B_{k+1}-B_k^2|$.

It follows that we can compute the optimal length with the following simple algorithm:

c := 0, l := |A - B|
while l > c do:
    if A < B then swap(A,B)
    A' := ⌊√A⌉
    c := c + 1 + |A-(A')^2|
    A := A'
    l := min (l, c + |A - B|)
output l

This computes the result with $O(\log\log A+\log\log B)$ arithmetic operations of total bit-complexity $O(M(\log A)+M(\log B))=O(\log A\log\log A+\log B\log\log B)$, where $M(n)=O(n\log n)$ is the complexity of $n$-bit multiplication.

There is a simple algorithm because the minimal path from $A$ to $B$ using these operations must have a very constrained form.

First, an optimal sequence of $x+1$ and $x-1$ operations from $a$ to $b$ has clearly length $|a-b|$, i.e., it cannot mix operations of different signs.

Second, in an optimal path, no $x^2$ operation precedes any $\sqrt x$ operation. Indeed, if there were a subsequence $a,a^2,\dots,b^2,b$, where the $\dots$ are $x\pm1$ operations, we can replace it with just a sequence of $x\pm1$ operations. This shortens the sequence as $$2+|a^2-b^2|\ge2+|a-b|>|a-b|.$$

Third, if the optimal path contains a sequence of $x\pm1$ operations followed by $\sqrt x$, say a subsequence $a,\dots,b^2,b$, then WLOG $b^2$ is the nearest square to $a$. Indeed, let $b'=\lfloor\sqrt a\rceil$, where $\lfloor x\rceil:=\lfloor x+\frac12\rfloor$, and replace the subsequence with $a,\dots,b'^2,b',\dots,b$. This does not increase the sequence, as $$|a-b^2|\ge|a-b'^2|+|b-b'|:$$ if $a-b^2$ and $a-b'^2$ have the same sign, we have $|a-b^2|=|a-b'^2|+|b^2-b'^2|$. If, say, $b'^2<a<(b'+1)^2\le b^2$, we have $$\begin{align*} |a-b^2|&=|b^2-(b'+1)^2|+|(b'+1)^2-a|\\ &\ge|b-(b'+1)|+|b'^2-a|+1=|b-b'|+|b'^2-a|, \end{align*}$$ as $|b'^2-a|<|(b'+1)^2-a|$.

Thus, the optimal path from $A$ to $B$ looks as $$A_0,\dots,A_1^2,A_1,\dots,A_2^2,A_2,\dots,A_n,\dots,B_m,B_m^2,\dots,B_{m-1},B_{m-1}^2,\dots,B_0,$$ where $A_0=A$, $A_{i+1}=\lfloor\sqrt{A_i}\rceil$, $B_0=B$, $B_{j+1}=\lfloor\sqrt{B_j}\rceil$. The length $c_i$ of the subpath from $A$ to $A_i$ is given by $c_0=0$, $c_{i+1}=c_i+1+|A_i-A_{i+1}^2|$, and likewise, the length $d_i$ of the subpath from $B_i$ to $B$ is $d_0=0$, $d_{i+1}=d_i+1+|B_i-B_{i+1}^2|$, thus the total length is $l=c_n+d_m+|A_n-B_m|$.

We can compute the optimal length $l$ by calculating the sequences $A_i$ and $B_j$ as above, until reaching $A_N=1=B_M$, and then $$l=\min\{c_n+d_m+|A_n-B_m|:n\le N,m\le M\}.$$ Note that $N=O(\log\log A)$ and $M=O(\log\log B)$. We can further simplify the expression by noting that we do not have to consider all pairs $(n,m)$, but only those where $A_n$ and $B_m$ are neighbours in the sequence obtained by sorting $\{A_n:n\le N\}\cup\{B_m:m\le M\}$. Indeed, if, say, $A_n<B_k<B_m$, then $$B_m-A_n=(B_m-B_{k+1})+(B_{k+1}-B_k)+(B_k-A_n)\ge d_k-d_m+(B_k-A_n)$$ as $B_{k+1}-B_k>|B_{k+1}-B_k^2|$.

It follows that we can compute the optimal length with the following simple algorithm:

c := 0, l := |A - B|
while l > c do:
    if A < B then swap(A,B)
    A' := ⌊√A⌉
    c := c + 1 + |A-(A')^2|
    A := A'
    l := min (l, c + |A - B|)
output l

This computes the result with $O(\log\log A+\log\log B)$ arithmetic operations of total bit-complexity $O(M(\log A)+M(\log B))=O(\log A\log\log A+\log B\log\log B)$, where $M(n)=O(n\log n)$ is the complexity of $n$-bit multiplication.

further optimization
Source Link
Emil Jeřábek
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

There is a simple algorithm because the minimal path from $A$ to $B$ using these operations must have a very constrained form.

First, an optimal sequence of $x+1$ and $x-1$ operations from $a$ to $b$ has clearly length $|a-b|$, i.e., it cannot mix operations of different sings.

Second, in an optimal path, no $x^2$ operation precedes any $\sqrt x$ operation. Indeed, if there were a subsequence $a,a^2,\dots,b^2,b$, where the $\dots$ are $x\pm1$ operations, we can replace it with just a sequence of $x\pm1$ operations. This shortens the sequence as $$2+|a^2-b^2|\ge2+|a-b|>|a-b|.$$

Third, if the optimal path contains a sequence of $x\pm1$ operations followed by $\sqrt x$, say a subsequence $a,\dots,b^2,b$, then WLOG $b^2$ is the nearest square to $a$. Indeed, let $b'=\lfloor\sqrt a\rceil$, where $\lfloor x\rceil:=\lfloor x+\frac12\rfloor$, and replace the subsequence with $a,\dots,b'^2,b',\dots,b$. This does not increase the sequence, as $$|a-b^2|\ge|a-b'^2|+|b-b'|:$$ if $a-b^2$ and $a-b'^2$ have the same sign, we have $|a-b^2|=|a-b'^2|+|b^2-b'^2|$. If, say, $b'^2<a<(b'+1)^2\le b^2$, we have $$\begin{align*} |a-b^2|&=|b^2-(b'+1)^2|+|(b'+1)^2-a|\\ &\ge|b-(b'+1)|+|b'^2-a|+1=|b-b'|+|b'^2-a|, \end{align*}$$ as $|b'^2-a|<|(b'+1)^2-a|$.

Thus, the optimal path from $A$ to $B$ looks as $$A_0,\dots,A_1^2,A_1,\dots,A_2^2,A_2,\dots,A_n,\dots,B_m,B_m^2,\dots,B_{m-1},B_{m-1}^2,\dots,B_0,$$ where $A_0=A$, $A_{i+1}=\lfloor\sqrt{A_i}\rceil$, $B_0=B$, $B_{j+1}=\lfloor\sqrt{B_j}\rceil$. The length $c_i$ of the subpath from $A$ to $A_i$ is given by $c_0=0$, $c_{i+1}=c_i+1+|A_i-A_{i+1}^2|$, and likewise, the length $d_i$ of the subpath from $B_i$ to $B$ is $d_0=0$, $d_{i+1}=d_i+1+|B_i-B_{i+1}^2|$, thus the total length is $l=c_n+d_m+|A_n-B_m|$.

We can compute the optimal length $l$ by calculating the sequences $A_i$ and $B_j$ as above, until reaching $A_N=1=B_M$, and then $$l=\min\{c_n+d_m+|A_n-B_m|:n\le N,m\le M\}.$$ Note that $N=O(\log\log A)$ and $M=O(\log\log B)$. We can further simplify the expression by noting that we do not have to consider all pairs $(n,m)$, but only those where $A_n$ and $B_m$ are neighbours in the sequence obtained by sorting $\{A_n:n\le N\}\cup\{B_m:m\le M\}$. Indeed, if, say, $A_n<B_k<B_m$, then $$B_m-A_n=(B_m-B_{k+1})+(B_{k+1}-B_k)+(B_k-A_n)\ge d_k-d_m+(B_k-A_n)$$ as $B_{k+1}-B_k>|B_{k+1}-B_k^2|$.

It follows that we can compute the optimal length with the following simple algorithm:

c := 0, d := 0, l := |A - B|
while Al ≠> Bc do:
    if A < B then swap(A,B) and swap(c,d)
    A' := ⌊√A⌉
    c := c + 1 + |A-(A')^2|
    A := A'
    l := min (l, c + d + |A - B|)
output l

This computes the result with $O(\log\log A+\log\log B)$ arithmetic operations of total bit-complexity $O(M(\log A)+M(\log B))=O(\log A\log\log A+\log B\log\log B)$, where $M(n)=O(n\log n)$ is the complexity of $n$-bit multiplication.

There is a simple algorithm because the minimal path from $A$ to $B$ using these operations must have a very constrained form.

First, an optimal sequence of $x+1$ and $x-1$ operations from $a$ to $b$ has clearly length $|a-b|$, i.e., it cannot mix operations of different sings.

Second, in an optimal path, no $x^2$ operation precedes any $\sqrt x$ operation. Indeed, if there were a subsequence $a,a^2,\dots,b^2,b$, where the $\dots$ are $x\pm1$ operations, we can replace it with just a sequence of $x\pm1$ operations. This shortens the sequence as $$2+|a^2-b^2|\ge2+|a-b|>|a-b|.$$

Third, if the optimal path contains a sequence of $x\pm1$ operations followed by $\sqrt x$, say a subsequence $a,\dots,b^2,b$, then WLOG $b^2$ is the nearest square to $a$. Indeed, let $b'=\lfloor\sqrt a\rceil$, where $\lfloor x\rceil:=\lfloor x+\frac12\rfloor$, and replace the subsequence with $a,\dots,b'^2,b',\dots,b$. This does not increase the sequence, as $$|a-b^2|\ge|a-b'^2|+|b-b'|:$$ if $a-b^2$ and $a-b'^2$ have the same sign, we have $|a-b^2|=|a-b'^2|+|b^2-b'^2|$. If, say, $b'^2<a<(b'+1)^2\le b^2$, we have $$\begin{align*} |a-b^2|&=|b^2-(b'+1)^2|+|(b'+1)^2-a|\\ &\ge|b-(b'+1)|+|b'^2-a|+1=|b-b'|+|b'^2-a|, \end{align*}$$ as $|b'^2-a|<|(b'+1)^2-a|$.

Thus, the optimal path from $A$ to $B$ looks as $$A_0,\dots,A_1^2,A_1,\dots,A_2^2,A_2,\dots,A_n,\dots,B_m,B_m^2,\dots,B_{m-1},B_{m-1}^2,\dots,B_0,$$ where $A_0=A$, $A_{i+1}=\lfloor\sqrt{A_i}\rceil$, $B_0=B$, $B_{j+1}=\lfloor\sqrt{B_j}\rceil$. The length $c_i$ of the subpath from $A$ to $A_i$ is given by $c_0=0$, $c_{i+1}=c_i+1+|A_i-A_{i+1}^2|$, and likewise, the length $d_i$ of the subpath from $B_i$ to $B$ is $d_0=0$, $d_{i+1}=d_i+1+|B_i-B_{i+1}^2|$, thus the total length is $l=c_n+d_m+|A_n-B_m|$.

We can compute the optimal length $l$ by calculating the sequences $A_i$ and $B_j$ as above, until reaching $A_N=1=B_M$, and then $$l=\min\{c_n+d_m+|A_n-B_m|:n\le N,m\le M\}.$$ Note that $N=O(\log\log A)$ and $M=O(\log\log B)$. We can further simplify the expression by noting that we do not have to consider all pairs $(n,m)$, but only those where $A_n$ and $B_m$ are neighbours in the sequence obtained by sorting $\{A_n:n\le N\}\cup\{B_m:m\le M\}$. Indeed, if, say, $A_n<B_k<B_m$, then $$B_m-A_n=(B_m-B_{k+1})+(B_{k+1}-B_k)+(B_k-A_n)\ge d_k-d_m+(B_k-A_n)$$ as $B_{k+1}-B_k>|B_{k+1}-B_k^2|$.

It follows that we can compute the optimal length with the following simple algorithm:

c := 0, d := 0, l := |A - B|
while A ≠ B do:
    if A < B then swap(A,B) and swap(c,d)
    A' := ⌊√A⌉
    c := c + 1 + |A-(A')^2|
    A := A'
    l := min (l, c + d + |A - B|)
output l

This computes the result with $O(\log\log A+\log\log B)$ arithmetic operations of total bit-complexity $O(M(\log A)+M(\log B))=O(\log A\log\log A+\log B\log\log B)$, where $M(n)=O(n\log n)$ is the complexity of $n$-bit multiplication.

There is a simple algorithm because the minimal path from $A$ to $B$ using these operations must have a very constrained form.

First, an optimal sequence of $x+1$ and $x-1$ operations from $a$ to $b$ has clearly length $|a-b|$, i.e., it cannot mix operations of different sings.

Second, in an optimal path, no $x^2$ operation precedes any $\sqrt x$ operation. Indeed, if there were a subsequence $a,a^2,\dots,b^2,b$, where the $\dots$ are $x\pm1$ operations, we can replace it with just a sequence of $x\pm1$ operations. This shortens the sequence as $$2+|a^2-b^2|\ge2+|a-b|>|a-b|.$$

Third, if the optimal path contains a sequence of $x\pm1$ operations followed by $\sqrt x$, say a subsequence $a,\dots,b^2,b$, then WLOG $b^2$ is the nearest square to $a$. Indeed, let $b'=\lfloor\sqrt a\rceil$, where $\lfloor x\rceil:=\lfloor x+\frac12\rfloor$, and replace the subsequence with $a,\dots,b'^2,b',\dots,b$. This does not increase the sequence, as $$|a-b^2|\ge|a-b'^2|+|b-b'|:$$ if $a-b^2$ and $a-b'^2$ have the same sign, we have $|a-b^2|=|a-b'^2|+|b^2-b'^2|$. If, say, $b'^2<a<(b'+1)^2\le b^2$, we have $$\begin{align*} |a-b^2|&=|b^2-(b'+1)^2|+|(b'+1)^2-a|\\ &\ge|b-(b'+1)|+|b'^2-a|+1=|b-b'|+|b'^2-a|, \end{align*}$$ as $|b'^2-a|<|(b'+1)^2-a|$.

Thus, the optimal path from $A$ to $B$ looks as $$A_0,\dots,A_1^2,A_1,\dots,A_2^2,A_2,\dots,A_n,\dots,B_m,B_m^2,\dots,B_{m-1},B_{m-1}^2,\dots,B_0,$$ where $A_0=A$, $A_{i+1}=\lfloor\sqrt{A_i}\rceil$, $B_0=B$, $B_{j+1}=\lfloor\sqrt{B_j}\rceil$. The length $c_i$ of the subpath from $A$ to $A_i$ is given by $c_0=0$, $c_{i+1}=c_i+1+|A_i-A_{i+1}^2|$, and likewise, the length $d_i$ of the subpath from $B_i$ to $B$ is $d_0=0$, $d_{i+1}=d_i+1+|B_i-B_{i+1}^2|$, thus the total length is $l=c_n+d_m+|A_n-B_m|$.

We can compute the optimal length $l$ by calculating the sequences $A_i$ and $B_j$ as above, until reaching $A_N=1=B_M$, and then $$l=\min\{c_n+d_m+|A_n-B_m|:n\le N,m\le M\}.$$ Note that $N=O(\log\log A)$ and $M=O(\log\log B)$. We can further simplify the expression by noting that we do not have to consider all pairs $(n,m)$, but only those where $A_n$ and $B_m$ are neighbours in the sequence obtained by sorting $\{A_n:n\le N\}\cup\{B_m:m\le M\}$. Indeed, if, say, $A_n<B_k<B_m$, then $$B_m-A_n=(B_m-B_{k+1})+(B_{k+1}-B_k)+(B_k-A_n)\ge d_k-d_m+(B_k-A_n)$$ as $B_{k+1}-B_k>|B_{k+1}-B_k^2|$.

It follows that we can compute the optimal length with the following simple algorithm:

c := 0, l := |A - B|
while l > c do:
    if A < B then swap(A,B)
    A' := ⌊√A⌉
    c := c + 1 + |A-(A')^2|
    A := A'
    l := min (l, c + |A - B|)
output l

This computes the result with $O(\log\log A+\log\log B)$ arithmetic operations of total bit-complexity $O(M(\log A)+M(\log B))=O(\log A\log\log A+\log B\log\log B)$, where $M(n)=O(n\log n)$ is the complexity of $n$-bit multiplication.

Source Link
Emil Jeřábek
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

There is a simple algorithm because the minimal path from $A$ to $B$ using these operations must have a very constrained form.

First, an optimal sequence of $x+1$ and $x-1$ operations from $a$ to $b$ has clearly length $|a-b|$, i.e., it cannot mix operations of different sings.

Second, in an optimal path, no $x^2$ operation precedes any $\sqrt x$ operation. Indeed, if there were a subsequence $a,a^2,\dots,b^2,b$, where the $\dots$ are $x\pm1$ operations, we can replace it with just a sequence of $x\pm1$ operations. This shortens the sequence as $$2+|a^2-b^2|\ge2+|a-b|>|a-b|.$$

Third, if the optimal path contains a sequence of $x\pm1$ operations followed by $\sqrt x$, say a subsequence $a,\dots,b^2,b$, then WLOG $b^2$ is the nearest square to $a$. Indeed, let $b'=\lfloor\sqrt a\rceil$, where $\lfloor x\rceil:=\lfloor x+\frac12\rfloor$, and replace the subsequence with $a,\dots,b'^2,b',\dots,b$. This does not increase the sequence, as $$|a-b^2|\ge|a-b'^2|+|b-b'|:$$ if $a-b^2$ and $a-b'^2$ have the same sign, we have $|a-b^2|=|a-b'^2|+|b^2-b'^2|$. If, say, $b'^2<a<(b'+1)^2\le b^2$, we have $$\begin{align*} |a-b^2|&=|b^2-(b'+1)^2|+|(b'+1)^2-a|\\ &\ge|b-(b'+1)|+|b'^2-a|+1=|b-b'|+|b'^2-a|, \end{align*}$$ as $|b'^2-a|<|(b'+1)^2-a|$.

Thus, the optimal path from $A$ to $B$ looks as $$A_0,\dots,A_1^2,A_1,\dots,A_2^2,A_2,\dots,A_n,\dots,B_m,B_m^2,\dots,B_{m-1},B_{m-1}^2,\dots,B_0,$$ where $A_0=A$, $A_{i+1}=\lfloor\sqrt{A_i}\rceil$, $B_0=B$, $B_{j+1}=\lfloor\sqrt{B_j}\rceil$. The length $c_i$ of the subpath from $A$ to $A_i$ is given by $c_0=0$, $c_{i+1}=c_i+1+|A_i-A_{i+1}^2|$, and likewise, the length $d_i$ of the subpath from $B_i$ to $B$ is $d_0=0$, $d_{i+1}=d_i+1+|B_i-B_{i+1}^2|$, thus the total length is $l=c_n+d_m+|A_n-B_m|$.

We can compute the optimal length $l$ by calculating the sequences $A_i$ and $B_j$ as above, until reaching $A_N=1=B_M$, and then $$l=\min\{c_n+d_m+|A_n-B_m|:n\le N,m\le M\}.$$ Note that $N=O(\log\log A)$ and $M=O(\log\log B)$. We can further simplify the expression by noting that we do not have to consider all pairs $(n,m)$, but only those where $A_n$ and $B_m$ are neighbours in the sequence obtained by sorting $\{A_n:n\le N\}\cup\{B_m:m\le M\}$. Indeed, if, say, $A_n<B_k<B_m$, then $$B_m-A_n=(B_m-B_{k+1})+(B_{k+1}-B_k)+(B_k-A_n)\ge d_k-d_m+(B_k-A_n)$$ as $B_{k+1}-B_k>|B_{k+1}-B_k^2|$.

It follows that we can compute the optimal length with the following simple algorithm:

c := 0, d := 0, l := |A - B|
while A ≠ B do:
    if A < B then swap(A,B) and swap(c,d)
    A' := ⌊√A⌉
    c := c + 1 + |A-(A')^2|
    A := A'
    l := min (l, c + d + |A - B|)
output l

This computes the result with $O(\log\log A+\log\log B)$ arithmetic operations of total bit-complexity $O(M(\log A)+M(\log B))=O(\log A\log\log A+\log B\log\log B)$, where $M(n)=O(n\log n)$ is the complexity of $n$-bit multiplication.