Dzielenie liczb wielocyfrowych - Long division

W arytmetycznych , długo podział jest standardowym algorytmu podziału odpowiedni do rozdzielania wielu cyfr cyfry arabskie ( systemy pozycyjne ), które jest proste, wystarczy wykonać ręcznie. Rozbija problem podziału na szereg łatwiejszych kroków.

Tak jak we wszystkich problemów podziału, jeden numer, zwany dzielna jest podzielone przez drugi, zwany dzielnik , tworząc efekt zwany iloraz . Umożliwia wykonywanie obliczeń obejmujących dowolnie duże liczby, wykonując szereg prostych kroków. Skrócona forma dzielenia długiego nazywana jest dzieleniem krótkim , które jest prawie zawsze używane zamiast dzielenia długiego, gdy dzielnik ma tylko jedną cyfrę. Kawałek (znany również jako metoda ilorazów cząstkowych lub metoda kata) jest mniej mechaniczną formą długiego dzielenia, widoczną w Wielkiej Brytanii, która przyczynia się do bardziej holistycznego zrozumienia procesu dzielenia.

Chociaż pokrewne algorytmy istnieją od XII wieku naszej ery, specyficzny algorytm we współczesnym użyciu został wprowadzony przez Henry'ego Briggsa c. 1600 rne.

Edukacja

Niedrogie kalkulatory i komputery stały się najczęstszym sposobem rozwiązywania problemów z dzieleniem, eliminując tradycyjne ćwiczenia matematyczne i zmniejszając edukacyjną możliwość pokazania, jak to zrobić za pomocą techniki papieru i ołówka. (Wewnętrznie urządzenia te wykorzystują jeden z wielu algorytmów dzielenia , z których szybsze polegają na aproksymacjach i mnożeniach w celu wykonania zadań). W Stanach Zjednoczonych długi podział był szczególnie ukierunkowany na złagodzenie, a nawet wyeliminowanie ze szkolnego programu nauczania, matematyki reformowanej , choć tradycyjnie wprowadzano ją w czwartej lub piątej klasie.

metoda

W krajach anglosaskich, długo podział nie używać ukośnik podział ⟨ / ⟩ lub znak dzielenia ⟨÷⟩ symbole lecz konstruuje tableau . Dzielnik jest oddzielona od dywidendy za pomocą prawego nawiasu ⟨ ) ⟩ lub pionowym pasku ⟨ | ; dywidenda jest oddzielona od ilorazu przez vinculum (tj. overbar ). Kombinacja tych dwóch symboli jest czasami nazywana długim symbolem podziału lub nawiasem dzielącym . Rozwinął się w XVIII wieku z wcześniejszego zapisu jednowierszowego oddzielającego dywidendę od ilorazu lewym nawiasem .

Proces rozpoczyna się od podzielenia skrajnej lewej cyfry dywidendy przez dzielnik. Iloraz (zaokrąglony w dół do liczby całkowitej) staje się pierwszą cyfrą wyniku, a reszta jest obliczana (ten krok jest zapisywany jako odejmowanie). Ta reszta jest przenoszona do przodu, gdy proces jest powtarzany na kolejnej cyfrze dywidendy (oznaczonej jako „sprowadzanie” następnej cyfry do reszty). Po przetworzeniu wszystkich cyfr i braku pozostałości proces jest zakończony.

Poniżej pokazano przykład przedstawiający dzielenie 500 przez 4 (z wynikiem 125).

     125      (Explanations)
   4)500
     4        ( 4 ×  1 =  4)
     10       ( 5 -  4 =  1)
      8       ( 4 ×  2 =  8)
      20      (10 -  8 =  2)
      20      ( 4 ×  5 = 20)
       0      (20 - 20 =  0)

Przykład dzielenia długiego wykonywanego bez kalkulatora.

Bardziej szczegółowy podział kroków przedstawia się następująco:

