Algorytmy i Struktury Danych - Mnożenie dużych liczb

Naszym zadaniem jest znalezienie iloczynu:

W = a×b

gdzie:
a – liczba duża,
b – liczba mała

Liczba mała b rozkłada się na sumę potęg 2 mnożonych przez kolejne bity b_i liczby b:

b = b₃₁×2³¹+b₃₀×2³⁰+…+b₂×2²+b₁×2¹+b₀×2⁰

Teraz możemy zapisać:

W = a×(b₃₁×2³¹+b₃₀×2³⁰+…+b₂×2²+b₁×2¹+b₀×2⁰)
W = a×b₃₁×2³¹+a×b₃₀×2³⁰+…+a×b₂×2²+a×b₁×2¹+a×b₀×2⁰

Na pierwszy rzut oka otrzymany wzór wydaje się mało przydatny. Jednakże pozory mylą. Zapiszmy to nieco inaczej:

W = b₃₁×2³¹×a+b₃₀×2³⁰×a+…+b₃×2³×a+b₂×2²×a+b₁×2¹×a+b₀×2⁰×aW = b₃₁×2³¹×a+b₃₀×2³⁰×a+…+b₃×8a+b₂×4a+b₁×2a+b₀×a

W powyższym wzorze b_i to i-ty bit mniejszej liczby. Natomiast kolejne iloczyny 2ⁱ×a bardzo łatwo oblicza się dynamicznie za pomocą dodawania, ponieważ, co łatwo zauważyć, każdy kolejny iloczyn jest dwa razy większy od poprzedniego:

a₀ = a
a₁ = 2×a = a₀+a₀a₂ = 4×a = a₁+a₁a₃ = 8×a = a₂+a₂…
a₃₀ = 2³⁰×a = a₂₉+a₂₉a₃₁ = 2³¹×a = a₃₀+a₃₀

Iloczyny dodajemy do wyniku W, jeśli odpowiedni bit b_i jest równy 1. W całym tym postępowaniu wykonywane są tylko dodawania dużych liczb, które zostały opisane w poprzednim rozdziale. Bity z liczby b możemy łatwo wydzielać za pomocą operacji koniunkcji i przesuwów

Algorytm mnożenia dowolnie dużej liczby nieujemnej przez małą liczbę nieujemną

Wejście:

a : duża liczba jako łańcuch znakowy.
b : mała liczba; b ∈ N.

Wyjście:

w : łańcuch wynikowy, który zawiera cyfry iloczynu ab.
a : zawartość nieokreślona.
b : zawiera zero.

Elementy pomocnicze:

dodaj(x, y) : dodaje dwie duże liczby x i y jako łańcuchy i zwraca wynik jako łańcuch.

Lista kroków:

K01: w ← "0" ; zerujemy wynik
K02: Jeśli (b and 1) = 1, ; jeśli bit b_i = 1, to dodaj a_i do w
     to w ← dodaj(w, a)
K03: b ← b shr 1 ; przesuń bity w b o jedną pozycję w prawo
K04: Jeśli b = 0, ; reszta bitów jest zerowa, kończymy
     to zakończ
K05: a ← dodaj(a, a) ; oblicz kolejne a_iK06: Idź do kroku K02 ; kontynuuj pętlę

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje dwie liczby nieujemne. Pierwsza o dowolnej ilości cyfr. Druga w zakresie od 0 do 4294967295. Oblicza ich iloczyn i wypisuje wynik.

Pascal

// Mnożenie dużej liczby przez małą
// Data: 23.10.2012
// (C)2020 mgr Jerzy Wałaszek
//---------------------------------

program mulbigsmall;

// Oblicza sumę podanych liczb
//----------------------------
function dodaj(var x, y : ansistring)
                        : ansistring;
var
  z : ansistring;
  p, w, i, j, k, n : integer;

