Algorytmy i Struktury Danych - Potęgowanie dużych liczb

Normalnie potęgowanie aⁿ 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_i – i-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.

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, ; jeśli bit b_i = 1, to wymnóż w przez a_i
     to w ← mnóż(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 ← mnóż(a, a) ; oblicz kolejne a_iK06: 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

Python (dodatek)

# Potęgowanie liczb całkowitych
# Data: 3.04.2024
# (C)2024 mgr Jerzy Wałaszek
#------------------------------
# odczytujemy dane
a = int(input()) # liczba
b = int(input()) # potęga

# potęgujemy
w = 1
while True:
    if b & 1: w *= a
    b >>= 1
    if b > 0: a *= a
    else: break
# wypisujemy wynik
print(w)
print()

Wynik:

123456
123
18030210630404480750814092786593857280734268863855968048844015985795850236081373
25021978269698632257308716304364197947589320743503803676976498146265429266026647
07275874269201777743912313197516323690221274713845895457748735309484337191373255
52792827178520638296799898433048210535094222997067705494083821093695230393940165
67561276077785996672437028140727462194319422930054164116350760212960454933051336
45615566590735965652587934290425473827719935012870093575987789431818047013404691
79577317040576461464605494929884618467829681362559533331161138525173524450544844
3050050547161779229749134489643622579100908331839817426366854332416

JavaScript

<html>
  <head>
    <title>
      Potęga
    </title>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align: center;
               background-color:
               #E7E7DA"
        class="nomargin">
          <b>
          Potęga dużej liczby
          przez małą
          <br/></b>(C)2026
          mgr Jerzy Wałaszek<hr>
		  <table border="0"
		  id="table268"
		  cellpadding="0"
		  style="border-collapse:
		         collapse"
		  bgcolor="#E7E7DA"
		  class="nomargin">
            <tr>
              <td valign="top"
                  style="text-align:
                         right"
                  nowrap>
                &nbsp;&nbsp;
                Duża liczba =
                <input
                type="text"
                name="inp_a"
                size="80"
                value="123456"
                style="text-align:
                       right;">
                &nbsp;<br>
                Mała liczba =
                <input
                type="text"
                name="inp_b"
                size="25"
                value="123"
                style="text-align:
                       right;">
                &nbsp;
              </td>
            </tr>
          </table>
          <hr>
          <input
          type="button"
          value="Potęguj"
          name="B1"
          onclick="main()">
          <hr>
          <b>Wynik:</b>
          <div align="center">
            <table
            border="0"
            cellpadding="4"
            style="border-collapse:
                   collapse"
            class="small">
              <tr>
                <td id="out">&nbsp;</td>
              </tr>
            </table>
          </div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script language=javascript
        type=text/javascript>

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

// Oblicza sumę podanych liczb
//----------------------------
function dodaj(x, y)
{
  let z, 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  = x.charCodeAt(--i) + 
         y.charCodeAt(--j) + 
         p - 96;
    p  = Math.floor(w / 10);
    z = (w % 10) + z;
  }

  while(i)
  {
    w  = x.charCodeAt(--i) + 
         p - 48;
    p  = Math.floor(w / 10);
    z = (w % 10) + z;
  }

  while(j)
  {
    w  = y.charCodeAt(--j) + 
         p - 48;
    p  = Math.floor(w / 10);
    z = (w % 10) + z;
  }

  if(p) z = p + z;
  if(z == "") z = "0"
  
  // zwracamy wynik dodawania
  return z

}

// Mnoży dużą liczbę a
// przez małą b
//--------------------
function mnoz_ab(a, b)
{
  // zerujemy łańcuch wyjściowy
  var w = "0";

  // wykonujemy mnożenie
  while(true)
  {
    if(b & 1)
      w = dodaj(w, a);
    if(b>>= 1)
      a = dodaj(a, a);
    else
      break;
  }

  // zwracamy wynik mnożenia
  return w
}

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

  // mnożymy
  w = "0";
  z = "";
  for(i = b.length - 1;
      i >= 0;
      i--)
  {
    c = mnoz_ab(a, b
               .charCodeAt(i) -
               48) + z;
    w = dodaj(w, c);
    z += "0";
  }
 
  // zwracamy wynik mnożenia
  return w;
}

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

function main()
{
  var a,w,b,i,test;

  // Odczytujemy dane:
  // duża liczba
  a = document.frm.inp_a.value;
  // mała liczba
  b = parseInt(document.frm
               .inp_b.value);
  test = true;
  for(i = 0;
      i < a.length;
      i++)
    if(a.charAt(i) < '0' ||
       a.charAt(i) > '9')
    {
      test = false;
      break;
    }
  // potęgujemy
  if(!isNaN(b) && test)
  {
    w = "1";
    while(true)
    {
      if(b & 1)
        w = mnoz(w, a);
      if(b>>= 1)
        a = mnoz(a, a);
      else break;
    }

    // wypisujemy wyniki
    t = "<pre>";
    c = 0;
    for(i = 0;
        i < w.length;
        i++)
    {
      t += w.charAt(i)
      if(++c == 80)
      {
        c = 0;
        t += "<br/>";
      }
    }
    t += "</pre>";
    document.getElementById("out")
    .innerHTML = t;
  }
  else
    document.getElementById("out")
    .innerHTML = "<span style=" +
                 "'color:Red'>" +
                 "Złe dane!" +
                 "</span>";
}

</script>

  </body>
</html>

do podrozdziału do strony

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.

Potęgowanie dużych liczb