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

©2024 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:

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 bi liczby b:

b = b31·231+b30·230+…+b2·22+b1·21+b0·20

Teraz możemy zapisać:

W = a·(b31·231+b30·230+…+b2·22+b1·21+b0·20)
W = a·b31·231+a·b30·230+…+a·b2·22+a·b1·21+a·b0·20

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

W = b31·231·a+b30·230·a+…+b3·23·a+b2·22·a+b1·21·a+b0·20·a
W = b31·231·a+b30·230·a+…+b3·8a+b2·4a+b1·2a+b0·a

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

a0 = a
a1 = 2a = a0+a0
a2 = 4a = a1+a1
a3 = 8a = a2+a2
a30 = 230a = a29+a29
a31 = 231a = a30+a30

Iloczyny dodajemy do wyniku W, jeśli odpowiedni bit bi 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.
: 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 bi = 1, to dodaj ai 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 ai
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
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

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
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 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:   cc+z ; dołączamy zera w celu przesunięcia tego iloczynu
K07:   w ← dodaj(w,c) ; iloczyn dodajemy do wyniku
K08:   zz+"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

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
©2024 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.