begin

  i := length(x);
  j := length(y);
  n := i; if j < i then n := j;
  p := 0;
  z := '';

  for k := 1 to n do
  begin
    w  := ord(x[i])+ord(y[j])+p-96;
    dec(i); dec(j);
    p  := w div 10;
    z := chr((w mod 10)+48)+z;
  end;

  while i > 0 do
  begin
    w  := ord(x[i])+p-48;
    dec(i);
    p  := w div 10;
    z := chr((w mod 10)+48)+z;
  end;

  while j > 0 do
  begin
    w := ord(y[j])+p-48;
    dec(j);
    p := w div 10;
    z := chr((w mod 10)+48)+z;
  end;

  if p > 0 then z := chr(p+48)+z;
  if z = '' then z := '0';
  dodaj := z;  // zwracamy wynik dodawania

end;

//********************
//** PROGRAM GŁÓWNY **
//********************

var
  a, w : ansistring;
  b : dword;

begin

  // odczytujemy liczby do mnożenia
  readln(a);
  readln(b);

  w := '0'; // zerujemy łańcuch wyjściowy

  while true do // wykonujemy mnożenie
  begin
    if(b and 1) = 1 then w := dodaj(w, a);
    b := b shr 1;
    if b = 0 then break;
    a := dodaj(a, a);
  end;

  writeln(w); // wyświetlamy wynik

end.

C++

// Mnożenie dużej liczby przez małą
// Data: 23.10.2012
// (C)2020 mgr Jerzy Wałaszek
//---------------------------------

#include <iostream>
#include <string>

using namespace std;

// Oblicza sumę podanych liczb
//----------------------------
string dodaj (string & x, string & y)
{
  string z;
  int p, w, i, j, k, n;

  i = x.length();
  j = y.length();

  n = i; if(j < i) n = j;

  p = 0;

  z = "";

  for(k = 1; k <= n; k++)
  {
    w = (int)(x[--i])+(int)(y[--j])+p-96;
    p = w/10;
    z = (char)((w%10)+48)+z;
  }

  while(i)
  {
    w = x[--i]+p-48;
    p = w/10;
    z = (char)((w%10)+48)+z;
  }

  while(j)
  {
    w = y[--j]+p-48;
    p = w/10;
    z = (char)((w%10)+48)+z;
  }

  if(p) z = (char)(p+48)+ z;

  if(z == "") z = "0";

  return z;  // zwracamy wynik dodawania
}

//********************
//** PROGRAM GŁÓWNY **
//********************

int main()
{
  string a, w;
  unsigned int b;

  // odczytujemy liczby do mnożenia

  cin >> a >> b;

  w = "0"; // zerujemy łańcuch wyjściowy

  while(true) // wykonujemy mnożenie
  {
    if(b & 1)   w = dodaj(w, a);
    if(b >>= 1) a = dodaj(a, a);
    else break;
  }

  cout << w << endl; // wyświetlamy wynik

  return 0;

}

Basic

' Mnożenie dużej liczby przez małą
' Data: 23.10.2012
' (C)2020 mgr Jerzy Wałaszek
'---------------------------------

' Oblicza sumę podanych liczb
'----------------------------
Function dodaj (ByRef x As String, _
                ByRef y As String) _
                As String

  Dim As string z
  Dim As Integer p, w, i, j, k, n

  i = Len(x)
  j = Len(y)

  n = i
  If j < i Then n = j

  p = 0

  z = ""

  For k = 1 To n
    w  = Asc(Mid(x, i, 1))+Asc(Mid(y, j, 1))+p-96
    i -= 1: j -= 1
    p  = w\10
    z = Chr((w Mod 10)+48)+z
  Next

  While i > 0
    w  = Asc(Mid(x, i, 1))+p-48
    i -= 1
    p  = w\10
    z = Chr((w Mod 10)+48)+z
  Wend

  While j > 0
    w  = Asc(Mid(y, j, 1))+p-48
    j -= 1
    p  = w\10
    z = Chr((w Mod 10)+48)+z
  Wend

  If p > 0 Then z = Chr(p+48)+z

  If z = "" Then z = "0"
 
  dodaj = z

