長割り算

Standard division algorithm for multi-digit numbers

算術において、長除法は、多桁のヒンドゥー・アラビア数字（位取り記数法）の除算に適した標準的な除算アルゴリズムであり、手計算で実行できるほど単純です。長除法は、除算問題を一連のより簡単なステップに分解します。

すべての割り算問題と同様に、被除数と呼ばれる数を除数と呼ばれる別の数で割り、商と呼ばれる結果を生成します。これにより、任意の大きな数を含む計算を一連の簡単な手順で実行できます。^[1]長除算の短縮形は短除算と呼ばれ、除数が1桁しかない場合、ほとんどの場合、長除算の代わりに短除算が使用されます^{[要出典] 。}

歴史

関連するアルゴリズムは12世紀から存在していた。^[2]アル＝サマワル・アル＝マグリビー（1125–1174）は、本質的に長除算を必要とする小数の計算を行い、無限小数の結果を得たが、アルゴリズムを形式化することはなかった。^[3]カルドリーニ（1491）は、中世イタリアでダンダ法として知られる長除算の最も初期の印刷例であり、 ^[4]ピティスカス（1608）による分数の小数表記の導入により、より実用的になった。現代で使用されている具体的なアルゴリズムは、ヘンリー・ブリッグス によって1600年頃に導入された。^[5]

教育

安価な電卓とコンピュータは、割り算の問題を解く最も一般的な方法となり、伝統的な数学演習を排除し、紙と鉛筆による方法を示す教育機会を減少させています。（これらの機器は内部的に、さまざまな割り算アルゴリズムの1つを使用しており、そのうち高速なものは近似値と乗算を利用してタスクを達成しています。）北米では、長割り算は伝統的に4年生、5年生、さらには6年生で導入されてきましたが、数学改革によって特に学校のカリキュラムから軽視、あるいは削除されることが狙われています。^[6]

方法

英語圏では、長除算は除算スラッシュ ⟨ ∕ ⟩や除算記号 ⟨÷⟩を使用せず、代わりにタブローを構成します。^[7]除数は右括弧 ⟨ ) ⟩または縦棒 ⟨ | ⟩で被除数から区切られ、被除数はビンキュラム（つまりオーバーバー）で商から区切られます。これらの2つの記号の組み合わせは、長除算記号または除算括弧と呼ばれることもあります。^{[8]これは、被除数と商を}左括弧で区切る以前の1行表記から18世紀に発展しました。^{[9] [10]}

この処理は、被除数の左端の桁を除数で割ることから始まります。商（整数に切り捨てられたもの）が結果の最初の桁となり、余りが計算されます（この手順は減算と表記されます）。この余りは、被除数の次の桁でこの処理を繰り返す際に繰り越されます（次の桁を余りに「下げる」と表記されます）。すべての桁の処理が完了し、余りがなくなったら、処理は完了です。

以下に、500 を 4 で割った値 (結果は 125) の例を示します。

  1 2 5 （説明） 4)500 4 ( 4 × 1 = 4 ) 1 0 ( 5 - 4 = 1 ) 8 ( 4 × 2 = 8 ) 2 0 ( 10 - 8 = 2 ) 20 ( 4 × 5 = 20 ) 0 (20 - 20 = 0)

電卓を使わずに長除算を実行する例。

手順のより詳細な内訳は次のとおりです。