1. Znajdź najkrótszą sekwencję cyfr, zaczynając od lewego końca dywidendy, 500, do której dzielnik 4 przechodzi co najmniej raz. W tym przypadku jest to po prostu pierwsza cyfra, 5. Największa liczba, przez którą można pomnożyć dzielnik 4 bez przekraczania 5, wynosi 1, więc cyfra 1 jest umieszczana nad 5, aby rozpocząć konstruowanie ilorazu.
2. Następnie 1 mnoży się przez dzielnik 4, aby otrzymać największą liczbę całkowitą będącą wielokrotnością dzielnika 4 bez przekraczania 5 (w tym przypadku 4). Ta 4 jest następnie umieszczana pod i odejmowana od 5, aby uzyskać resztę, 1, która jest umieszczana pod 4 pod 5.
3. Następnie pierwsza nieużywana cyfra dywidendy, w tym przypadku pierwsza cyfra 0 po 5, jest kopiowana bezpośrednio pod nią i obok pozostałej 1, tworząc liczbę 10.
4. W tym momencie proces powtarza się wystarczająco dużo razy, aby osiągnąć punkt zatrzymania: największa liczba, przez którą można pomnożyć dzielnik 4 bez przekraczania 10, wynosi 2, więc 2 jest zapisane powyżej jako druga cyfra ilorazu najbardziej po lewej stronie. To 2 jest następnie mnożone przez dzielnik 4, aby otrzymać 8, co jest największą wielokrotnością 4, która nie przekracza 10; więc 8 jest zapisywane poniżej 10, a odejmowanie 10 minus 8 jest wykonywane, aby uzyskać resztę 2, która jest umieszczona poniżej 8.
5. Następna cyfra dywidendy (ostatnie 0 z 500) jest kopiowana bezpośrednio pod nią i obok reszty 2, tworząc 20. Następnie umieszcza się największą liczbę, przez którą można pomnożyć dzielnik 4 bez przekraczania 20, czyli 5 powyżej jako trzecia cyfra ilorazu najbardziej od lewej. Ta 5 jest mnożona przez dzielnik 4, aby uzyskać 20, które jest zapisywane poniżej i odejmowane od istniejących 20, aby uzyskać resztę 0, która jest następnie zapisywana poniżej drugiej 20.
6. W tym momencie, ponieważ nie ma już cyfr do sprowadzenia z dywidendy, a ostatni wynik odejmowania wynosił 0, możemy być pewni, że proces się zakończył.

Gdyby ostatnia reszta, gdy skończyły nam się cyfry dywidendy, była czymś innym niż 0, możliwe byłyby dwa sposoby działania:

1. Moglibyśmy po prostu na tym poprzestać i powiedzieć, że dzielna podzielona przez dzielnik to iloraz zapisany na górze, a reszta na dole, i napisać odpowiedź jako iloraz, po którym następuje ułamek będący resztą dzieloną przez dzielnik.
2. Moglibyśmy wydłużyć dywidendę, zapisując ją jako, powiedzmy, 500.000... i kontynuować proces (używając kropki dziesiętnej w ilorazie bezpośrednio nad kropką dziesiętną w dywidendzie), aby uzyskać odpowiedź dziesiętną, jak poniżej przykład.

      31.75     
   4)127.00
     12         (12 ÷ 4 = 3)
      07        (0 remainder, bring down next figure)
       4        (7 ÷ 4 = 1 r 3)                                             
       3.0      (bring down 0 and the decimal point)
       2.8      (7 × 4 = 28, 30 ÷ 4 = 7 r 2)
         20     (an additional zero is brought down)
         20     (5 × 4 = 20)
          0

W tym przykładzie dziesiętna część wyniku jest obliczana poprzez kontynuowanie procesu poza cyfrą jednostek, „sprowadzając” zera jako dziesiętną część dywidendy.

Ten przykład ilustruje również, że na początku procesu można pominąć etap, który daje zero. Ponieważ pierwsza cyfra 1 jest mniejsza niż dzielnik 4, pierwszy krok jest wykonywany na pierwszych dwóch cyfrach 12. Podobnie, jeśli dzielnik miałby 13, pierwszy krok wykonywałby się na 127, a nie na 12 lub 1.

Podstawowa procedura długiego dzielenia n ÷ m

1. Znajdź położenie wszystkich miejsc dziesiętnych w dzielnej n i dzielniku m .
2. Jeśli to konieczne, uprość problem długiego dzielenia, przesuwając ułamki dziesiętne dzielnika i dzielnej o tę samą liczbę miejsc dziesiętnych w prawo (lub w lewo), tak aby ułamek dziesiętny dzielnika znajdował się na prawo od ostatniej cyfry .
3. Podczas dzielenia długiego utrzymuj liczby ułożone prosto od góry do dołu pod tabelą.
4. Po każdym kroku upewnij się, że reszta dla tego kroku jest mniejsza niż dzielnik. Jeśli tak nie jest, możliwe są trzy problemy: mnożenie jest błędne, odejmowanie jest błędne lub potrzebny jest większy iloraz.
5. W końcu reszta, r , jest dodawana do rosnącego ilorazu jako ułamek ,  r / m .

