Mnożenie dużych liczb


Tematy pokrewne   Podrozdziały
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie
  Problem 1
Problem 2
 

Problem 1

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

 

 

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 liczby 2 mnożonych przez kolejne bity bi 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 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.:

 

 

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
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, to w ← dodaj(w,a) ; jeśli bit bi = 1, to dodaj ai do w
K03: bb 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 ai
K06: Idź do K02 ; kontynuuj pętlę

 

Program

Ważne:

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.

 

Lazarus
// Mnożenie dużej liczby przez małą
// Data: 23.10.2012
// (C)2012 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.
Code::Blocks
// Mnożenie dużej liczby przez małą
// Data: 23.10.2012
// (C)2012 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;

}
Free Basic
' Mnożenie dużej liczby przez małą
' Data: 23.10.2012
' (C)2012 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)2012 mgr Jerzy Wałaszek

Duża liczba →

Mała liczba →

.

 

Problem 2

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

 

 

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 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 K05...K08 ; przetwarzamy cyfry w b
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  

 

Program

Ważne:

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.

 

Lazarus
// Mnożenie dużych liczb
// Data: 23.10.2012
// (C)2012 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.
Code::Blocks
// Mnożenie dużych liczb
// Data: 23.10.2012
// (C)2012 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;
}
Free Basic
' Mnożenie dużych liczb
' Data: 23.10.2012
' (C)2012 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)2012 mgr Jerzy Wałaszek

 

 

.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.