1. 被除数500の左端から始めて、割る数4が少なくとも1回含まれる最短の数字列を求めます。この場合、これは単に最初の数字である5です。割る数4に5を超えずに掛け算できる最大の数は1なので、商を作るために数字1を5の上に置きます。
2. 次に、1に除数4を掛けて、5（この場合は4）を超えない、除数4の倍数の中で最大の整数を求めます。この4を5の下に置いて5から引くと、余りの1が求められます。この1は、5の下の4の下に置きます。
3. その後、被除数の最初のまだ使用されていない数字、この場合は 5 の後の最初の数字 0 が、その数字のすぐ下、余り 1 の隣にコピーされ、数字 10 が形成されます。
4. この時点で、この処理は停止点に達するまで繰り返されます。4を10を超えずに掛け算できる最大の数は2なので、商の左から2番目の桁として2が上に書き込まれます。次に、この2に4を掛け算して8を得ます。これは10を超えない4の最大の倍数です。8を10の下に書き、10から8を引くことで余り2を求め、それを8の下に書きます。
5. 被除数の次の桁（500の最後の0）を、そのすぐ下に、余りの2の隣にコピーして20を作ります。次に、20を超えずに除数4に掛けられる最大の数である5を、商の左から3番目の桁として上に置きます。この5に除数4を掛けて20を作り、それを下に書き、既存の20から引いて余りの0を作り、それを次の20の下に書きます。
6. この時点では、被除数から下げる桁はもうなく、最後の減算結果が 0 であったため、プロセスが終了したことが確認できます。

被除数の桁がなくなったときの最後の余りが 0 以外であった場合、次の 2 つの対処方法が可能です。

1. ここで止めて、被除数を除数で割ったものは、商が上に書かれ、余りが下に書かれると言うこともできます。そして答えは、商の後に余りを除数で割った分数が続く形で書きます。
2. 次の例のように、被除数を 500.000... のように拡張し、(被除数の小数点のすぐ上にある商の小数点を使用して) 処理を続行して、小数の答えを得ることができます。

  31.75  4)127.00 12 (12 ÷ 4 = 3) 07（余り0 、次の数字を下へ） 4 （7÷4＝1r3）  3.0（0と小数点を下げる） 2.8 （7×4＝28、30÷4＝7r2） 20（ゼロが1つ追加されます） 20 （5×4＝20） 0

この例では、結果の小数部分は、一桁目を超えて処理を継続し、被除数の小数部分であるゼロを「下げる」ことによって計算されます。

この例は、処理の開始時にゼロを生成するステップを省略できることも示しています。最初の数字1は除数4より小さいため、最初のステップは最初の2桁の12に対して実行されます。同様に、除数が13の場合、最初のステップは12や1ではなく、127に対して実行されます。

長除算の基本手順n ÷ m

1. 被除数nと除数mのすべての小数点の位置を見つけます。
2. 必要に応じて、除数と被除数の小数を同じ小数点以下の桁数だけ右（または左）に移動して、除数の小数が最後の桁の右側になるようにして、長除算の問題を簡略化します。
3. 長割り算をするときは、表の下で数字を上から下まで一直線に並べます。
4. 各ステップの余りが除数より小さいことを確認してください。そうでない場合は、掛け算が間違っている、引き算が間違っている、あるいは商を大きくする必要がある、という3つの問題が考えられます。
5. 最終的に、余りrが分数r ⁄ mとして増大商に加算されます。

不変性と正しさ

プロセスのステップの基本的な説明（上記）は、結果が正しいことを保証するステップの特性（具体的には、 q × m + r = n、ここでqは最終的な商、rは最終的な剰余）ではなく、実行されるステップの特性に重点を置いています。説明を少し変更すると、記述量が増え、商の桁を単に更新するのではなく変更する必要が生じますが、プロセスの中間点でq × m + rを評価できるようにすることで、これらのステップが実際に正しい答えを生成する理由をより明確にすることができます。これは、アルゴリズムの導出で使用される重要な特性を示しています（下記）。

具体的には、上記の基本的な手順を修正して、構築中の商の数字の後のスペースを少なくとも 1 の位まで 0 で埋め、それらの 0 を除算括弧の下に書く数字に含めます。

これにより、各ステップで不変関係を維持できます。q × m + r = n。ここで、qは部分的に構築された商（割り算の括弧の上）、r は部分的に構築された余り（割り算の括弧の下の一番下の数値）です。初期状態ではq=0、r=nであるため、この性質は最初から成り立ちます。このプロセスは各ステップで r を減らし、 q を増やしていきます。最終的に、商 + 整数の余りの形式で答えを求める場合、 r<mで停止します。