Własność niezmienna i poprawność

Podstawowa prezentacja etapów procesu (powyżej) skupia się na tym, jakie etapy mają być wykonane, a nie na właściwościach tych etapów, które zapewniają poprawność wyniku (w szczególności, że q × m + r = n , gdzie q jest końcowym ilorazem ir końcową resztą). Niewielka zmiana prezentacji wymaga więcej pisania i wymaga zmiany, a nie tylko aktualizacji cyfr ilorazu, ale może rzucić więcej światła na to, dlaczego te kroki faktycznie dają poprawną odpowiedź, umożliwiając ocenę q × m + r na poziomie pośrednim punktów w procesie. Ilustruje to kluczową właściwość użytą do wyprowadzenia algorytmu (poniżej) .

Konkretnie zmieniamy powyższą podstawową procedurę tak, aby miejsce po cyfrach budowanego ilorazu wypełniały zerami , przynajmniej do miejsca jedynek, i uwzględniały te zera w liczbach, które piszemy pod nawiasem dzielenia.

Pozwala to na zachowanie na każdym kroku niezmienniczej relacji : q × m + r = n , gdzie q jest częściowo skonstruowanym ilorazem (nad nawiasem dzielenia), a r częściowo skonstruowaną resztą (numer dolny pod nawiasem dzielenia). Zauważ, że początkowo q=0 i r=n , więc ta własność jest początkowo zachowana; proces zmniejsza r i zwiększa q z każdym krokiem, ostatecznie zatrzymując się, gdy r<m, jeśli szukamy odpowiedzi w postaci ilorazu + reszta całkowita.

Wracając do powyższego przykładu 500 ÷ 4 , znajdujemy

     125      (q, changes from 000 to 100 to 120 to 125 as per notes below)
   4)500
     400      (  4 × 100 = 400)
     100      (500 - 400 = 100; now q=100, r=100; note q×4+r = 500.)
      80      (  4 ×  20 =  80)
      20      (100 -  80 =  20; now q=120, r= 20; note q×4+r = 500.)
      20      (  4 ×   5 =  20)
       0      ( 20 -  20 =   0; now q=125, r=  0; note q×4+r = 500.)

Przykład z dzielnikiem wielocyfrowym

Animowany przykład wielocyfrowego dzielenia długiego

Można użyć dzielnika dowolnej liczby cyfr. W tym przykładzie 1260257 ma zostać podzielone przez 37. Najpierw problem jest ustawiony w następujący sposób:

              
    37)1260257

Cyfry liczby 1260257 są pobierane, dopóki nie pojawi się liczba większa lub równa 37. Tak więc 1 i 12 to mniej niż 37, ale 126 jest większe. Następnie obliczana jest największa wielokrotność liczby 37 mniejszej lub równej 126. Czyli 3 × 37 = 111 < 126, ale 4 × 37 > 126. Wielokrotność 111 jest zapisana pod 126, a 3 na górze, gdzie pojawi się rozwiązanie:

         3    
    37)1260257
       111

Zwróć uwagę, w której kolumnie wartości miejsca te cyfry są wpisane. 3 w ilorazu znajduje się w tej samej kolumnie (dziesięć tysięcy miejsc) co 6 w dywidendzie 1260257, czyli w tej samej kolumnie co ostatnia cyfra 111.

111 jest następnie odejmowana od powyższej linii, ignorując wszystkie cyfry po prawej stronie:

         3    
    37)1260257
       111
        15

Teraz cyfra z następnej mniejszej wartości miejsca dywidendy jest kopiowana i dodawana do wyniku 15:

         3    
    37)1260257
       111
        150

Proces powtarza się: odejmuje się największą wielokrotność 37 mniejszą lub równą 150. To jest 148 = 4 × 37, więc 4 jest dodawane na górze jako następna cyfra ilorazu. Następnie wynik odejmowania jest rozszerzany o kolejną cyfrę pobraną z dywidendy:

         34   
    37)1260257
       111
        150
        148
          22

Największa wielokrotność 37 mniejsze lub równe 22 to 0 × 37 = 0. Odjęcie 0 od 22 daje 22, często nie piszemy kroku odejmowania. Zamiast tego po prostu bierzemy kolejną cyfrę z dywidendy:

         340  
    37)1260257
       111
        150
        148
          225

