長除算

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

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

関連するアルゴリズムは12世紀から存在していた。^[2] アル・サマワル・アル・マグリビ（1125–1174）は、本質的に長除算を必要とする小数の計算を実行し、無限の小数の結果をもたらしましたが、アルゴリズムを形式化しませんでした。^[3]カルドリーニ（1491）は、中世イタリアでダンダ法 として知られる長除算の最も古い印刷された例であり、 ^[4]ピティスカス（1608）による分数の10進表記の導入により、より実用的になりました。現代で使用されている特定のアルゴリズムは、ヘンリー・ブリッグス によって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 の左端から始めて、少なくとも 1 回は除数 4 が含まれる最短の数字列を見つけます。この場合、これは単に最初の数字 5 です。除数 4 を 5 を超えずに掛け合わせることができる最大の数は 1 なので、数字 1 を 5 の上に置いて商を作成します。
2. 次に、1 に除数 4 を掛けて、5 (この場合は 4) を超えない除数 4 の倍数である最大の整数を求めます。次に、この 4 を 5 の下に置いて 5 から引いて余りの 1 を求め、これを 5 の下の 4 の下に置きます。
3. その後、被除数の最初の未使用の桁、この場合は 5 の後の最初の桁 0 が、その桁のすぐ下、余り 1 の隣にコピーされ、数字 10 が形成されます。
4. この時点で、このプロセスは停止点に達するまで繰り返されます。10 を超えずに除数 4 を掛けることができる最大の数は 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 を出し、これを 2 番目の 20 の下に書きます。
6. この時点では、被除数から下げる桁がなくなり、最後の減算結果が 0 になったため、プロセスが終了したことが確認できます。

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

1. ここで止めて、被除数を除数で割った商を上に書き、余りを下に書き、答えを商の後に余りを除数で割った分数として書きます。
2. 被除数を拡張して、たとえば 500.000... と記述し、このプロセス (被除数の小数点のすぐ上の商の小数点を使用) を続行して、次の例のように小数の答えを得ることができます。

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

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

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

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

プロセスのステップの基本的な説明 (上記) では、実行するステップに重点が置かれており、結果が正しいことを保証するステップの特性 (具体的には、 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 と同じ列 (10,000 の位) に入ります。これは、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

22 以下の 37 の最大の倍数は 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 年以前の英国の£sdシステムなど) や測定単位 (常値など)の場合は、混合モードの除算を使用する必要があります。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 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 q=34061}$${\displaystyle r=0}$

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

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

b進数の加算、減算、乗算の表を記憶していなくても、数値を10 進数に変換し、最後に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 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
         それぞれ
          1 1
          90
          112
          10e
            4日
            48
             5階
             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 )という事実を利用して)。その後、上記と同じように進めます。

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

• アルゴリズム
• 任意精度演算
• エジプトの掛け算と割り算
• 初等算数
• フーリエ分割
• 多項式の長除算
• ショートディビジョン

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