上の500÷4の例をもう一度見てみると、

  1 2 5 （ q 、以下の注記に従って000 から100、 1 20 、 1 2 5に 4)500 400 ( 4 × 100 = 400) 100 (500 - 400 = 100 ; ここでq= 100、r= 100 ; 注: q×4+r = 500。) 80 ( 4 × 20 = 80) 20 (100 - 80 = 20 ; ここでq= 1 20、r= 20 ; 注: q×4+r = 500。) 20 ( 4 × 5 = 20) 0 ( 20 - 20 = 0; ここでq= 1 2 5、r= 0 ; q×4+r = 500であることに注意してください。)

複数桁の除数の例

多桁の長除算のアニメーション例

任意の桁数の除数を使用できます。この例では、1260257を37で割ります。まず、問題は次のように設定されます。

   37)1260257

1260257という数字を、37以上の数が現れるまで、各桁ごとに計算していきます。つまり、1と12は37より小さいですが、126は37より大きいです。次に、126以下の37の最大の倍数を計算します。つまり、3 × 37 = 111 < 126ですが、4 × 37 > 126です。111という倍数は126の下に書き、3は解が現れる上に書きます。

  3  37)1260257 111

これらの数字がどの位の列に書き込まれているか注意深く確認してください。商の3は、被除数1260257の6と同じ列（万の位）に書き込まれます。これは111の最後の桁と同じ列です。

次に、上の行から 111 を減算し、右側の数字をすべて無視します。

  3  37)1260257 111 15

次に、被除数の次の小さい位の数字をコピーし、結果の15に追加します

  3  37)1260257 111 150

この処理は繰り返されます。150以下の37の最大の倍数を引きます。148 = 4 × 37なので、商の次の桁として4が先頭に加算されます。そして、減算結果に被除数から別の桁を取り、その桁を拡張します。

  34  37)1260257 111 150 148 22

37の22以下の最大の倍数は0 × 37 = 0です。22から0を引くと22になりますが、引き算の手順を書かないことがよくあります。代わりに、被除数から別の桁を取ります

  340  37)1260257 111 150 148 225

このプロセスは、最後の行を 37 で正確に割るまで繰り返されます。

  34061 37)1260257 111 150 148 225 222 37

混合モードの長除法

10進法以外の通貨（1971年以前の英国のポンド単位など）や常用単位（アヴォワデュポワなど）では、混合モードの除算を使用する必要があります。50マイル600ヤードを37に分割することを考えてみましょう。

 マイル - ヤード - フィート - インチ  1 - 634 1 9 r. 15" 37) 50 - 600 - 0 - 0 37  22880  66  348 13 23480 66 348 1760  222  37  333 22880 128 29 15 ===== 111 348 == 170 === 148  22 66 ==

4つの列を順番に計算します。マイルから計算を始めると、50/37 = 1 余り 13 となります。これ以上の割り算は不可能なので、1,760 を掛けてマイルをヤードに変換します。結果は 22,880 ヤードです。これをヤードの列の一番上まで繰り上げ、被除数の 600 ヤードに加算すると 23,480 になります。23,480 / 37 の長割り算は通常通り行われ、634 余り 22 となります。この余りに 3 を掛けてフィートに変換し、フィートの列まで繰り上げます。フィートの長割り算は 1 余り 29 となり、さらに 12 を掛けて 348 インチとなります。長割り算が続けられ、最終的な余り 15 インチが結果行に表示されます。

小数点結果の解釈

商が整数でなく、除算処理が小数点を超えて拡張される場合、次の 2 つのいずれかが発生します。

1. プロセスは終了する可能性があり、これは余りが 0 に達したことを意味します。
2. 小数点を記入した後に生じた前回の剰余と同一の剰余に達する可能性があります。後者の場合、その時点以降、商に同じ数字の並びが何度も現れるため、処理を続ける意味がありません。そこで、繰り返しの並びの上にバーを描き、それが永遠に繰り返されることを示します（つまり、すべての有理数は有限小数または循環小数のいずれかです）。

英語圏以外の国での表記