End Function

'********************
'** PROGRAM GŁÓWNY **
'********************

Dim As String a, w
Dim As UInteger b

' odczytujemy liczby do mnożenia
Open Cons For Input As #1

Line Input a
Input #1, b

Close #1

w = "0" ' zerujemy łańcuch wyjściowy

While 1 ' wykonujemy mnożenie
  if(b And 1) = 1 Then w = dodaj(w, a)
  b Shr= 1
  If b = 0 Then Exit While
  a = dodaj(a, a)
Wend

Print w ' wyświetlamy wynik

End

Python (dodatek)

# Mnożenie dużych liczb
# Data: 1.04.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

# odczytujemy liczby do mnożenia
s1 = int(input("L1 = "))
s2 = int(input("L2 = "))
# obliczamy iloczyn
s3 = s1 * s2
# wyświetlamy wynik
print("   =", s3)

Wynik:

1234567890123456789012345678901234567890
555
685185179018518517901851851790185185178950

do podrozdziału do strony

Postąpimy zgodnie z algorytmem "szkolnym" (profesjonalne algorytmy wymagają innego podejścia). Liczby zapisujemy jedna nad drugą – umówmy się, że dłuższą liczbę zapisujemy u góry, a krótszą na dole:

x	95832808595775579737342988203408934789797363 21638626396236623668969866232198

Następnie tworzymy kolejne iloczyny częściowe górnej liczby przez cyfry liczby dolnej. Iloczyny te są przesunięte w lewo zgodnie z pozycją mnożącej cyfry:

                                95832808595775579737342988203408934789797363
                                           21638626396236623668969866232198

                               766662468766204637898743905627271478318378904
                              8624952773619802176360868938306804131081762670
                              9583280859577557973734298820340893478979736300
                            191665617191551159474685976406817869579594726000
                                                               … … … … … … …
                                                               … … … … … … …
                                                               … … … … … … …
  57499685157465347842405792922045360873878417800000000000000000000000000000
 95832808595775579737342988203408934789797363000000000000000000000000000000
1916656171915511594746859764068178695795947260000000000000000000000000000000

2073690341706041464574292083419814736706959241205382993813776933584726093874

Otrzymane iloczyny dodajemy do siebie i otrzymujemy wynik mnożenia. Do wyznaczania iloczynów częściowych możemy wykorzystać podany wcześniej algorytm mnożenia dużej liczby (pierwszej) przez małą (cyfrę drugiej). Do otrzymanego wyniku należy na końcu dołączać odpowiednią ilość zer (przesunięcie wg mnożonej cyfry).

Algorytm mnożenia dwóch dowolnie dużych nieujemnych liczb całkowitych

Wejście:

a, b : liczby podane w postaci łańcuchów znakowych.

Wyjście:

w : łańcuch wynikowy, który zawiera cyfry iloczynu ab.

Elementy pomocnicze:

c : łańcuch pomocniczy dla iloczynu częściowego.
z : łańcuch zawierający dodawane zera na końcu iloczynów częściowych.
n : zawiera liczbę cyfr w b; n ∈ N.
i : wskazuje pozycję cyfr w b przez które mnożymy a; i ∈ N.
dodaj(x, y) : dodaje dwie duże liczby x i y jako łańcuchy i zwraca wynik jako łańcuch.
mnóż(x, y) : zwraca łańcuch z iloczynem liczby dużej x jako łańcucha znakowego i liczby małej y; y ∈ N.
kod(x) : zwraca kod znaku x.

Lista kroków:

K01: w ← "0" ; zerujemy wynik
K02: z ← "" ; będzie zawierać dodawane zera
K03: n ← |b| ; wyznaczamy liczbę cyfr w b
K04: Dla i = n, n-1, …, 1: ; przetwarzamy cyfry w b
     wykonuj kroki K05…K08
