Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2022 mgr Jerzy Wałaszek
I LO w Tarnowie

Mnożenie dużych liczb

SPIS TREŚCI
Podrozdziały

Problem nr 1

Należy pomnożyć dowolnie dużą nieujemną liczbę całkowitą przez nieujemną liczbę całkowitą względnie małą, np. 32 bitową.

Rozwiązanie problemu nr 1

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 ia 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
Mnożenie dużej liczby przez małą
(C)2020 mgr Jerzy Wałaszek

Duża liczba →

Mała liczba →

.

Na początek:  podrozdziału   strony 

Problem nr 2

Należy obliczyć wartość iloczynu dwóch dowolnie dużych nieujemnych liczb całkowitych.

Rozwiązanie problemu nr 2

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
191665617191551159474685976406817869579594726
0000000000000000000000000000000
  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
Mnożenie dużych liczb
(C)2020 mgr Jerzy Wałaszek

 

 

.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2022 mgr Jerzy Wałaszek

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.