中国、日本、韓国では、インドを含む英語圏の国と同じ表記法が使用されています。その他の国でも、基本的な原則は同じですが、数字の配置が異なる場合があります。

ラテンアメリカ

ラテンアメリカ（アルゼンチン、ボリビア、メキシコ、コロンビア、パラグアイ、ベネズエラ、ウルグアイ、ブラジルを除く）では、計算方法はほぼ同じですが、書き方が異なります。以下は、上記の同じ2つの例です。通常、商は除数の下に引かれた棒の下に書きます。計算式の右側に長い縦線が引かれることもあります

 500 ÷ 4 = 1 2 5 （説明） 4 ( 4 × 1 = 4 ) 1 0 ( 5 - 4 = 1 ) 8 ( 4 × 2 = 8 ) 2 0 ( 10 - 8 = 2 ) 20 ( 4 × 5 = 20 ) 0 (20 - 20 = 0)

そして

 127 ÷ 4 = 31.75 124  30 (0を下げて、小数を商にする) 28 （7×4＝28） 20（ゼロが1つ追加されます） 20 （5×4＝20） 0

メキシコでは、英語圏の表記法が使われていますが、減算の結果のみが注釈付けされ、計算は以下のように暗算で行われます。

  1 2 5 （説明） 4)500 1 0 ( 5 - 4 = 1 ) 2 0 ( 10 - 8 = 2 ) 0 (20 - 20 = 0)

ボリビア、ブラジル、パラグアイ、ベネズエラ、フランス語圏カナダ、コロンビア、ペルーでは、商が縦線で区切られないことを除き、ヨーロッパ表記法（下記参照）が使用されています（下記参照）。

 127| 4  − 124 31,75 30 − 28 20 − 20 0

メキシコ、ウルグアイ、アルゼンチンでも同じ手順が適用されますが、減算の結果のみが注釈付けされ、計算は暗算で行われます。

ユーラシア

スペイン、イタリア、フランス、ポルトガル、リトアニア、ルーマニア、トルコ、ギリシャ、ベルギー、ベラルーシ、ウクライナ、ロシアでは、除数は被除数の右側に書かれ、縦線で区切られます。割り算も縦書きで行われますが、商（結果）は除数の下に書かれ、横線で区切られます。イラン、ベトナム、モンゴルでも同じ方法が用いられています

 127| 4  − 124 |31,75 30 − 28 20 − 20 0

キプロスではフランスと同様、長い縦棒で被除数とそれに続く減算を商と除数から分離します。以下の例では 6359 を 17 で割ると 374 となり、余りは 1 になります。

 6359| 17  − 51 |374 125 | − 119 | 69| − 68 | 1|

小数は直接割るのではなく、被除数と除数に10の累乗を掛けて、2つの整数で割り算します。したがって、12.7を0.4で割る場合（小数点の代わりにカンマを使用します）、まず被除数と除数を127と4に変更し、その後、上記と同様に割り算を行います。

オーストリア、ドイツ、スイスでは、正規方程式の表記法が用いられます。<被除数> : <除数> = <商> で、コロン「:」は除算演算子の2進中置記号（「/」または「÷」に相当）を表します。これらの地域では、小数点はコンマで表記されます。（上記のラテンアメリカ諸国の最初のセクションを参照。ほぼ同じ方法で表記されています。）

 127 : 4 = 31,75 − 12 07 − 4 30 − 28 20 − 20 0

デンマーク、ノルウェー、ブルガリア、北マケドニア、ポーランド、クロアチア、スロベニア、ハンガリー、チェコ共和国、スロバキア、ベトナム、セルビアでも同じ表記が採用されています。

オランダでは次の表記法が使われます。

 12 / 135 \ 11,25 12 15 12 30 24 60 60 0

フィンランドでは、1970年代に上記のイタリア式が英米式に置き換えられました。しかし、2000年代初頭には、除数と被除数の順序が維持されるドイツ式が一部の教科書で採用されています。^[11]

任意の基数に対するアルゴリズム