K05:   c ← mnóż(a, kod(b[i])-48) ; obliczamy iloczyn a przez cyfrę z b
K06:   c ← c+z ; dołączamy zera w celu przesunięcia tego iloczynu
K07:   w ← dodaj(w, c) ; iloczyn dodajemy do wyniku
K08:   z ← z+"0" ; zwiększamy liczbę zer dla następnego obiegu
K09: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje dwie dowolnie duże liczby nieujemne, oblicza ich iloczyn i wypisuje wynik.

Pascal

// Mnożenie dużych liczb
// Data: 23.10.2012
// (C)2020 mgr Jerzy Wałaszek
//---------------------------------------

program mulbignum;

// Oblicza sumę podanych liczb
//----------------------------
function dodaj(var x, y : ansistring)
                        : ansistring;
var
  z : ansistring;
  p, w, i, j, k, n : integer;

begin

  i := length(x);
  j := length(y);

  n := i; if j < i then n := j;

  p := 0;

  z := '';

  for k := 1 to n do
  begin
    w := ord(x[i])+ord(y[j])+p-96;
    dec(i); dec(j);
    p := w div 10;
    z := chr((w mod 10)+48)+z;
  end;

  while i > 0 do
  begin
    w := ord(x[i])+p-48;
    dec(i);
    p := w div 10;
    z := chr((w mod 10)+48)+z;
  end;

  while j > 0 do
  begin
    w := ord(y[j])+p-48;
    dec(j);
    p := w div 10;
    z := chr((w mod 10)+48)+z;
  end;

  if p > 0 then z := chr(p+48)+z;

  if z = '' then z := '0';

  dodaj := z; // zwracamy wynik dodawania

end;

// Mnoży dużą liczbę a przez małą b
//---------------------------------
function mnoz(a : ansistring;
              b : dword)
                : ansistring;
var
  w : ansistring;

begin

  w := '0'; // zerujemy łańcuch wyjściowy

  while true do // wykonujemy mnożenie
  begin
    if(b and 1) = 1 then w := dodaj(w, a);
    b := b shr 1;
    if b = 0 then break;
    a := dodaj(a, a);
  end;

  mnoz := w; // zwracamy wynik mnożenia

end;

//********************
//** PROGRAM GŁÓWNY **
//********************

var
  a, b, c, w, z : ansistring;
  i : dword;

begin

  // odczytujemy liczby do mnożenia
  readln(a);
  readln(b);

  // mnożymy
  w := '0';
  z := '';
  for i := length(b) downto 1 do
  begin
    c := mnoz(a, ord(b[i])-48)+z;
    w := dodaj(w, c);
    z := z+'0';
  end;

  // wypisujemy wyniki
  writeln(w);

end.

C++

// Mnożenie dużych liczb
// Data: 23.10.2012
// (C)2020 mgr Jerzy Wałaszek
//---------------------------------------

#include <iostream>
#include <string>

using namespace std;

// Oblicza sumę podanych liczb
//----------------------------
string dodaj(string & x, string & y)
{
  string z;
  int p, w, i, j, k, n;

  i = x.length();
  j = y.length();

  n = i; if(j < i) n = j;

  p = 0;

  z = "";

  for(k = 1; k <= n; k++)
  {
    w = (int)(x[--i])+(int)(y[--j])+p-96;
    p = w/10;
    z = (char)((w%10)+48)+z;
  }

  while(i)
  {
    w = x[--i]+p-48;
    p = w/10;
    z = (char)((w % 10)+48)+z;
  }

  while(j)
  {
    w = y[--j]+p-48;
    p = w/10;
    z = (char)((w%10)+48)+z;
  }

  if(p) z = (char)(p+48)+z;

  if(z == "") z = "0";

  return z; // zwracamy wynik dodawania
}