Proces powtarza się, aż 37 dokładnie podzieli ostatnią linię:

         34061
    37)1260257
       111
        150
        148
          225
          222
            37

Długi podział w trybie mieszanym

W przypadku walut niedziesiętnych (takich jak brytyjski system £sd sprzed 1971) i miar (takich jak avoirdupois ) należy zastosować podział w trybie mieszanym . Rozważ podzielenie 50 mil 600 jardów na 37 części:

          mi -     yd -   ft -   in
           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
                   ==

Każda z czterech kolumn jest przerabiana po kolei. Zaczynając od mil: 50/37 = 1 reszta 13. Dalsze dzielenie nie jest możliwe, więc wykonaj długie mnożenie przez 1760, aby przeliczyć mile na jardy, a wynik to 22 880 jardów. Przenieś to na szczyt kolumny jardów i dodaj do 600 jardów dywidendy, dając 23480. Długi podział 23480 / 37 przebiega teraz jak normalny, dając 634 z resztą 22. Resztę mnoży się przez 3, aby uzyskać stopy i przenieść do kolumny stóp. Długi podział stóp daje 1 resztę 29, która jest następnie pomnożona przez dwanaście, aby uzyskać 348 cali. Dalszy podział jest kontynuowany, a ostatnia reszta 15 cali jest pokazana w wierszu wyniku.

Interpretacja wyników dziesiętnych

Gdy iloraz nie jest liczbą całkowitą, a proces dzielenia jest przedłużony poza przecinek dziesiętny, może zdarzyć się jedna z dwóch rzeczy:

1. Proces może się zakończyć, co oznacza, że ​​osiągnięto pozostałą część 0; lub
2. Można osiągnąć resztę, która jest identyczna z poprzednią, która pojawiła się po zapisaniu miejsc dziesiętnych. W tym drugim przypadku kontynuowanie procesu byłoby bezcelowe, ponieważ od tego momentu w ilorazu pojawiałaby się w kółko ta sama sekwencja cyfr. Tak więc nad powtarzającą się sekwencją narysowana jest kreska, aby wskazać, że powtarza się ona w nieskończoność (tzn. każda liczba wymierna jest albo kończącym, albo powtarzającym się dziesiętnym ).

Notacja w krajach nieanglojęzycznych

Chiny, Japonia, Korea używają tej samej notacji, co kraje anglojęzyczne, w tym Indie. W innych miejscach stosuje się te same ogólne zasady, ale liczby są często ułożone inaczej.

Ameryka Łacińska

W Ameryce Łacińskiej (z wyjątkiem Argentyny , Boliwii , Meksyku , Kolumbii , Paragwaju , Wenezueli , Urugwaju i Brazylii ) obliczenia są prawie takie same, ale zapisane inaczej, jak pokazano poniżej z tymi samymi dwoma przykładami użytymi powyżej. Zwykle iloraz zapisuje się pod kreską narysowaną pod dzielnikiem. Czasami po prawej stronie obliczeń rysowana jest długa pionowa linia.

     500 ÷ 4 =  125   (Explanations) 
     4                ( 4 ×  1 =  4)
     10               ( 5 -  4 =  1)
      8               ( 4 ×  2 =  8)
      20              (10 -  8 =  2)
      20              ( 4 ×  5 = 20)
       0              (20 - 20 =  0)

oraz

     127 ÷ 4 = 31.75
     124                             
       30      (bring down 0; decimal to quotient)
       28      (7 × 4 = 28)
        20     (an additional zero is added)
        20     (5 × 4 = 20)
          0

W Meksyku używana jest anglojęzyczna notacja światowa, z tą różnicą, że tylko wynik odejmowania jest opatrywany adnotacjami, a obliczenia wykonywane są mentalnie, jak pokazano poniżej:

     125     (Explanations)
   4)500
     10      ( 5 -  4 = 1)
      20     (10 -  8 = 2)
       0     (20 - 20 = 0)

W Boliwii , Brazylii , Paragwaju , Wenezueli , francuskojęzycznej Kanadzie , Kolumbii i Peru stosuje się notację europejską (patrz poniżej), z wyjątkiem tego, że iloraz nie jest oddzielony pionową linią, jak pokazano poniżej:

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