あらゆる自然数は、任意の 基数において、すべての に対して となる桁の列として一意に表現できる。は の桁数である。 の値は、その桁と基数によって次のように表される 。 ${\displaystyle n}$ ${\displaystyle b>1}$ ${\displaystyle n=\alpha _{0}\alpha _{1}\alpha _{2}...\alpha _{k-1}}$ ${\displaystyle 0\leq \alpha _{i}<b}$ ${\displaystyle 0\leq i<k}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n}$

${\displaystyle n=\sum _{i=0}^{k-1}\alpha _{i}b^{k-i-1}}$

を被除数、を除数とします。ここでは の桁数です。 の場合、商は、余りは です。それ以外の場合は、 から繰り返して停止します。 ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle l}$ ${\displaystyle m}$ ${\displaystyle k<l}$ ${\displaystyle q=0}$ ${\displaystyle r=n}$ ${\displaystyle 0\leq i\leq k-l}$

各反復 において、 はそれまでに抽出された商、は中間の被除数、は中間の剰余、は元の被除数の次の桁、 は商の次の桁とします。 基数 の桁の定義により、となります。剰余の定義により、 となります。すべての値は自然数です。 ${\displaystyle i}$ ${\displaystyle q_{i}}$ ${\displaystyle d_{i}}$ ${\displaystyle r_{i}}$ ${\displaystyle \alpha _{i}}$ ${\displaystyle \beta _{i}}$ ${\displaystyle b}$ ${\displaystyle 0\leq \beta _{i}<b}$ ${\displaystyle 0\leq r_{i}<m}$

${\displaystyle q_{-1}=0}$

${\displaystyle r_{-1}=\sum _{i=0}^{l-2}\alpha _{i}b^{l-2-i}}$

の最初の数字。 ${\displaystyle l-1}$ ${\displaystyle n}$

すべての反復において、次の 3 つの方程式は真となります。

${\displaystyle d_{i}=br_{i-1}+\alpha _{i+l-1}}$

${\displaystyle r_{i}=d_{i}-m\beta _{i}=br_{i-1}+\alpha _{i+l-1}-m\beta _{i}}$

${\displaystyle q_{i}=bq_{i-1}+\beta _{i}}$

となるようなものは 1 つだけ存在します。 ${\displaystyle \beta _{i}}$ ${\displaystyle 0\leq r_{i}<m}$

存在と一意性の証明 ${\displaystyle \beta _{i}}$

剰余の定義によれば、 ${\displaystyle r_{i}}$

${\displaystyle 0\leq r_{i}<m}$

${\displaystyle 0\leq br_{i-1}+\alpha _{i+l-1}-m\beta _{i}<m}$

${\displaystyle m\beta _{i}\leq br_{i-1}+\alpha _{i+l-1}<m(\beta _{i}+1)}$

不等式の左辺については、 ${\displaystyle \beta _{i}}$

${\displaystyle m\beta _{i}\leq br_{i-1}+\alpha _{i+l-1}}$

常に最大の が存在する。なぜならであり、 ならば、 ${\displaystyle \beta _{i}}$ ${\displaystyle 0\leq \beta _{i}<b}$ ${\displaystyle \beta _{i}=0}$

${\displaystyle 0\leq br_{i-1}+\alpha _{i+l-1}}$

しかし、、、なので、これは常に真である。不等式の右辺については、最小のものが存在すると仮定する。 ${\displaystyle b>1}$ ${\displaystyle r_{i-1}\geq 0}$ ${\displaystyle \alpha _{i+l-1}\geq 0}$ ${\displaystyle \beta _{i}^{\prime }}$

${\displaystyle br_{i-1}+\alpha _{i+l-1}<m(\beta _{i}^{\prime }+1)}$

これは不等式が成り立つ最小値なので、 ${\displaystyle \beta _{i}^{\prime }}$ ${\displaystyle \beta _{i}^{\prime }-1}$

${\displaystyle br_{i-1}+\alpha _{i+l-1}\geq m\beta _{i}^{\prime }}$

