化簡平方根

Question 1

問題中的演算法非常低效：當然，除非原始整數是完全平方數。

本回答（按時間順序）：

一種模仿最簡單分解演算法的巨集方法，
使用 OP 中的演算法的可擴展方法。更新非常尷尬的是，作者並沒有理解OP的演算法，在找到了I諸如I^2divide之類的簡化之後N，他遞歸地進行了一次，但N<-N/I^2不明白演算法可以就此停止。（作為一個蒼白的藉口，他首先實現了「自下而上」的方式，這需要遞歸，與「自上而下」（效率較低）的方式相反）。答案因此更新，向所有慷慨信任的早期投票者致歉。

我再次更新（抱歉），因為我現在已經閱讀了更多的xintexpr.sty文檔，並且為了提高效率，我從切換i=sqrt(N)..1到到i=-sqrt(N)++（沒有--可用的，因此帶有減號的技巧）。前者預先產生整個floor(\sqrt{N})數字列表（sqrt意味著中的截斷平方根\xintiiexpr），後者是迭代器，不會預先產生內容。此外，前一種語法只能產生大約5000值（sqrt(N)..[-1]..1沒有這樣的限制，但仍會預先產生所有內容）。
更快（高中分解類型）演算法的可擴展實現，如方法 1 所示。

老實說，2.、3. 甚至 1. 可能會更好地完全使用\numexpr它們來處理更大的數字2^31，這有點牽強，用 10 位素數來處理數萬個數字需要時間除法得出結論它是無平方的...實現2. 有一個內在的限制，2^62因為平方根必須是一個 TeX 數字（由於內部的某些構造）。

\xintexpr在 2. 和 3. 中，我們將遞歸序列語法的可能性推到了合理範圍之外。記號有點麻煩。除此之外xintexpr.sty 1.2g是需要的，因為它改變了相關語法。

最後（2017）我還加入了 no-package numexpr only 可擴充方法。

第一種方法（我們改變演算法）

並不是說這是一個簡單的問題。谷歌搜尋顯示，顯然數學家目前認為找到整數的平方自由基可能與完全因式分解一樣困難：https://math.stackexchange.com/questions/171568/finding-the-radical-of-an-integer和https://math.stackexchange.com/questions/14667/square-free-integers-factorization。

這是一種模仿最簡單形式的分解演算法的方法（使用巨集）。

套件xintexpr僅用於允許輸入，例如 1e7或甚至表達式。它還會載入xinttools語法中使用的內容。

除此之外，所有操作都是透過xint.由於我們在範例中幾乎只處理數字，因此<2^31我們可以採用一種變體，其中所有操作都將使用 uniquely 完成\numexpr，自然會更快。

程式碼使用\xintiiDivision它同時計算商和餘數。這就是為什麼\xintAssign使用來將它們儲存到兩個巨集\A和中\B。此程式碼檢查是否\B消失以偵測可被 a 整除Q=P^2。

\documentclass[a4paper]{article}

\usepackage{geometry}

\usepackage{xintexpr}

\makeatletter
\def\Rsqrt@ {%
    \let\Nrad\N
    \def\Nroot {1}% 
% we will always have original N = \Nrad times \Nroot^2
% first we check powers of 2
    \def\P{2}%
    \def\Q{4}% \Q is always square of \P
    \xintloop
% try to divide \Nrad by 4. If possible, multiply \Nroot by 2
        \xintAssign\xintiiDivision{\Nrad}{\Q}\to \A\B
        \xintiiifZero{\B}
           {\let\Nrad\A
            \edef\Nroot{\xintiiMul{\Nroot}{\P}}% 
            \iftrue}
           {\iffalse}%
    \repeat
% try to divide \Nrad by 9=3^2, then by 25=5^2, etc...
% unfortunately we divide by all odd integers, but only odd prime
% integers would be really needed
    \def\P{3}%
    \xintloop
      \edef\Q{\xintiiSqr{\P}}%
      \xintiiifGt{\Q}{\Nrad}
         {\iffalse}%
         {\xintloop
             \xintAssign\xintiiDivision{\Nrad}{\Q}\to \A\B
             \xintiiifZero{\B}
                {\let\Nrad\A
                 \edef\Nroot{\xintiiMul{\P}{\Nroot}}% 
                 \iftrue}
                {\iffalse}%
          \repeat 
          \edef\P{\xintiiAdd{2}{\P}}%
          \iftrue
         }%
    \repeat
% at this stage \N = \Nrad times \Nroot^2
% and \Nrad is square-free.
    \xintiiifOne{\Nroot}{}{\Nroot}%
    \xintiiifOne{\Nrad} {}{\sqrt{\Nrad}}%
}%

