Potęgowanie dużych liczb


Tematy pokrewne
Ł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

Obliczyć xy, gdzie x jest dowolnie dużą nieujemną liczbą całkowitą, a y jest względnie małą nieujemną liczbą całkowitą, np. 32-bitową.

 

 

Normalnie potęgowanie an całkowite wymaga wykonania n-1 mnożeń przez a:

 

 

Mnożenie dużych liczb jest bardzo kosztowne czasowo. Istnieje zatem naturalne pytanie, czy takiej operacji potęgowania nie można wykonać przy mniejszej liczbie mnożeń. Okazuje się, że tak – postąpimy podobnie jak przy mnożeniu – przedstawimy potęgę w postaci sumy potęg liczby 2. Wykorzystamy prostą własność potęgowania:

 

 

Niech:

 

gdzie bii-ty bit liczby b, i = 0,1,...,31 dla liczb 32-bitowych.

 

 

Jeśli dokładnie się przyjrzysz ostatniemu wzorowi, to powinieneś spostrzec, że zbudowany on jest z iloczynu wyrażeń:

 

 

Kolejne wartości potęg w prosty sposób obliczamy dynamicznie:

 

 

Bity bi wydzielamy z b za pomocą koniunkcji oraz przesuwu w prawo w identyczny sposób jak przy mnożeniu.

Możemy już przystąpić do konstrukcji algorytmu potęgującego.

 

Algorytm potęgowania 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 potęgi ab
a – zawartość nieokreślona
b – zawiera zero

Elementy pomocnicze:
mnóż(x,y)  –  mnoży dwie duże liczby jako łańcuchy i zwraca wynik jako łańcuch
Lista kroków:
K01: w ← "1" ; ustawiamy wynik na 1
K02: Jeśli (b and 1) = 1, to w ← mnóż(w,a) ; jeśli bit bi = 1, to wymnóż w przez ai
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 ← mnóż(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 a i b. Pierwsza o dowolnej ilości cyfr. Druga w zakresie od 0 do 4294967295. Oblicza ab i wypisuje wynik.

Uwaga: potęgi dużych liczb mogą wymagać bardzo długiego czasu obliczeń, a wynik nie będzie się mieścił w oknie konsoli.

 

Lazarus
// Potęgowanie dużej liczby przez małą
// Data: 24.10.2012
// (C)2012 mgr Jerzy Wałaszek
//---------------------------------------

program bigpower;

// 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_ab(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_ab := w;    // zwracamy wynik mnożenia

end;

// Mnoży dwie duże liczby
//-----------------------
function mnoz(var a,b : ansistring) : ansistring;
var
  c,w,z : ansistring;
  i : dword;
begin
  // mnożymy

  w := '0';

  z := '';

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

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

end;

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

var
  a,w : ansistring;
  b   : dword;

begin

  // odczytujemy dane

  readln(a);  // duża liczba
  readln(b);  // mała liczba

  // potęgujemy

  w := '1';

  while true do
  begin
    if (b and 1) = 1 then w := mnoz(w,a);
    b := b shr 1;
    if b <> 0 then a := mnoz(a,a) else break;
  end;

  // wypisujemy wynik

  writeln(w);
  
end.
Code::Blocks
// Potęgowanie dużej liczby przez małą
// Data: 24.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_ab(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
}

// Mnoży dwie duże liczby
//-----------------------
string mnoz(string & a, string & b)
{
  string c,w,z;
  int i;

  // mnożymy

  w = "0";

  z = "";

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

  return w;  // zwracamy wynik mnożenia
}

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

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

  // odczytujemy dane

  cin >> a;  // duża liczba
  cin >> b;  // mała liczba

  // potęgujemy

  w = "1";

  while(true)
  {
    if(b & 1)   w = mnoz(w,a);
    if(b >>= 1) a = mnoz(a,a); else break;
  }

  // wypisujemy wynik

  cout << w << endl;

}
Free Basic
' Potęgowanie dużej liczby przez małą
' Data: 24.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_ab(ByRef x As String, ByVal b As UInteger) As String

  Dim As String a,w

  a = x
  
  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_ab = w       ' zwracamy wynik mnożenia

End Function

' Mnoży dwie duże liczby
'-----------------------
Function mnoz(ByRef a As String, ByRef b As String) As String

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

  ' mnożymy

  w = "0"

  z = ""

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

  mnoz = w

End Function

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

Dim As String a,w
Dim As UInteger b

' odczytujemy dane

Open Cons For Input As #1

Line Input a ' duża liczba
Input #1,b   ' mała liczba

Close #1

' potęgujemy

w = "1"

while 1
  If (b And 1) = 1 Then w = mnoz(w,a)
  b Shr= 1
  If b = 0 Then Exit While
  a = mnoz(a,a)
Wend

' wypisujemy wynik

Print w

End
Wynik
123456
123
18030210630404480750814092786593857280734268863855968048844015985795850236081373
25021978269698632257308716304364197947589320743503803676976498146265429266026647
07275874269201777743912313197516323690221274713845895457748735309484337191373255
52792827178520638296799898433048210535094222997067705494083821093695230393940165
67561276077785996672437028140727462194319422930054164116350760212960454933051336
45615566590735965652587934290425473827719935012870093575987789431818047013404691
79577317040576461464605494929884618467829681362559533331161138525173524450544844
3050050547161779229749134489643622579100908331839817426366854332416

 

Potęga dużej liczby przez małą
(C)2012 mgr Jerzy Wałaszek

Duża liczba →

Mała liczba →

.

 



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.