これは不等式の左辺と全く同じです。したがって、 です。 は常に存在するので、 もに等しく、この不等式に成り立つ はただ一つしかありません。したがって、 の存在と一意性が証明されました。 ${\displaystyle \beta _{i}=\beta _{i}^{\prime }}$ ${\displaystyle \beta _{i}}$ ${\displaystyle \beta _{i}^{\prime }}$ ${\displaystyle \beta _{i}}$ ${\displaystyle \beta _{i}}$ ${\displaystyle \beta _{i}}$

最終的な商は、そして最終的な余りは ${\displaystyle q=q_{k-l}}$ ${\displaystyle r=r_{k-l}}$

例

10進法で、上記の例（と ）を使用すると、初期値と になります ${\displaystyle n=1260257}$ ${\displaystyle m=37}$ ${\displaystyle q_{-1}=0}$ ${\displaystyle r_{-1}=1}$

${\displaystyle 0\leq i\leq k-l}$	${\displaystyle \alpha _{i+l-1}}$	${\displaystyle d_{i}=br_{i-1}+\alpha _{i+l-1}}$	${\displaystyle \beta _{i}}$	${\displaystyle r_{i}=d_{i}-m\beta _{i}}$	${\displaystyle q_{i}=bq_{i-1}+\beta _{i}}$
0	2	${\displaystyle 10\cdot 1+2=12}$	0	${\displaystyle 12-37\cdot 0=12}$	${\displaystyle 10\cdot 0+0=0}$
1	6	${\displaystyle 10\cdot 12+6=126}$	3	${\displaystyle 126-37\cdot 3=15}$	${\displaystyle 10\cdot 0+3=3}$
2	0	${\displaystyle 10\cdot 15+0=150}$	4	${\displaystyle 150-37\cdot 4=2}$	${\displaystyle 10\cdot 3+4=34}$
3	2	${\displaystyle 10\cdot 2+2=22}$	0	${\displaystyle 22-37\cdot 0=22}$	${\displaystyle 10\cdot 34+0=340}$
4	5	${\displaystyle 10\cdot 22+5=225}$	6	${\displaystyle 225-37\cdot 6=3}$	${\displaystyle 10\cdot 340+6=3406}$
5	7	${\displaystyle 10\cdot 3+7=37}$	1	${\displaystyle 37-37\cdot 1=0}$	${\displaystyle 10\cdot 3406+1=34061}$

したがって、および。 ${\displaystyle q=34061}$ ${\displaystyle r=0}$

16進数では、およびの場合、初期値はおよびです ${\displaystyle n={\text{f412df}}}$ ${\displaystyle m=12}$ ${\displaystyle q_{-1}=0}$ ${\displaystyle r_{-1}={\text{f}}}$

${\displaystyle 0\leq i\leq k-l}$	${\displaystyle \alpha _{i+l-1}}$	${\displaystyle d_{i}=br_{i-1}+\alpha _{i+l-1}}$	${\displaystyle \beta _{i}}$	${\displaystyle r_{i}=d_{i}-m\beta _{i}}$	${\displaystyle q_{i}=bq_{i-1}+\beta _{i}}$
0	4	${\displaystyle 10\cdot {\text{f}}+4={\text{f4}}}$	${\displaystyle {\text{d}}}$	${\displaystyle {\text{f4}}-12\cdot {\text{d}}={\text{a}}}$	${\displaystyle 10\cdot 0+{\text{d}}={\text{d}}}$
1	1	${\displaystyle 10\cdot {\text{a}}+1={\text{a1}}}$	8	${\displaystyle {\text{a1}}-12\cdot 8=11}$	${\displaystyle 10\cdot {\text{d}}+8={\text{d8}}}$
2	2	${\displaystyle 10\cdot 11+2=112}$	${\displaystyle {\text{f}}}$	${\displaystyle 112-12\cdot {\text{f}}=4}$	${\displaystyle 10\cdot {\text{d8}}+{\text{f}}={\text{d8f}}}$
3	${\displaystyle {\text{d}}=13}$	${\displaystyle 10\cdot 4+{\text{d}}={\text{4d}}}$	4	${\displaystyle {\text{4d}}-12\cdot 4=5}$	${\displaystyle 10\cdot {\text{d8f}}+4={\text{d8f4}}}$
4	${\displaystyle {\text{f}}=15}$	${\displaystyle 10\cdot 5+{\text{f}}={\text{5f}}}$	5	${\displaystyle {\text{5f}}-12\cdot 5=5}$	${\displaystyle 10\cdot {\text{d8f4}}+5={\text{d8f45}}}$