Ta sama procedura obowiązuje w Meksyku , Urugwaju i Argentynie , tylko wynik odejmowania jest opatrywany adnotacjami, a obliczenia wykonywane są mentalnie.

Eurazja

W Hiszpanii, Włoszech, Francji, Portugalii, Litwie, Rumunii, Turcji, Grecji, Belgii, Białorusi, Ukrainie i Rosji dzielnik znajduje się po prawej stronie dywidendy i jest oddzielony pionową kreską. Podział również występuje w kolumnie, ale iloraz (wynik) jest zapisany poniżej dzielnika i oddzielony poziomą linią. Ta sama metoda stosowana jest w Iranie, Wietnamie i Mongolii.

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

Na Cyprze, a także we Francji, długa pionowa kreska oddziela dywidendę i kolejne odejmowania od ilorazu i dzielnika, jak w poniższym przykładzie 6359 podzielone przez 17, co daje 374 z resztą 1.

6

3

5

17

1

374

6

Liczby dziesiętne nie są dzielone bezpośrednio, dzielna i dzielnik są mnożone przez potęgę dziesiątki tak, że dzielenie obejmuje dwie liczby całkowite. Dlatego, jeśli dzielić 12,7 przez 0,4 (zamiast miejsc dziesiętnych używa się przecinków), dzielna i dzielnik zostaną najpierw zmienione na 127 i 4, a następnie dzielenie będzie przebiegać jak powyżej.

W Austrii , Niemczech i Szwajcarii używana jest notacyjna postać równania normalnego. <dividend> : <divisor> = <iloraz>, z dwukropkiem ":" oznaczającym binarny symbol infiksowy dla operatora dzielenia (analogicznie do "/" lub "÷"). W tych regionach separator dziesiętny jest zapisany jako przecinek. (por. pierwsza część krajów Ameryki Łacińskiej powyżej, gdzie robi się to praktycznie w ten sam sposób):

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

Ten sam zapis jest stosowany w Danii , Norwegii , Bułgarii , Macedonii Północnej , Polsce , Chorwacji , Słowenii , Węgrzech , Czechach , Słowacji , Wietnamie i Serbii .

W Holandii stosuje się następujący zapis:

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

Algorytm dla dowolnej bazy

Każda liczba naturalna może być reprezentowany w dowolnym systemie liczbowym jako sekwencji z cyfr , gdy dla wszystkich , w oznacza liczbę cyfr . Wartość pod względem cyfr i podstawy wynosi ${\ Displaystyle n}$ ${\displaystyle b>1}$ ${\ Displaystyle n = \ alfa _ {0} \ alfa _ {1} \ alfa _ {2} ... \ alfa _ {k-1}}$${\ Displaystyle 0 \ leq \ alfa _ {i} <b}$${\displaystyle 0\leq i<k}$${\displaystyle k}$${\ Displaystyle n}$${\ Displaystyle n}$

${\ Displaystyle n = \ suma _ {i = 0} ^ {k-1} \ alfa _ {i} b ^ {ki-1}}$

Niech będzie dzielną i będzie dzielnikiem, gdzie jest liczbą cyfr w . Jeśli , to i . W przeciwnym razie wykonujemy iterację od , przed zatrzymaniem. ${\ Displaystyle n}$${\ Displaystyle m}$${\displaystyle l}$${\ Displaystyle m}$${\displaystyle k<l}$${\displaystyle q=0}$${\displaystyle r=n}$${\displaystyle 0\leq i\leq kl}$

Dla każdej iteracji niech będzie ilorazem wyodrębnionym do tej pory, będzie pośrednią dywidendą, będzie pośrednią resztą, będzie następną cyfrą oryginalnej dywidendy i będzie następną cyfrą ilorazu. Z definicji cyfr w podstawie , . Z definicji reszty . Wszystkie wartości są liczbami naturalnymi. inicjujemy ${\displaystyle i}$${\displaystyle q_{i}}$${\displaystyle d_{i}}$${\displaystyle r_{i}}$${\ Displaystyle \ alfa _ {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} = \ suma _ {i = 0} ^ {l-2} \ alfa _ {i} b ^ {l-2-i}}$

pierwsze cyfry . ${\ Displaystyle l-1}$${\ Displaystyle n}$

W każdej iteracji prawdziwe są trzy równania:

${\ Displaystyle d_ {i} = br_ {i-1} + \ alfa _ {i + l-1}}$

${\ Displaystyle R_ {i} = d_ {i} -m \ beta _ {i} = br_ {i-1} + \ alfa _ {i + l-1} -m \ beta _ {i}}$

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