\newcommand* \Rsqrt[1]{%
   \begingroup
     \edef\N{\xinttheiexpr #1\relax}%
     \xintiiifSgn \N
        {\pm\edef\N{\xintiiAbs{\N}}\xintiiifOne\N{}{\Rsqrt@}i}
        {0}
        {\xintiiifOne \N{1}{\Rsqrt@}}
   \endgroup
}

\makeatother
\usepackage{multicol}

\begin{document}

\parindent0pt\def\columnseprule{.4pt}%

% testing
% \begin{multicols}{4}
% \xintFor* #1 in {\xintSeq {10000}{10100}}\do
%        {$\sqrt{#1}=\Rsqrt{#1}$\par}
% \end{multicols}

% $\Rsqrt{-10}, \Rsqrt{-1}, \Rsqrt{-16}$

$\Rsqrt {1e6}, \Rsqrt {1e7}, \Rsqrt{1e21}$

\pdfsetrandomseed 123456789

\begin{multicols}{3}
\xintiloop [1+1]
    \edef\Z {\xinttheiiexpr 
             (\pdfuniformdeviate 1000)^2
             *\pdfuniformdeviate 1000\relax }%
    $\sqrt{\Z}=\Rsqrt{\Z}$\par
\ifnum\xintiloopindex<50
\repeat
\end{multicols}
    
\end{document}

第二種方法（與OP中的演算法相同，可擴展實作）

用原來的演算法。這裡我們定義了\ExtractRadical哪個可擴展地A,B返回N=A^2 B。不可擴展的包裝器\Rsqrt從上述更快的方法中循環生成，區分負數或A\sqrt{B}的情況。NN=0, 1

我添加了程式碼註解來解釋實作。早期版本非常蹩腳（請參閱答案頂部），並且還需要額外的版本，xintexpr 1.2g但現在不再是這樣了。

\documentclass[a4paper]{article}

\usepackage{geometry}

\usepackage{xintexpr}

% Aim: given N find largest I such as I^2 divides N.
% Then compute J=N/I^2 and print I\sqrt{J}.

% Algorithm: compute first truncated square root Imax of N.
% With I = Imax try to divide N by I^2, if it does not work
% repeat with I replaced by I-1 and so on. 
% As soon as it works the seeked-for I has been found.

% **** Notice: embarrassingly the author of this answer initially continued
% **** the algorithm recursively with N<-N/I^2, which was very stupid, but
% **** explainable from the fact that he had implemented first another (much
% **** faster) algorithm which divided not from the top down, but from the
% **** bottom up.

% The code is far simpler now. And it does not require xintexpr 1.2g anymore,
% earlier versions of xintexpr.sty work, too.

% The iteration over i used Imax..1 syntax which requires Imax 
% to be <2^31. Else we could use Imax..[-1]..1, but we don't
% really consider realistic to iterate over 2^31 or more values !

% After an update we use (-Imax)++ syntax; this also requires Imax<2^31.

\def\ExtractRadical #1{%
  \xinttheiiexpr 
  subs(
  % we return I, #1//I^2 where I is biggest integer such as I^2 divides #1.
     (I, #1//I^2), 
  % The I is computed via the "seq" here. Theoretically this "seq" 
  % evaluates as many values as the last list indicates.
  % But here we omit all i's such that i^2 does not divide #1
  % and as soon as we have found one, we stop here and now by 
  % "break". We work topdown, at the worst I=1.
% The i=A..B syntax pre-generates all values, which is wasteful
% and limited to about at most 5000 values.
%       I=seq((#1/:i^2)?{omit}{break(i)}, i=sqrt(#1)..1)
% On the contrary the N++ syntax does not pre-generate anything.
       I=seq((#1/:i^2)?{omit}{break(-i)}, i=-sqrt(#1)++)
% There is currently no "n--" only "n++", thus we tricked with a minus sign.
      )
  \relax
}

\makeatletter

\def\Rsqrt@ {\expandafter\Rsqrt@@\romannumeral-`0\ExtractRadical\N,}

% The #2#3 trick is to get rid of a space after the comma
% because \ExtractRadical does \xinttheiiexpr which in case
% of comma separated values on output always inserts such a space.
% Naturally as the typesetting is in math mode the space is
% not a real problem (it is not a problem either in \xintiiifOne 
% as here its argument is already expanded anyhow).
\def\Rsqrt@@ #1,#2#3,{\xintiiifOne{#1}{}{#1}\xintiiifOne{#2#3}{}{\sqrt{#2#3}}}

\newcommand* \Rsqrt[1]{%
   \begingroup
     \edef\N{\xinttheiexpr #1\relax}%
     \xintiiifSgn \N
        {\pm\edef\N{\xintiiAbs{\N}}\xintiiifOne\N{}{\Rsqrt@}i}
        {0}
        {\xintiiifOne \N{1}{\Rsqrt@}}
   \endgroup
 }

\makeatother
\usepackage{multicol}

\begin{document}

\parindent0pt\def\columnseprule{.4pt}%

% testing

\begin{multicols}{4}
\xintFor* #1 in {\xintSeq {10000}{10099}}\do
       {$\sqrt{#1}=\Rsqrt{#1}$\par}
\end{multicols}

% $\Rsqrt{-10}, \Rsqrt{-1}, \Rsqrt{-16}$

$\Rsqrt {1e6}, \Rsqrt {1e7}$%, 

% this one does not work because 10^10.5 > 2^31 causes an arithmetic
% overflow in the "sqrt(J)..1" part. 
% It would not overflow with "sqrt(J)..[-1]..1"
% but then we can wait long time ... 
% from 31622776601 downto
%      10000000000 that's a lot of iterations !
%$\Rsqrt{1e21}$
% The update uses n++ syntax, but this also requires abs(n) to be <2^31
% hence the same remark applies: a "Number too big" error is generated.
% Better actually than to wait the completion of 21622776601 iterations ;-)


% \stop

\pdfsetrandomseed 123456789

% we try with smaller numbers... 1000 replaced by 100...
\begin{multicols}{3}
\xintiloop [1+1]
    \edef\Z {\xinttheiiexpr 
             (\pdfuniformdeviate 100)^2
             *\pdfuniformdeviate 100\relax }%
    $\sqrt{\Z}=\Rsqrt{\Z}$\par
\ifnum\xintiloopindex<51
\repeat
\end{multicols}

\end{document}

第三種方法：同樣是更快的演算法，但可擴展。

按照 ala 的方式編寫程式碼會更合理\numexpr。詳細內容請見程式碼註解。這個範例現在有 51 個隨機範例，有趣的是，缺少的一個（來自第一種方法）結果是一個隨機正方形（pdftex 隨機數產生器的隨機種子設定為123456789）。

\documentclass[a4paper]{article}

\usepackage{geometry}

\usepackage{xintexpr}[2016/03/19]%
% needs xintexpr 1.2g due to 
%  - changed meaning of iter
%  - shift by 1 in [L][n] syntax


% syntax \ExtractRadical {N or <integer expression>} expands to "A, B" with
% N=A^2 B, B square-free
% Algorithm:
% main variable a triple (P, I, J) where
%  - always N = I^2 J
%  - J's prime factors < P have multiplicity one.
% START: (2, 1, N)
% ITER:  (P, I, J)
         % Q=P^2
         % is Q > J ?
         %   - yes: STOP(I, J)
         %   - no:
         %         does Q divide J ?
         %         - yes: I<-I*P, J<-J/Q and repeat until Q does not divide J
         %         - no; continue with (P+2, I, J). Except if P=2 then we go
         %                      on with P=3.
% Also works with N=0 (produces 1, 0) and with N=1 (produces 1, 1)
%

\newcommand*\ExtractRadical [1]{%
  \xinttheiiexpr 
  iter (2, 1, #1; % starting triple P=2, I=1, J=N
  subs(subs(subs(subs(
  % apart from Q=P^2, these substitutions are mainly because [@][n] syntax
  % is cumbersome; and inefficient as it allows n to be itself a complicated
  % expression, hence does some rather unneeded parsing here of n= 0, 1, 2.
  % We really need some better syntax like iter(P=2, I=1, J=#1;...) and then
  % work with P, I, J standing for the last values.
  % Or at least something like subs(..., (Q, P, I, J)=(...)).
  % (not yet with xintexpr 1.2g). 
  (Q>J)?
      {break(I, J)}
      {(J/:Q)?
          {(n)?{P+2}{3}, I, J}
      % must use parentheses here: ([@][1]). Else ]/: will confuse parser.
      % I could have used again subs, but well. 
          {iter(P*I,J//Q;(([@][1])/:Q)?{break((n)?{P+2}{3},@)}
                                       {(P*[@][0],([@][1])//Q)},e=1++)
          }
      }
  , Q=P^2), P=[@][0]), I=[@][1]), J=[@][2]), n=0++)
    \relax
}             
                  
\makeatletter
\def\Rsqrt@ {\expandafter\Rsqrt@@\romannumeral-`0\ExtractRadical\N,}

\def\Rsqrt@@ #1,#2,{\xintiiifOne{#1}{}{#1}\xintiiifOne{#2}{}{\sqrt{#2}}}

\newcommand* \Rsqrt[1]{%
   \begingroup
     \edef\N{\xinttheiexpr #1\relax}%
     \xintiiifSgn \N
        {\pm\edef\N{\xintiiAbs{\N}}\xintiiifOne\N{}{\Rsqrt@}i}
        {0}
        {\xintiiifOne \N{1}{\Rsqrt@}}
   \endgroup
 }

\makeatother
\usepackage{multicol}

\begin{document}

\parindent0pt\def\columnseprule{.4pt}%

% testing

% \xintFor* #1 in {\xintSeq {0}{50}}\do 
% {\ExtractRadical {#1}\par}

% \ExtractRadical {128}

% \ExtractRadical {1024}
% \stop

% $\Rsqrt{5000}$

% \stop

% \begin{multicols}{4}
% \xintFor* #1 in {\xintSeq {10000}{10099}}\do
%        {$\sqrt{#1}=\Rsqrt{#1}$\par}
% \end{multicols}

$\Rsqrt{-10}, \Rsqrt{-1}, \Rsqrt{-16}$

$\Rsqrt {1e6}, \Rsqrt {1e7}, \Rsqrt {1e21}$%, 

\pdfsetrandomseed 123456789

\begin{multicols}{3}
\xintiloop [1+1]
    \edef\Z {\xinttheiiexpr 
             (\pdfuniformdeviate 1000)^2
             *\pdfuniformdeviate 1000\relax }%
    $\sqrt{\Z}=\Rsqrt{\Z}$\par
\ifnum\xintiloopindex<51
\repeat
\end{multicols}

\end{document}

更新（2017）。

如果需要的話，這裡是無包可擴充巨集。它擴展到I,J原來的位置N並且I**2 times J沒有J正方形。僅使用\numexpr.僅限於<2**31整數。從低到大進行，與初等因式分解方法相同。停止標準應該改進，下面的評論也適用於此。

\makeatletter

\newcommand\ExtractRadical[1]{%
    \romannumeral0%
    \expandafter
    \ExtractRadical@two@i\expandafter1\expandafter,\the\numexpr#1.%
}%
\def\ExtractRadical@two@i #1,#2.{%
    \ifnum4>#2 \expandafter\ExtractRadical@two@done\fi
    \expandafter\ExtractRadical@two@ii\the\numexpr#2/4;#1,#2.%
}%
\edef\ExtractRadical@two@done #1;#2,#3.%
    {\space#2,#3}% (not sole #2 for readability)
\def\ExtractRadical@two@ii #1;#2,#3.{%
    \ifnum\numexpr#1*4=#3 
      \expandafter\@firstoftwo
    \else
      \expandafter\@secondoftwo
    \fi
   {\expandafter\ExtractRadical@two@i\the\numexpr2*#2,#1.}%
   {\ExtractRadical@i 3;#2,#3.}%
}%
\def\ExtractRadical@i #1;{%
    \expandafter\ExtractRadical@ii\the\numexpr#1*#1.#1;%
}%
\def\ExtractRadical@ii #1.#2;#3,#4.{%
    \ifnum#1>#4 \expandafter\ExtractRadical@done\fi
    \expandafter\ExtractRadical@iii\the\numexpr#4/#1.#1;#4.#2;#3.%
}%
\def\ExtractRadical@iii #1.#2;#3.{%
    \ifnum\numexpr#1*#2=#3
      \expandafter\@firstoftwo
    \else
      \expandafter\@secondoftwo
    \fi
    \ExtractRadical@update
    \ExtractRadical@next
    #1.#2;#3.%
}%
\def\ExtractRadical@update #1.#2;#3.#4;#5.{%
    \expandafter\ExtractRadical@ii
    \the\numexpr#2\expandafter.%
    \the\numexpr#4\expandafter;%
    \the\numexpr#4*#5,#1.%
}%
\def\ExtractRadical@next #1.#2;#3.#4;#5.{%
    \expandafter\ExtractRadical@i\the\numexpr2+#4;#5,#3.%
}%
\edef\ExtractRadical@done #1;#2.#3;#4.{\space#4,#2}%

\makeatother

Answer

問題中的演算法非常低效：當然，除非原始整數是完全平方數。

本回答（按時間順序）：

一種模仿最簡單分解演算法的巨集方法，
使用 OP 中的演算法的可擴展方法。更新非常尷尬的是，作者並沒有理解OP的演算法，在找到了I諸如I^2divide之類的簡化之後N，他遞歸地進行了一次，但N<-N/I^2不明白演算法可以就此停止。（作為一個蒼白的藉口，他首先實現了「自下而上」的方式，這需要遞歸，與「自上而下」（效率較低）的方式相反）。答案因此更新，向所有慷慨信任的早期投票者致歉。

我再次更新（抱歉），因為我現在已經閱讀了更多的xintexpr.sty文檔，並且為了提高效率，我從切換i=sqrt(N)..1到到i=-sqrt(N)++（沒有--可用的，因此帶有減號的技巧）。前者預先產生整個floor(\sqrt{N})數字列表（sqrt意味著中的截斷平方根\xintiiexpr），後者是迭代器，不會預先產生內容。此外，前一種語法只能產生大約5000值（sqrt(N)..[-1]..1沒有這樣的限制，但仍會預先產生所有內容）。
更快（高中分解類型）演算法的可擴展實現，如方法 1 所示。

老實說，2.、3. 甚至 1. 可能會更好地完全使用\numexpr它們來處理更大的數字2^31，這有點牽強，用 10 位素數來處理數萬個數字需要時間除法得出結論它是無平方的...實現2. 有一個內在的限制，2^62因為平方根必須是一個 TeX 數字（由於內部的某些構造）。

\xintexpr在 2. 和 3. 中，我們將遞歸序列語法的可能性推到了合理範圍之外。記號有點麻煩。除此之外xintexpr.sty 1.2g是需要的，因為它改變了相關語法。

最後（2017）我還加入了 no-package numexpr only 可擴充方法。

第一種方法（我們改變演算法）

並不是說這是一個簡單的問題。谷歌搜尋顯示，顯然數學家目前認為找到整數的平方自由基可能與完全因式分解一樣困難：https://math.stackexchange.com/questions/171568/finding-the-radical-of-an-integer和https://math.stackexchange.com/questions/14667/square-free-integers-factorization。

這是一種模仿最簡單形式的分解演算法的方法（使用巨集）。

套件xintexpr僅用於允許輸入，例如 1e7或甚至表達式。它還會載入xinttools語法中使用的內容。

除此之外，所有操作都是透過xint.由於我們在範例中幾乎只處理數字，因此<2^31我們可以採用一種變體，其中所有操作都將使用 uniquely 完成\numexpr，自然會更快。

程式碼使用\xintiiDivision它同時計算商和餘數。這就是為什麼\xintAssign使用來將它們儲存到兩個巨集\A和中\B。此程式碼檢查是否\B消失以偵測可被 a 整除Q=P^2。

\documentclass[a4paper]{article}

\usepackage{geometry}

\usepackage{xintexpr}

\makeatletter
\def\Rsqrt@ {%
    \let\Nrad\N
    \def\Nroot {1}% 
% we will always have original N = \Nrad times \Nroot^2
% first we check powers of 2
    \def\P{2}%
    \def\Q{4}% \Q is always square of \P
    \xintloop
% try to divide \Nrad by 4. If possible, multiply \Nroot by 2
        \xintAssign\xintiiDivision{\Nrad}{\Q}\to \A\B
        \xintiiifZero{\B}
           {\let\Nrad\A
            \edef\Nroot{\xintiiMul{\Nroot}{\P}}% 
            \iftrue}
           {\iffalse}%
    \repeat
% try to divide \Nrad by 9=3^2, then by 25=5^2, etc...
% unfortunately we divide by all odd integers, but only odd prime
% integers would be really needed
    \def\P{3}%
    \xintloop
      \edef\Q{\xintiiSqr{\P}}%
      \xintiiifGt{\Q}{\Nrad}
         {\iffalse}%
         {\xintloop
             \xintAssign\xintiiDivision{\Nrad}{\Q}\to \A\B
             \xintiiifZero{\B}
                {\let\Nrad\A
                 \edef\Nroot{\xintiiMul{\P}{\Nroot}}% 
                 \iftrue}
                {\iffalse}%
          \repeat 
          \edef\P{\xintiiAdd{2}{\P}}%
          \iftrue
         }%
    \repeat
% at this stage \N = \Nrad times \Nroot^2
% and \Nrad is square-free.
    \xintiiifOne{\Nroot}{}{\Nroot}%
    \xintiiifOne{\Nrad} {}{\sqrt{\Nrad}}%
}%

\newcommand* \Rsqrt[1]{%
   \begingroup
     \edef\N{\xinttheiexpr #1\relax}%
     \xintiiifSgn \N
        {\pm\edef\N{\xintiiAbs{\N}}\xintiiifOne\N{}{\Rsqrt@}i}
        {0}
        {\xintiiifOne \N{1}{\Rsqrt@}}
   \endgroup
}

\makeatother
\usepackage{multicol}

\begin{document}

\parindent0pt\def\columnseprule{.4pt}%

% testing
% \begin{multicols}{4}
% \xintFor* #1 in {\xintSeq {10000}{10100}}\do
%        {$\sqrt{#1}=\Rsqrt{#1}$\par}
% \end{multicols}

% $\Rsqrt{-10}, \Rsqrt{-1}, \Rsqrt{-16}$

$\Rsqrt {1e6}, \Rsqrt {1e7}, \Rsqrt{1e21}$

\pdfsetrandomseed 123456789

\begin{multicols}{3}
\xintiloop [1+1]
    \edef\Z {\xinttheiiexpr 
             (\pdfuniformdeviate 1000)^2
             *\pdfuniformdeviate 1000\relax }%
    $\sqrt{\Z}=\Rsqrt{\Z}$\par
\ifnum\xintiloopindex<50
\repeat
\end{multicols}
    
\end{document}

第二種方法（與OP中的演算法相同，可擴展實作）

用原來的演算法。這裡我們定義了\ExtractRadical哪個可擴展地A,B返回N=A^2 B。不可擴展的包裝器\Rsqrt從上述更快的方法中循環生成，區分負數或A\sqrt{B}的情況。NN=0, 1

我添加了程式碼註解來解釋實作。早期版本非常蹩腳（請參閱答案頂部），並且還需要額外的版本，xintexpr 1.2g但現在不再是這樣了。

\documentclass[a4paper]{article}

\usepackage{geometry}

\usepackage{xintexpr}

% Aim: given N find largest I such as I^2 divides N.
% Then compute J=N/I^2 and print I\sqrt{J}.

% Algorithm: compute first truncated square root Imax of N.
% With I = Imax try to divide N by I^2, if it does not work
% repeat with I replaced by I-1 and so on. 
% As soon as it works the seeked-for I has been found.

% **** Notice: embarrassingly the author of this answer initially continued
% **** the algorithm recursively with N<-N/I^2, which was very stupid, but
% **** explainable from the fact that he had implemented first another (much
% **** faster) algorithm which divided not from the top down, but from the
% **** bottom up.

% The code is far simpler now. And it does not require xintexpr 1.2g anymore,
% earlier versions of xintexpr.sty work, too.

% The iteration over i used Imax..1 syntax which requires Imax 
% to be <2^31. Else we could use Imax..[-1]..1, but we don't
% really consider realistic to iterate over 2^31 or more values !

% After an update we use (-Imax)++ syntax; this also requires Imax<2^31.

\def\ExtractRadical #1{%
  \xinttheiiexpr 
  subs(
  % we return I, #1//I^2 where I is biggest integer such as I^2 divides #1.
     (I, #1//I^2), 
  % The I is computed via the "seq" here. Theoretically this "seq" 
  % evaluates as many values as the last list indicates.
  % But here we omit all i's such that i^2 does not divide #1
  % and as soon as we have found one, we stop here and now by 
  % "break". We work topdown, at the worst I=1.
% The i=A..B syntax pre-generates all values, which is wasteful
% and limited to about at most 5000 values.
%       I=seq((#1/:i^2)?{omit}{break(i)}, i=sqrt(#1)..1)
% On the contrary the N++ syntax does not pre-generate anything.
       I=seq((#1/:i^2)?{omit}{break(-i)}, i=-sqrt(#1)++)
% There is currently no "n--" only "n++", thus we tricked with a minus sign.
      )
  \relax
}

\makeatletter

\def\Rsqrt@ {\expandafter\Rsqrt@@\romannumeral-`0\ExtractRadical\N,}

% The #2#3 trick is to get rid of a space after the comma
% because \ExtractRadical does \xinttheiiexpr which in case
% of comma separated values on output always inserts such a space.
% Naturally as the typesetting is in math mode the space is
% not a real problem (it is not a problem either in \xintiiifOne 
% as here its argument is already expanded anyhow).
\def\Rsqrt@@ #1,#2#3,{\xintiiifOne{#1}{}{#1}\xintiiifOne{#2#3}{}{\sqrt{#2#3}}}

\newcommand* \Rsqrt[1]{%
   \begingroup
     \edef\N{\xinttheiexpr #1\relax}%
     \xintiiifSgn \N
        {\pm\edef\N{\xintiiAbs{\N}}\xintiiifOne\N{}{\Rsqrt@}i}
        {0}
        {\xintiiifOne \N{1}{\Rsqrt@}}
   \endgroup
 }

\makeatother
\usepackage{multicol}

\begin{document}

\parindent0pt\def\columnseprule{.4pt}%

% testing

\begin{multicols}{4}
\xintFor* #1 in {\xintSeq {10000}{10099}}\do
       {$\sqrt{#1}=\Rsqrt{#1}$\par}
\end{multicols}

% $\Rsqrt{-10}, \Rsqrt{-1}, \Rsqrt{-16}$

$\Rsqrt {1e6}, \Rsqrt {1e7}$%, 

% this one does not work because 10^10.5 > 2^31 causes an arithmetic
% overflow in the "sqrt(J)..1" part. 
% It would not overflow with "sqrt(J)..[-1]..1"
% but then we can wait long time ... 
% from 31622776601 downto
%      10000000000 that's a lot of iterations !
%$\Rsqrt{1e21}$
% The update uses n++ syntax, but this also requires abs(n) to be <2^31
% hence the same remark applies: a "Number too big" error is generated.
% Better actually than to wait the completion of 21622776601 iterations ;-)


% \stop

\pdfsetrandomseed 123456789

% we try with smaller numbers... 1000 replaced by 100...
\begin{multicols}{3}
\xintiloop [1+1]
    \edef\Z {\xinttheiiexpr 
             (\pdfuniformdeviate 100)^2
             *\pdfuniformdeviate 100\relax }%
    $\sqrt{\Z}=\Rsqrt{\Z}$\par
\ifnum\xintiloopindex<51
\repeat
\end{multicols}

\end{document}

第三種方法：同樣是更快的演算法，但可擴展。

按照 ala 的方式編寫程式碼會更合理\numexpr。詳細內容請見程式碼註解。這個範例現在有 51 個隨機範例，有趣的是，缺少的一個（來自第一種方法）結果是一個隨機正方形（pdftex 隨機數產生器的隨機種子設定為123456789）。

\documentclass[a4paper]{article}

\usepackage{geometry}

\usepackage{xintexpr}[2016/03/19]%
% needs xintexpr 1.2g due to 
%  - changed meaning of iter
%  - shift by 1 in [L][n] syntax


% syntax \ExtractRadical {N or <integer expression>} expands to "A, B" with
% N=A^2 B, B square-free
% Algorithm:
% main variable a triple (P, I, J) where
%  - always N = I^2 J
%  - J's prime factors < P have multiplicity one.
% START: (2, 1, N)
% ITER:  (P, I, J)
         % Q=P^2
         % is Q > J ?
         %   - yes: STOP(I, J)
         %   - no:
         %         does Q divide J ?
         %         - yes: I<-I*P, J<-J/Q and repeat until Q does not divide J
         %         - no; continue with (P+2, I, J). Except if P=2 then we go
         %                      on with P=3.
% Also works with N=0 (produces 1, 0) and with N=1 (produces 1, 1)
%

\newcommand*\ExtractRadical [1]{%
  \xinttheiiexpr 
  iter (2, 1, #1; % starting triple P=2, I=1, J=N
  subs(subs(subs(subs(
  % apart from Q=P^2, these substitutions are mainly because [@][n] syntax
  % is cumbersome; and inefficient as it allows n to be itself a complicated
  % expression, hence does some rather unneeded parsing here of n= 0, 1, 2.
  % We really need some better syntax like iter(P=2, I=1, J=#1;...) and then
  % work with P, I, J standing for the last values.
  % Or at least something like subs(..., (Q, P, I, J)=(...)).
  % (not yet with xintexpr 1.2g). 
  (Q>J)?
      {break(I, J)}
      {(J/:Q)?
          {(n)?{P+2}{3}, I, J}
      % must use parentheses here: ([@][1]). Else ]/: will confuse parser.
      % I could have used again subs, but well. 
          {iter(P*I,J//Q;(([@][1])/:Q)?{break((n)?{P+2}{3},@)}
                                       {(P*[@][0],([@][1])//Q)},e=1++)
          }
      }
  , Q=P^2), P=[@][0]), I=[@][1]), J=[@][2]), n=0++)
    \relax
}             
                  
\makeatletter
\def\Rsqrt@ {\expandafter\Rsqrt@@\romannumeral-`0\ExtractRadical\N,}

\def\Rsqrt@@ #1,#2,{\xintiiifOne{#1}{}{#1}\xintiiifOne{#2}{}{\sqrt{#2}}}

\newcommand* \Rsqrt[1]{%
   \begingroup
     \edef\N{\xinttheiexpr #1\relax}%
     \xintiiifSgn \N
        {\pm\edef\N{\xintiiAbs{\N}}\xintiiifOne\N{}{\Rsqrt@}i}
        {0}
        {\xintiiifOne \N{1}{\Rsqrt@}}
   \endgroup
 }

\makeatother
\usepackage{multicol}

\begin{document}

\parindent0pt\def\columnseprule{.4pt}%

% testing

% \xintFor* #1 in {\xintSeq {0}{50}}\do 
% {\ExtractRadical {#1}\par}

% \ExtractRadical {128}

% \ExtractRadical {1024}
% \stop

% $\Rsqrt{5000}$

% \stop

% \begin{multicols}{4}
% \xintFor* #1 in {\xintSeq {10000}{10099}}\do
%        {$\sqrt{#1}=\Rsqrt{#1}$\par}
% \end{multicols}

$\Rsqrt{-10}, \Rsqrt{-1}, \Rsqrt{-16}$

$\Rsqrt {1e6}, \Rsqrt {1e7}, \Rsqrt {1e21}$%, 

\pdfsetrandomseed 123456789

\begin{multicols}{3}
\xintiloop [1+1]
    \edef\Z {\xinttheiiexpr 
             (\pdfuniformdeviate 1000)^2
             *\pdfuniformdeviate 1000\relax }%
    $\sqrt{\Z}=\Rsqrt{\Z}$\par
\ifnum\xintiloopindex<51
\repeat
\end{multicols}

\end{document}

更新（2017）。

如果需要的話，這裡是無包可擴充巨集。它擴展到I,J原來的位置N並且I**2 times J沒有J正方形。僅使用\numexpr.僅限於<2**31整數。從低到大進行，與初等因式分解方法相同。停止標準應該改進，下面的評論也適用於此。

\makeatletter

\newcommand\ExtractRadical[1]{%
    \romannumeral0%
    \expandafter
    \ExtractRadical@two@i\expandafter1\expandafter,\the\numexpr#1.%
}%
\def\ExtractRadical@two@i #1,#2.{%
    \ifnum4>#2 \expandafter\ExtractRadical@two@done\fi
    \expandafter\ExtractRadical@two@ii\the\numexpr#2/4;#1,#2.%
}%
\edef\ExtractRadical@two@done #1;#2,#3.%
    {\space#2,#3}% (not sole #2 for readability)
\def\ExtractRadical@two@ii #1;#2,#3.{%
    \ifnum\numexpr#1*4=#3 
      \expandafter\@firstoftwo
    \else
      \expandafter\@secondoftwo
    \fi
   {\expandafter\ExtractRadical@two@i\the\numexpr2*#2,#1.}%
   {\ExtractRadical@i 3;#2,#3.}%
}%
\def\ExtractRadical@i #1;{%
    \expandafter\ExtractRadical@ii\the\numexpr#1*#1.#1;%
}%
\def\ExtractRadical@ii #1.#2;#3,#4.{%
    \ifnum#1>#4 \expandafter\ExtractRadical@done\fi
    \expandafter\ExtractRadical@iii\the\numexpr#4/#1.#1;#4.#2;#3.%
}%
\def\ExtractRadical@iii #1.#2;#3.{%
    \ifnum\numexpr#1*#2=#3
      \expandafter\@firstoftwo
    \else
      \expandafter\@secondoftwo
    \fi
    \ExtractRadical@update
    \ExtractRadical@next
    #1.#2;#3.%
}%
\def\ExtractRadical@update #1.#2;#3.#4;#5.{%
    \expandafter\ExtractRadical@ii
    \the\numexpr#2\expandafter.%
    \the\numexpr#4\expandafter;%
    \the\numexpr#4*#5,#1.%
}%
\def\ExtractRadical@next #1.#2;#3.#4;#5.{%
    \expandafter\ExtractRadical@i\the\numexpr2+#4;#5,#3.%
}%
\edef\ExtractRadical@done #1;#2.#3;#4.{\space#4,#2}%

\makeatother

Question 2

這是一個基於 LuaLaTeX 的解決方案。程式碼設定了一個名為的 LaTeX 宏\rsqrt，它呼叫名為的 Lua 函數rsqrt。後者實現了您提出的簡化演算法 - 具有以下改進：

對於n=0or n=1，代碼僅返回n（不含平方根符號）；和
\sqrt{n/i²}如果它等於1，即如果n是「平方數」（4、9、16 等）或較小平方數的乘積，請注意省略該項。例如，如果n=36，則\rsqrt{36}顯示6自36 = 6^2 = 2^2*3^2。

不執行輸入健全性檢查，即使用者負責提供一個參數，該參數\rsqrt要麼是非負整數，要麼計算結果為非負整數。因此，可以編寫\rsqrt{1e6}和\rsqrt{3.6e7}：宏將分別返回1000和6000。

請注意，該巨集\rsqrt必須在數學模式下使用，因為它可能會輸出\sqrt指令。

% !TEX TS-program = lualatex  
%% Note: Code updated 2019/10/26 to work with LaTeX 2019-10-01 

%% Create an external file to contain the Lua code
\begin{filecontents*}[overwrite]{rsqrt.lua}

function rsqrt ( n )
  -- n : a non-negative whole number (or something
  --     that evaluates to a non-neg. whole number)
  if n == 0 or n == 1 then   -- Nothing to do
    return ( n )
  else
    i = math.floor ( math.sqrt ( n ) )
    while i > 1 do
      if ( n % i^2 == 0 ) then     -- n is divisible by i^2
        k = math.floor ( n / i^2 ) -- 'math.floor' makes k an explicit integer
        if k == 1 then  -- n is a "square" number (or a product of square numbers)
          return ( i )
        else
          return ( i .. "\\sqrt{" .. k .. "}" )
        end
      end
      i = i-1
    end
    -- No simplification possible:
    return ( "\\sqrt{" .. n .. "}" )
  end
end
-- Define a vector (in form of a Lua table) of whole numbers
nvec = {0,1,2,3,4,5,7,12,16,18,27,32}

-- Lua function to print 3-column array:
function PrintArray()
  for i=1,#nvec do
    u = nvec[i]
    tex.sprint ( math.floor(u) .. 
                "& \\sqrt{" .. math.floor(u) .. 
                "}&" .. rsqrt(u) .. "\\\\" )
  end
end

\end{filecontents*}

\documentclass{article}

%% Load Lua code from external file:
\directlua{dofile("rsqrt.lua")}

%% TeX-side code: "wrapper" macro that invokes the Lua function:
\newcommand\rsqrt[1]{\directlua{tex.sprint(rsqrt(#1))}}

\begin{document}
\[
\renewcommand\arraystretch{1.25}
\begin{array}{@{} rcc @{}}
  \verb+n+ & \verb+\sqrt+ & \verb+\rsqrt+ \\ % print header row
  \directlua{PrintArray()}    % create and print body of 'array'
\end{array}
\]
\end{document}

Answer

這是一個基於 LuaLaTeX 的解決方案。程式碼設定了一個名為的 LaTeX 宏\rsqrt，它呼叫名為的 Lua 函數rsqrt。後者實現了您提出的簡化演算法 - 具有以下改進：

對於n=0or n=1，代碼僅返回n（不含平方根符號）；和
\sqrt{n/i²}如果它等於1，即如果n是「平方數」（4、9、16 等）或較小平方數的乘積，請注意省略該項。例如，如果n=36，則\rsqrt{36}顯示6自36 = 6^2 = 2^2*3^2。

不執行輸入健全性檢查，即使用者負責提供一個參數，該參數\rsqrt要麼是非負整數，要麼計算結果為非負整數。因此，可以編寫\rsqrt{1e6}和\rsqrt{3.6e7}：宏將分別返回1000和6000。

請注意，該巨集\rsqrt必須在數學模式下使用，因為它可能會輸出\sqrt指令。

% !TEX TS-program = lualatex  
%% Note: Code updated 2019/10/26 to work with LaTeX 2019-10-01 

%% Create an external file to contain the Lua code
\begin{filecontents*}[overwrite]{rsqrt.lua}

function rsqrt ( n )
  -- n : a non-negative whole number (or something
  --     that evaluates to a non-neg. whole number)
  if n == 0 or n == 1 then   -- Nothing to do
    return ( n )
  else
    i = math.floor ( math.sqrt ( n ) )
    while i > 1 do
      if ( n % i^2 == 0 ) then     -- n is divisible by i^2
        k = math.floor ( n / i^2 ) -- 'math.floor' makes k an explicit integer
        if k == 1 then  -- n is a "square" number (or a product of square numbers)
          return ( i )
        else
          return ( i .. "\\sqrt{" .. k .. "}" )
        end
      end
      i = i-1
    end
    -- No simplification possible:
    return ( "\\sqrt{" .. n .. "}" )
  end
end
-- Define a vector (in form of a Lua table) of whole numbers
nvec = {0,1,2,3,4,5,7,12,16,18,27,32}

-- Lua function to print 3-column array:
function PrintArray()
  for i=1,#nvec do
    u = nvec[i]
    tex.sprint ( math.floor(u) .. 
                "& \\sqrt{" .. math.floor(u) .. 
                "}&" .. rsqrt(u) .. "\\\\" )
  end
end

\end{filecontents*}

\documentclass{article}

%% Load Lua code from external file:
\directlua{dofile("rsqrt.lua")}

%% TeX-side code: "wrapper" macro that invokes the Lua function:
\newcommand\rsqrt[1]{\directlua{tex.sprint(rsqrt(#1))}}

\begin{document}
\[
\renewcommand\arraystretch{1.25}
\begin{array}{@{} rcc @{}}
  \verb+n+ & \verb+\sqrt+ & \verb+\rsqrt+ \\ % print header row
  \directlua{PrintArray()}    % create and print body of 'array'
\end{array}
\]
\end{document}

Question 3

在expl3：

\documentclass{article}

\usepackage{xparse}

\ExplSyntaxOn
\NewDocumentCommand{\rsqrt}{m}
 {
  \manual_rsqrt:n { #1 }
 }

\int_new:N \l_manual_rsqrt_int

\cs_new_protected:Nn \manual_rsqrt:n
 {
  \int_set:Nn \l_manual_rsqrt_int { \fp_to_decimal:n { trunc(sqrt(#1),0) } }
  \bool_until_do:nn
   {
    \int_compare_p:n { \int_mod:nn { #1 } { \l_manual_rsqrt_int * \l_manual_rsqrt_int } == 0 }
   }
   {
    \int_decr:N \l_manual_rsqrt_int
   }
  \int_compare:nTF { \l_manual_rsqrt_int == 1 }
   {
    \sqrt{#1}
   }
   {
    \int_to_arabic:n { \l_manual_rsqrt_int }
    \int_compare:nF { #1 == \l_manual_rsqrt_int*\l_manual_rsqrt_int }
     {
      \sqrt{ \int_to_arabic:n { #1/(\l_manual_rsqrt_int*\l_manual_rsqrt_int) } }
     }
   }
 }
\ExplSyntaxOff

\begin{document}

$\rsqrt{4}$

$\rsqrt{8}$

$\rsqrt{18}$

$\rsqrt{12}$

$\rsqrt{7}$

\end{document}

如果你想處理參數 0 和 1 以及負參數，你可以將主定義改為

\NewDocumentCommand{\rsqrt}{m}
 {
  \int_compare:nTF { #1 < 0 }
   {
    \int_compare:nTF { #1 = -1 } { i } { \manual_rsqrt:n { -#1 } i }
   }
   {
    \int_compare:nTF { #1 < 2 } { #1 } { \manual_rsqrt:n { #1 } }
   }
 }

現在輸入

$\rsqrt{0}$ and $\rsqrt{1}$

$\rsqrt{-1}$ and $\rsqrt{-4}$ and $\rsqrt{-32}$

會輸出

Answer

在expl3：

\documentclass{article}

\usepackage{xparse}

\ExplSyntaxOn
\NewDocumentCommand{\rsqrt}{m}
 {
  \manual_rsqrt:n { #1 }
 }

\int_new:N \l_manual_rsqrt_int

\cs_new_protected:Nn \manual_rsqrt:n
 {
  \int_set:Nn \l_manual_rsqrt_int { \fp_to_decimal:n { trunc(sqrt(#1),0) } }
  \bool_until_do:nn
   {
    \int_compare_p:n { \int_mod:nn { #1 } { \l_manual_rsqrt_int * \l_manual_rsqrt_int } == 0 }
   }
   {
    \int_decr:N \l_manual_rsqrt_int
   }
  \int_compare:nTF { \l_manual_rsqrt_int == 1 }
   {
    \sqrt{#1}
   }
   {
    \int_to_arabic:n { \l_manual_rsqrt_int }
    \int_compare:nF { #1 == \l_manual_rsqrt_int*\l_manual_rsqrt_int }
     {
      \sqrt{ \int_to_arabic:n { #1/(\l_manual_rsqrt_int*\l_manual_rsqrt_int) } }
     }
   }
 }
\ExplSyntaxOff

\begin{document}

$\rsqrt{4}$

$\rsqrt{8}$

$\rsqrt{18}$

$\rsqrt{12}$

$\rsqrt{7}$

\end{document}

如果你想處理參數 0 和 1 以及負參數，你可以將主定義改為

\NewDocumentCommand{\rsqrt}{m}
 {
  \int_compare:nTF { #1 < 0 }
   {
    \int_compare:nTF { #1 = -1 } { i } { \manual_rsqrt:n { -#1 } i }
   }
   {
    \int_compare:nTF { #1 < 2 } { #1 } { \manual_rsqrt:n { #1 } }
   }
 }

現在輸入

$\rsqrt{0}$ and $\rsqrt{1}$

$\rsqrt{-1}$ and $\rsqrt{-4}$ and $\rsqrt{-32}$

會輸出

Question 4

如果您不反對跳出 LaTeX，這裡有一個使用該pythontex包的解決方案。我稱之為sroot簡單根。顯然，您可以隨意命名它。該版本需要一個

pdflatex *filename*.tex、 pythontex filename*.tex、 pdflatex *filename*.tex文檔的執行順序。

\documentclass{article}
\usepackage{pythontex}
\begin{document}
\newcommand{\sroot}[1]{\ensuremath{\py{simpleroot(#1)}}}
\begin{pycode}
from math import *
def simpleroot(n):
    if n==0:
        return(str(0))
    j=int(sqrt(n))
    flag_continue=True
    while flag_continue:
        b=n*1./(j*j)
        if b==int(b):
            mystring=str(j)+'\\sqrt{'+str(int(b)) +'}'
            flag_continue=False
        else:
            j-=1

        if int(b)==1:
            mystring=str(j)
        if int(b)==n and b>1:
            mystring='\\sqrt{'+str(int(b)) +'}'

    return(mystring)
\end{pycode}

This is a test.

The $\sqrt{1}$ is \sroot{1}.

The $\sqrt{4}$ is \sroot{4}.

The $\sqrt{7}$ is \sroot{7}.

The $\sqrt{8}$ is \sroot{8}.

The $\sqrt{18}$ is \sroot{18}.

The $\sqrt{23}$ is \sroot{23}.

The $\sqrt{27}$ is \sroot{27}.

The $\sqrt{32}$ is \sroot{32}.

The $\sqrt{64}$ is \sroot{64}.

The $\sqrt{80}$ is \sroot{80}.

The $\sqrt{1000}$ is \sroot{1000}.

The $\sqrt{3000033}$ is \sroot{3000033}.

Goodbye.
\end{document}

Answer

如果您不反對跳出 LaTeX，這裡有一個使用該pythontex包的解決方案。我稱之為sroot簡單根。顯然，您可以隨意命名它。該版本需要一個

pdflatex *filename*.tex、 pythontex filename*.tex、 pdflatex *filename*.tex文檔的執行順序。

\documentclass{article}
\usepackage{pythontex}
\begin{document}
\newcommand{\sroot}[1]{\ensuremath{\py{simpleroot(#1)}}}
\begin{pycode}
from math import *
def simpleroot(n):
    if n==0:
        return(str(0))
    j=int(sqrt(n))
    flag_continue=True
    while flag_continue:
        b=n*1./(j*j)
        if b==int(b):
            mystring=str(j)+'\\sqrt{'+str(int(b)) +'}'
            flag_continue=False
        else:
            j-=1

        if int(b)==1:
            mystring=str(j)
        if int(b)==n and b>1:
            mystring='\\sqrt{'+str(int(b)) +'}'

    return(mystring)
\end{pycode}

This is a test.

The $\sqrt{1}$ is \sroot{1}.

The $\sqrt{4}$ is \sroot{4}.

The $\sqrt{7}$ is \sroot{7}.

The $\sqrt{8}$ is \sroot{8}.

The $\sqrt{18}$ is \sroot{18}.

The $\sqrt{23}$ is \sroot{23}.

The $\sqrt{27}$ is \sroot{27}.

The $\sqrt{32}$ is \sroot{32}.

The $\sqrt{64}$ is \sroot{64}.

The $\sqrt{80}$ is \sroot{80}.

The $\sqrt{1000}$ is \sroot{1000}.

The $\sqrt{3000033}$ is \sroot{3000033}.

Goodbye.
\end{document}

化簡平方根

答案1

第一種方法（我們改變演算法）

第二種方法（與OP中的演算法相同，可擴展實作）

第三種方法：同樣是更快的演算法，但可擴展。

更新（2017）。

答案2

答案3

答案4

相關內容