したがって、および。 ${\displaystyle q={\text{d8f45}}}$ ${\displaystyle r={\text{5}}}$

bを底とする加算、減算、乗算の表を記憶していなくても、数値を小数に変換し、最後にbを底とする数値に戻すと、このアルゴリズムは機能します。例えば、上記の例では、

${\displaystyle n={\text{f412df}}_{16}=15\cdot 16^{5}+4\cdot 16^{4}+1\cdot 16^{3}+2\cdot 16^{2}+13\cdot 16^{1}+15\cdot 16^{0}}$

および

${\displaystyle m={\text{12}}_{16}=1\cdot 16^{1}+2\cdot 16^{0}=18}$

と。初期値はおよびです ${\displaystyle b=16}$ ${\displaystyle q_{-1}=0}$ ${\displaystyle r_{-1}=15}$

${\displaystyle 0\leq i\leq k-l}$	${\displaystyle \alpha _{i+l-1}}$	${\displaystyle d_{i}=br_{i-1}+\alpha _{i+l-1}}$	${\displaystyle \beta _{i}}$	${\displaystyle r_{i}=d_{i}-m\beta _{i}}$	${\displaystyle q_{i}=bq_{i-1}+\beta _{i}}$
0	4	${\displaystyle 16\cdot 15+4=244}$	${\displaystyle 13={\text{d}}}$	${\displaystyle 244-18\cdot 13=10}$	${\displaystyle 16\cdot 0+13=13}$
1	1	${\displaystyle 16\cdot 10+1=161}$	8	${\displaystyle 161-18\cdot 8=17}$	${\displaystyle 16\cdot 13+8}$
2	2	${\displaystyle 16\cdot 17+2=274}$	${\displaystyle 15={\text{f}}}$	${\displaystyle 274-18\cdot 15=4}$	${\displaystyle 16\cdot (16\cdot 13+8)+15=16^{2}\cdot 13+16\cdot 8+15}$
3	${\displaystyle {\text{d}}=13}$	${\displaystyle 16\cdot 4+13=77}$	4	${\displaystyle 77-18\cdot 4=5}$	${\displaystyle 16\cdot (16^{2}\cdot 13+16\cdot 8+15)+4=16^{3}\cdot 13+16^{2}\cdot 8+16\cdot 15+4}$
4	${\displaystyle {\text{f}}=15}$	${\displaystyle 16\cdot 5+15=95}$	5	${\displaystyle 95-18\cdot 5=5}$	${\displaystyle 16\cdot (16^{3}\cdot 13+16^{2}\cdot 8+16\cdot 15+4=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5}$

したがって、および。 ${\displaystyle q=16^{4}\cdot 13+16^{3}\cdot 8+16^{2}\cdot 15+16^{1}\cdot 4+5={\text{d8f45}}_{16}}$ ${\displaystyle r=5={\text{5}}_{16}}$

このアルゴリズムは、上記のセクションで示したのと同じ種類の鉛筆と紙の表記法を使用して実行できます。

  d8f45 r. 5 12 ) f412df 個 a1 90 112 10e 4日 48 5f 5a 5

有理数商

商が整数に制限されていない場合、アルゴリズムは で終了しません。代わりに、の場合、定義により となります。任意の反復処理で剰余がゼロになる場合、商は-進分数となり、基数位取り記法では有限小数展開として表されます。それ以外の場合、商は依然として有理数ですが -進有理数ではなく、基数位取り記法では無限循環小数展開として表されます。 ${\displaystyle i>k-l}$ ${\displaystyle i>k-l}$ ${\displaystyle \alpha _{i}=0}$ ${\displaystyle r_{i}}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle b}$