Istnieje tylko jeden taki , który . ${\ Displaystyle \ beta _ {i}}$${\displaystyle 0\leq r_{i}<m}$

Dowód istnienia i wyjątkowości${\ Displaystyle \ beta _ {i}}$  —

Zgodnie z definicją reszty , ${\displaystyle r_{i}}$

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

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

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

Dla lewej strony nierówności wybieramy największą taką, że ${\ Displaystyle \ beta _ {i}}$

${\ Displaystyle m \ beta _ {i} \ leq br_ {i-1} + \ alfa _ {i + l-1}}$

Zawsze jest taki największy , bo i jeśli , to ${\ Displaystyle \ beta _ {i}}$${\ Displaystyle 0 \ leq \ beta _ {i} <b}$${\ Displaystyle \ beta _ {i} = 0}$

${\ Displaystyle 0 \ leq br_ {i-1} + \ alfa _ {i + l-1}}$

ale ponieważ , , , to zawsze prawda. Dla prawej strony nierówności zakładamy, że istnieje najmniejsza taka, że ${\displaystyle b>1}$${\displaystyle r_{i-1}\geq 0}$${\ Displaystyle \ alfa _ {i + l-1} \ geq 0}$${\ Displaystyle \ beta _ {i} ^ {\ prime}}$

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

Ponieważ jest to najmniejsza wartość nierówności, musi to oznaczać, że dla${\ Displaystyle \ beta _ {i} ^ {\ prime}}$${\ Displaystyle \ beta _ {i} ^ {\ prime}-1}$

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

czyli dokładnie to samo, co lewa strona nierówności. Tak więc . Jak zawsze będzie istnieć, tak będzie równe , i jest tylko jeden jedyny, który jest ważny dla nierówności. W ten sposób udowodniliśmy istnienie i wyjątkowość . ${\ Displaystyle \ beta _ {i} = \ beta _ {i} ^ {\ prime}}$${\ Displaystyle \ beta _ {i}}$${\ Displaystyle \ beta _ {i} ^ {\ prime}}$${\ Displaystyle \ beta _ {i}}$${\ Displaystyle \ beta _ {i}}$${\ Displaystyle \ beta _ {i}}$

Ostateczny iloraz to, a końcowa reszta to${\displaystyle q=q_{kl}}$${\displaystyle r=r_{kl}}$

Przykłady

W bazie 10 , korzystając z powyższego przykładu z i , początkowe wartości i . ${\displaystyle n=1260257}$${\displaystyle m=37}$${\ Displaystyle q_ {-1} = 0}$${\ Displaystyle r_ {-1} = 1}$

