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

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Potęgowanie dużych liczb

SPIS TREŚCI

Problem

Należy obliczyć wartość potęgi x y, gdzie x  jest dowolnie dużą nieujemną liczbą całkowitą, a y  jest względnie małą nieujemną liczbą całkowitą, np. 32-bitową.

Rozwiązanie

Normalnie potęgowanie a n 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 b ii-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 b i 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 a b
a  – zawartość nieokreślona
b  – zawiera zero

Zmienne 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 b i = 1, to wymnóż w przez a i
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  ← mnóż ( 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 a i b. Pierwsza o dowolnej ilości cyfr. Druga w zakresie od 0 do 4294967295. Oblicza a b 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.
Pascal
// Potęgowanie dużej liczby przez małą
// Data: 24.10.2012
// (C)2020 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.
C++
// Potęgowanie dużej liczby przez małą
// Data: 24.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_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;

}
Basic
' Potęgowanie dużej liczby przez małą
' Data: 24.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_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)2020 mgr Jerzy Wałaszek

Duża liczba →

Mała liczba →

.

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