二進除算

パフォーマンス

各反復において、最も時間のかかるタスクは を選択することです。可能な値が存在することが分かっているので、比較を使用してを見つけることができます。各比較では を評価する必要があります。を被除数の桁数、 を除数の桁数とします。 の桁数。したがって、の乗算はであり、 の減算も同様です。したがって、を選択するにはかかります。アルゴリズムの残りの部分は、 の加算と とを1桁左に桁シフトすることなので、 とを基数で かかり、 は かかり、 は基数でかかるため、各反復には、または かかります。すべての桁について、アルゴリズムには、または基数でかかります ${\displaystyle \beta _{i}}$ ${\displaystyle b}$ ${\displaystyle \beta _{i}}$ ${\displaystyle O(\log(b))}$ ${\displaystyle d_{i}-m\beta _{i}}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle l}$ ${\displaystyle m}$ ${\displaystyle d_{i}\leq l+1}$ ${\displaystyle m\beta _{i}}$ ${\displaystyle O(l)}$ ${\displaystyle d_{i}-m\beta _{i}}$ ${\displaystyle O(l\log(b))}$ ${\displaystyle \beta _{i}}$ ${\displaystyle q_{i}}$ ${\displaystyle r_{i}}$ ${\displaystyle O(k)}$ ${\displaystyle O(l)}$ ${\displaystyle b}$ ${\displaystyle O(l\log(b)+k+l)}$ ${\displaystyle O(l\log(b)+k)}$ ${\displaystyle k-l+1}$ ${\displaystyle O((k-l+1)(l\log(b)+k))}$ ${\displaystyle O(kl\log(b)+k^{2})}$ ${\displaystyle b}$

一般化

有理数

整数の長除法は、有理数である限り、非整数の被除数を含むように簡単に拡張できます。これは、すべての有理数が循環小数展開を持つためです。この手順は、有限または有限小数展開を持つ除数（つまり、小数）を含むように拡張することもできます。この場合、新しい除数が整数になるように、除数と被除数に適切な10の累乗を掛けます（a  ÷  b = ( ca ) ÷ ( cb )という事実を利用します）。その後は、上記と同じように進めます

多項式

この方法の一般化されたバージョンである多項式長除法は、多項式の除算にも使用されます（合成除法と呼ばれる簡略版が使用されることもあります）。

参照

• アルゴリズム
• 任意精度演算
• エジプト式乗算と除算
• 初等算数
• フーリエ除算
• 多項式除算
• 短縮版

参考文献

1. Weisstein, Eric W.「長除算」. MathWorld
2. 「イスラム数学」. new.math.uiuc.edu . 2016年3月31日閲覧。
3. Victor J. Katz著『数学史入門』Addison-Wesley、2008年
4. ウィル・ウィンザー、ジョージ・ブッカー (2005). 「分割概念の歴史的分析」(PDF) .
5. ヘンリー・ブリッグス - オックスフォード・リファレンス。
6. クライン、ミルグラム「K-12カリキュラムにおける長除算の役割」(PDF) . CiteSeer . 2019年6月21日閲覧。
7. Nicholson, W. Keith (2012)、『抽象代数入門』第4版。、ジョン・ワイリー・アンド・サンズ、206ページ。
8. 「長除算記号」、Wolfram MathWorld 、 2016年2月11日閲覧。
9. ミラー、ジェフ（2010）「演算記号」、様々な数学記号の初期の使用。
10. ヒル、ジョン（1772）[初版1712年]、理論と実践の両方における算術（第11版）、ロンドン：ストラベン他、p. 200 、 2016年2月12日閲覧。
11. ハンネレ・イカヘイモ: Jakolaskuun ymmärrystä (フィンランド語)

外部リンク

• 長除法アルゴリズム
• 長除法とユークリッドの補題

Retrieved from "https://en.wikipedia.org/w/index.php?title=Long_division&oldid=1320742011"