${\displaystyle 0\leq i\leq kl}$	${\ Displaystyle \ alfa _ {i + l-1}}$	${\ Displaystyle d_ {i} = br_ {i-1} + \ alfa _ {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}$

Tak więc i . ${\displaystyle q=34061}$${\displaystyle r=0}$

W bazie 16 , z i , wartościami początkowymi są i . ${\ Displaystyle n = {\ tekst {f412df}}}$${\displaystyle m=12}$${\ Displaystyle q_ {-1} = 0}$${\ Displaystyle r_ {-1} = {\ tekst {f}}}$

${\displaystyle 0\leq i\leq kl}$	${\ Displaystyle \ alfa _ {i + l-1}}$	${\ Displaystyle d_ {i} = br_ {i-1} + \ alfa _ {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 {\ tekst {f}} + 4 = {\ tekst {f4}}}$	${\displaystyle {\tekst{d}}}$	${\ Displaystyle {\ tekst {f4}} -12 \ cdot {\ tekst {d}} = {\ tekst {a}}}$	${\ Displaystyle 10 \ cdot 0 + {\ tekst {d}} = {\ tekst {d}}}$
1	1	${\ Displaystyle 10 \ cdot {\ tekst {a}} +1 = {\ tekst {a1}}}$	8	${\ Displaystyle {\ tekst {a1}} -12 \ cdot 8 = 11}$	${\ Displaystyle 10 \ cdot {\ tekst {d}} + 8 = {\ tekst {d8}}}$
2	2	${\ Displaystyle 10 \ cdot 11 + 2 = 112}$	${\displaystyle {\tekst{f}}}$	${\ Displaystyle 112-12 \ cdot {\ tekst {f}} = 4}$	${\ Displaystyle 10 \ cdot {\ tekst {d8}} + {\ tekst {f}} = {\ tekst {d8f}}}$
3	${\ Displaystyle {\ tekst {d}} = 13}$	${\ Displaystyle 10 \ cdot 4+ {\ tekst {d}} = {\ tekst {4d}}}$	4	${\ Displaystyle {\ tekst {4d}}-12 \ cdot 4 = 5}$	${\ Displaystyle 10 \ cdot {\ tekst {d8f}} + 4 = {\ tekst {d8f4}}}$
4	${\ Displaystyle {\ tekst {f}} = 15}$	${\ Displaystyle 10 \ cdot 5+ {\ tekst {f}} = {\ tekst {5f}}}$	5	${\ Displaystyle {\ tekst {5f}}-12 \ cdot 5 = 5}$	${\ Displaystyle 10 \ cdot {\ tekst {d8f4}} + 5 = {\ tekst {d8f45}}}$

Tak więc i . ${\ Displaystyle q = {\ tekst {d8f45}}}$${\ Displaystyle r = {\ tekst {5}}}$

Jeśli nie ma zapamiętanych tablic dodawania , odejmowania lub mnożenia dla podstawy b , ten algorytm nadal działa , jeśli liczby są konwertowane na dziesiętne , a na końcu są konwertowane z powrotem na podstawę b . Na przykład w powyższym przykładzie

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

oraz

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

z . Początkowe wartości to i . ${\displaystyle b=16}$${\ Displaystyle q_ {-1} = 0}$${\ Displaystyle r_ {-1} = 15}$

${\displaystyle 0\leq i\leq kl}$	${\ Displaystyle \ alfa _ {i + l-1}}$	${\ Displaystyle d_ {i} = br_ {i-1} + \ alfa _ {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 = {\ tekst {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 = {\ tekst {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 {\ tekst {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 {\ tekst {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}\cpunkt 15+16^{1}\cpunkt 4+5}$

Tak więc i . ${\ Displaystyle q = 16 ^ {4} \ cdot 13 + 16 ^ {3} \ cdot 8 + 16 ^ {2} \ cdot 15 + 16 ^ {1} \ cdot 4 + 5 = {\ tekst {d8f45}} _{16}}$${\ Displaystyle r = 5 = {\ tekst {5}} _ {16}}$

Algorytm ten można wykonać za pomocą tego samego rodzaju notacji ołówkiem i papierem, jak pokazano w powyższych sekcjach.

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

Ilorazy racjonalne

Jeśli iloraz nie jest ograniczony do liczby całkowitej, algorytm nie kończy się dla . Zamiast tego, jeśli to z definicji. Jeśli reszta jest równa zero w dowolnej iteracji, to iloraz jest ułamkiem -adic i jest reprezentowany jako rozwinięcie skończone dziesiętne w podstawowym zapisie pozycyjnym. W przeciwnym razie jest to nadal liczba wymierna, ale nie wymierna -adyczna, a zamiast tego jest reprezentowana jako nieskończone, powtarzalne rozwinięcie dziesiętne w podstawowym zapisie pozycyjnym. ${\displaystyle i>kl}$${\displaystyle i>kl}$${\ Displaystyle \ alfa _ {i} = 0}$${\displaystyle r_{i}}$${\displaystyle b}$${\displaystyle b}$${\displaystyle b}$${\displaystyle b}$

Podział binarny

Obliczanie w systemie liczb binarnych jest prostsze, ponieważ każda cyfra w kursie może być tylko 1 lub 0 - nie jest potrzebne mnożenie, ponieważ mnożenie przez albo daje tę samą liczbę lub zero .

Gdyby to było na komputerze, mnożenie przez 10 może być reprezentowane przez przesunięcie bitowe o 1 w lewo, a znajdowanie sprowadza się do operacji logicznej , gdzie true = 1 i false = 0. Przy każdej iteracji wykonywane są następujące operacje : ${\ Displaystyle \ beta _ {i}}$ ${\displaystyle d_{i}\geq m}$${\displaystyle 0\leq i\leq kl}$

${\ Displaystyle {\ zacząć {wyrównany} \ alfa _ {i + l-1} \ i {\ mathtt {=}} \ n \ {\ mathtt {\ i}} \ (1 \ {\ mathtt {<<} }\ (k+1-il))\\d_{i}\ &{\mathtt {=}}\ r_{i-1}\ {\mathtt {<<}}\ 1+\alpha _{i+ l-1}\\\beta _{i}\ &{\mathtt {=}}\ {\mathtt {!}}(d_{i}<m)\\r_{i}\ &{\mathtt {= }}\ d_{i}-m\ {\mathtt {\&}}\ \beta _{I}\\q_{i}\ &{\mathtt {=}}\ q_{i-1}\ {\ mathtt {<<}}\ 1+\beta _{I}\end{wyrównany}}}$

Na przykład z i , początkowe wartości to i . ${\displaystyle n=10111001}$${\ Displaystyle m=1101}$${\ Displaystyle q_ {-1} = 0}$${\ Displaystyle r_ {-1} = 101}$

${\displaystyle 0\leq i\leq kl}$	${\ Displaystyle \ alfa _ {i + l-1} \ {\ mathtt {=}} \ n \ {\ mathtt {\ i}} \ (1 \ {\ mathtt {<<}} \ (k + 1 - il))}$	${\ Displaystyle d_ {i} \ {\ mathtt {=}} \ r_ {i-1} \ {\ mathtt {<<}} \ 1 + \ alfa _ {i + l-1}}$	${\ Displaystyle \ beta _ {i} \ {\ mathtt {=}} \ ! (d_ {i} <m)}$	${\ Displaystyle r_ {i} \ {\ mathtt {=}} \ d_ {i}-m \ {\ mathtt {\ i}} \ \ beta _ {i}}$	${\ Displaystyle q_ {i} \ {\ mathtt {=}} \ q_ {i-1} \ {\ mathtt {<<}} \ 1+ \ beta _ {i}}$
0	1	1011	0	1011 − 0 = 1011	0
1	1	10111	1	10111 – 1101 = 1010	1
10	0	10100	1	10100 – 1101 = 111	11
11	0	1110	1	1110 – 1101 = 1	111
100	1	11	0	11 − 0 = 11	1110

Tak więc i . ${\displaystyle q=1110}$${\displaystyle r=11}$

Wydajność

W każdej iteracji najbardziej czasochłonnym zadaniem jest wybranie . Wiemy, że są możliwe wartości, więc możemy je znaleźć za pomocą porównań . Każde porównanie będzie wymagało oceny . Niech będzie liczbą cyfr w dzielnej i będzie liczbą cyfr w dzielniku . Liczba cyfr w . Mnożenie jest zatem , podobnie jak odejmowanie . Dlatego trzeba wybrać . Pozostała część algorytmu to dodawanie i przesuwanie cyfry i w lewo o jedną cyfrę, a więc zajmuje czas i podstawę , więc każda iteracja trwa , lub po prostu . Dla wszystkich cyfr algorytm wymaga czasu lub podstawy . ${\ 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-1)(l\log(b)+k))}$${\ Displaystyle O (kl \ log (b) + k ^ {2})}$${\displaystyle b}$

Uogólnienia

Liczby wymierne

Długie dzielenie liczb całkowitych można łatwo rozszerzyć o dywidendy niebędące liczbami całkowitymi, o ile są one racjonalne . Dzieje się tak, ponieważ każda liczba wymierna ma cykliczne rozwinięcie dziesiętne . Procedurę można również rozszerzyć o dzielniki, które mają skończone lub końcowe rozwinięcie dziesiętne (tj. ułamki dziesiętne ). W tym przypadku procedura polega na pomnożeniu dzielnika i dzielnej przez odpowiednią potęgę dziesiątki tak, aby nowy dzielnik był liczbą całkowitą – wykorzystując fakt, że a  ÷  b = ( ca ) ÷ ( cb ) – a następnie postępuj jak wyżej.

Wielomiany

Uogólniona wersja tej metody zwana wielomianowym dzieleniem długim jest również używana do dzielenia wielomianów (czasami przy użyciu skróconej wersji zwanej dzieleniem syntetycznym ).

Zobacz też

• Algorytm
• Arytmetyka z arbitralną precyzją
• Mnożenie i dzielenie w Egipcie
• Arytmetyka elementarna
• Podział Fouriera
• Wielomianowe dzielenie długie
• Algorytm przesuwania n-tego pierwiastka – do znalezienia pierwiastka kwadratowego lub dowolnego n-tego pierwiastka z liczby
• Krótki podział

Bibliografia

Zewnętrzne linki

• Algorytm długiego dzielenia
• Długa dywizja i lemat Euklidesa