// Mnoży dużą liczbę a przez małą b
//---------------------------------
string mnoz(string a, unsigned int b)
{
  string w;

  w = "0"; // zerujemy łańcuch wyjściowy

  while(true) // wykonujemy mnożenie
  {
    if(b & 1)   w = dodaj(w, a);
    if(b >>= 1) a = dodaj(a, a); else break;
  }

  return w; // zwracamy wynik mnożenia
}

//********************
//** PROGRAM GŁÓWNY **
//********************

int main()
{
  string a, b, c, w, z;
  int i;

  // odczytujemy liczby do mnożenia
  cin >> a >> b;

  // mnożymy
  w = "0";
  z = "";
  for(i = b.length()-1; i >= 0; i--)
  {
    c = mnoz(a, b[i]-48)+z;
    w = dodaj(w, c);
    z += "0";
  }

  // wypisujemy wyniki
  cout << w << endl;

  return 0;
}

Basic

' Mnożenie dużych liczb
' Data: 23.10.2012
' (C)2020 mgr Jerzy Wałaszek
'---------------------------------------

' Oblicza sumę podanych liczb
'----------------------------
Function dodaj(ByRef x As String, _
               ByRef y As String) _
                       As String
  Dim As string z
  Dim As Integer p, w, i, j, k, n

  i = Len(x)
  j = Len(y)

  n = i: If j < i Then n = j

  p = 0

  z = ""

  For k = 1 To n
    w  = Asc(Mid(x, i, 1))+Asc(Mid(y, j, 1))+p-96
    i -= 1: j -= 1
    p  = w\10
    z = Chr((w Mod 10)+48)+z
  Next

  While i > 0
    w = Asc(Mid(x, i, 1))+p-48
    i -= 1
    p = w\10
    z = Chr((w Mod 10)+48)+z
  Wend

  While j > 0
    w = Asc(Mid(y, j, 1))+p-48
    j -= 1
    p = w\10
    z = Chr((w Mod 10)+48)+z
  Wend

  If p > 0 Then z = Chr(p+48)+z

  If z = "" Then z = "0"
 
  dodaj = z

End Function

' Mnoży dużą liczbę a przez małą b
'---------------------------------
Function mnoz(ByRef x As String, _
              ByVal b As UInteger) _
                      As String
  Dim As String a, w
 
  a = x ' tworzymy kopię roboczą łańcucha

  w = "0" ' zerujemy łańcuch wyjściowy

  While 1 ' wykonujemy mnożenie
    if(b And 1) = 1 Then w = dodaj(w, a)
    b Shr= 1
    If b = 0 Then Exit While
    a = dodaj(a, a)
  Wend

  mnoz = w ' zwracamy wynik mnożenia

End Function

'********************
'** PROGRAM GŁÓWNY **
'********************

Dim As String a, b, c, w, z
Dim As UInteger i

' odczytujemy liczby do mnożenia
Line Input a
Line Input b

' mnożymy
w = "0"
z = ""
For i = Len(b) To 1 Step -1
  c = mnoz(a, Asc(Mid(b, i, 1))-48)+z
  w = dodaj(w, c)
  z += "0"
Next

' wypisujemy wyniki
Print w

End

Python (dodatek)

# Mnożenie dużych liczb
# Data: 2.04.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

# odczytujemy liczby do mnożenia
s1 = int(input("L1 = "))
s2 = int(input("L2 = "))
# obliczamy iloczyn
s3 = s1 * s2
# wyświetlamy wynik
print("   =", s3)

Wynik:

95832808595775579737342988203408934789797363
21638626396236623668969866232198
2073690341706041464574292083419814736706959241205382993813776933584726093874

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Mnożenie dużych liczb

Problem nr 1

Rozwiązanie problemu nr 1

Algorytm mnożenia dowolnie dużej liczby nieujemnej przez małą liczbę nieujemną

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Problem nr 2

Rozwiązanie problemu nr 2

Algorytm mnożenia dwóch dowolnie dużych nieujemnych liczb całkowitych

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy