平方根の簡略化

Question 1

質問のアルゴリズムは非常に非効率的です。もちろん、元の整数が完全な平方である場合は除きます。

この回答（時系列順）:

最も単純な因数分解アルゴリズムを模倣したマクロを使ったアプローチ。
OP のようなアルゴリズムを使用した拡張可能なアプローチ。アップデート非常に恥ずかしいことに、著者は OP のアルゴリズムを理解しておらず、dividedIなどの単純化を見つけた後、アルゴリズムがそこで停止できることを理解せずに再帰的に進みました。(言い訳として、彼は最初に「トップダウン」(効率の悪い) 方法とは逆に、再帰を必要とする「ボトムアップ」方法を実装しました)。回答はこのように更新されました。寛大で信頼できる初期の賛成者全員にお詫び申し上げます。I^2NN<-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 数値でなければならないため (内部の構造のため)、という固有の制限があります。

2. と 3. では、再帰シーケンスの構文の可能性を、妥当な範囲から少し超えて押し広げています\xintexpr。表記が少し面倒です。xintexpr.sty 1.2g関連する構文が変更されたため、さらにが必要です。

最後に（2017）パッケージなしのnumexprのみの展開可能なアプローチも追加します。

最初のアプローチ（アルゴリズムを変更する）

これは簡単な問題だと言っているわけではありません。少しグーグルで調べてみると、どうやら数学者は現在、整数の平方根を求めるのは完全な因数分解と同じくらい難しいと考えているようです。https://math.stackexchange.com/questions/171568/finding-the-radical-of-an-integerそしてhttps://math.stackexchange.com/questions/14667/square-free-integers-factorization。

ここでは、因数分解アルゴリズムの最も単純な形式を模倣するアプローチ (マクロを使用) を示します。

パッケージは、やなどxintexprの入力を許可するためだけに使用されます。また、構文で使用されるもロードします。1e7xinttools

それ以外では、すべての操作はから利用できるマクロを使用して実行されますxint。例ではほぼ数値のみを扱っているため、<2^31すべての操作を一意にで実行する変種を使用することもできます。\numexpr当然、その方がかなり高速になります。

コードでは\xintiiDivision、商と余りを同時に計算するを使用します。これが、を 2 つのマクロとに格納するために使用される理由です。\xintAssignコードでは、が消えるかどうかを調べて、で割り切れるかどうかを検出します。\A\B\BQ=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}

2 番目のアプローチ (OP と同じアルゴリズム、拡張可能な実装)

元のアルゴリズムでは、\ExtractRadicalは拡張可能A,Bでを返しますN=A^2 B。拡張不可能なラッパーは、\Rsqrt上記のより高速なアプローチを再利用してを生成しA\sqrt{B}、負Nまたはの場合を区別しますN=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}

3 番目のアプローチ: これもより高速なアルゴリズムですが、拡張可能です。

これを à la but well にコード化する方が合理的でしょう\numexpr。詳細はコードコメントにあります。この例には現在 51 個のランダムな例があり、面白いことに、(最初のアプローチから) 欠けている 1 つはランダムな正方形であることがわかりました (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 のアルゴリズムを理解しておらず、dividedIなどの単純化を見つけた後、アルゴリズムがそこで停止できることを理解せずに再帰的に進みました。(言い訳として、彼は最初に「トップダウン」(効率の悪い) 方法とは逆に、再帰を必要とする「ボトムアップ」方法を実装しました)。回答はこのように更新されました。寛大で信頼できる初期の賛成者全員にお詫び申し上げます。I^2NN<-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 数値でなければならないため (内部の構造のため)、という固有の制限があります。

2. と 3. では、再帰シーケンスの構文の可能性を、妥当な範囲から少し超えて押し広げています\xintexpr。表記が少し面倒です。xintexpr.sty 1.2g関連する構文が変更されたため、さらにが必要です。

最後に（2017）パッケージなしのnumexprのみの展開可能なアプローチも追加します。

最初のアプローチ（アルゴリズムを変更する）

これは簡単な問題だと言っているわけではありません。少しグーグルで調べてみると、どうやら数学者は現在、整数の平方根を求めるのは完全な因数分解と同じくらい難しいと考えているようです。https://math.stackexchange.com/questions/171568/finding-the-radical-of-an-integerそしてhttps://math.stackexchange.com/questions/14667/square-free-integers-factorization。

ここでは、因数分解アルゴリズムの最も単純な形式を模倣するアプローチ (マクロを使用) を示します。

パッケージは、やなどxintexprの入力を許可するためだけに使用されます。また、構文で使用されるもロードします。1e7xinttools

それ以外では、すべての操作はから利用できるマクロを使用して実行されますxint。例ではほぼ数値のみを扱っているため、<2^31すべての操作を一意にで実行する変種を使用することもできます。\numexpr当然、その方がかなり高速になります。

コードでは\xintiiDivision、商と余りを同時に計算するを使用します。これが、を 2 つのマクロとに格納するために使用される理由です。\xintAssignコードでは、が消えるかどうかを調べて、で割り切れるかどうかを検出します。\A\B\BQ=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}

2 番目のアプローチ (OP と同じアルゴリズム、拡張可能な実装)

元のアルゴリズムでは、\ExtractRadicalは拡張可能A,Bでを返しますN=A^2 B。拡張不可能なラッパーは、\Rsqrt上記のより高速なアプローチを再利用してを生成しA\sqrt{B}、負Nまたはの場合を区別しますN=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}

3 番目のアプローチ: これもより高速なアルゴリズムですが、拡張可能です。

これを à la but well にコード化する方が合理的でしょう\numexpr。詳細はコードコメントにあります。この例には現在 51 個のランダムな例があり、面白いことに、(最初のアプローチから) 欠けている 1 つはランダムな正方形であることがわかりました (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=0またはの場合n=1、コードは単にを返しますn(平方根記号なし)。
\sqrt{n/i²}がに等しい場合1、つまりがn「平方数」（4、9、16 など）またはより小さい平方数の積である場合は、項を省略するように注意してください。たとえば、の場合n=36、であるためが\rsqrt{36}表示されます。636 = 6^2 = 2^2*3^2

入力の妥当性チェックは実行されません。つまり、ユーザーは、負でない整数であるか、負でない整数に評価される引数をに提供する必要があります。したがって、とと\rsqrt書いても問題ありません。マクロはそれぞれとを返します。\rsqrt{1e6}\rsqrt{3.6e7}10006000

マクロはディレクティブ\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=0またはの場合n=1、コードは単にを返しますn(平方根記号なし)。
\sqrt{n/i²}がに等しい場合1、つまりがn「平方数」（4、9、16 など）またはより小さい平方数の積である場合は、項を省略するように注意してください。たとえば、の場合n=36、であるためが\rsqrt{36}表示されます。636 = 6^2 = 2^2*3^2

入力の妥当性チェックは実行されません。つまり、ユーザーは、負でない整数であるか、負でない整数に評価される引数をに提供する必要があります。したがって、とと\rsqrt書いても問題ありません。マクロはそれぞれとを返します。\rsqrt{1e6}\rsqrt{3.6e7}10006000

マクロはディレクティブ\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

最初のアプローチ（アルゴリズムを変更する）

2 番目のアプローチ (OP と同じアルゴリズム、拡張可能な実装)

3 番目のアプローチ: これもより高速なアルゴリズムですが、拡張可能です。

アップデート（2017）。

答え2

答え3

答え4

関連情報