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

Naszym zadaniem jest znalezienie iloczynu:

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:

Teraz możemy zapisać:

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

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.:

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

Zmienne 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, to w ← dodaj ( w, a )	jeśli bit b_i = 1, to dodaj a_i do w
K03:	b ← b shr 1	przesuń bity w b o jedną pozycję w prawo
K04:	Jeśli b = 0, to zakończ	reszta bitów jest zerowa, kończymy
K05:	a ← dodaj ( a, a )	oblicz kolejne a_i
K06:	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

Wynik:

1234567890123456789012345678901234567890
555
685185179018518517901851851790185185178950

Na początek: podrozdziału 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:

x	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

Zmienne 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: wykonuj kroki K05...K08	przetwarzamy cyfry w b
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

Wynik:

95832808595775579737342988203408934789797363
21638626396236623668969866232198
2073690341706041464574292083419814736706959241205382993813776933584726093874

Na początek: podrozdziału 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:

Zmienne 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:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy