How to do exponentiation using multiplication in Portugol as arithmetic operation?

Question

I need to make a pseudocode that has numero1 and numero2 (have to be natural numbers less than 50), need to raise the numero1 at the numero2, just using the multiplication operation, and show the result. How do?

Answer 1

You want to do the exponentiation of two numbers natural? Luckily, I already have dealt with a problem recently which involved calculating the exponential of two real numbers. For this, I needed the definition of exponentiation, which is given using a non-zero natural exponent and, only after the definition, is extrapolated to all other numbers. Worth checking out the answer given, is an enabler and deals with various mathematical subjects.

In the other answer, I set exponentiation like this:

Natural exponentiation equals direct point (disregard 0 as natural now). The exponent indicates how many times you should multiply the base in the following algorithm [for the form b^n]:

1. if n == 1, return b
2. otherwise, return b * b^(n-1)

This can be transformed into pseudocode (using Python as a basis):

def pow(b, n):
  if n == 1:
    return b
  else:
    return b*pow(b, n-1)

In one more dialect pythonic:

def pow(b, n):
  return b if n == 1 else b*pow(b, n-1)

So with a simple recursion we would solve the problem, right? In fact, it is still necessary to trim some edges. The first is the case of 0. In the answer quoted at the beginning of this one I explain how to arrive at the convention that any number different from 0 to 0 is 1.

One of the other edges is that we could have an algorithm that runs in a much shorter time, more specifically in o(log n) multiplications. This algorithm makes use of the division and conquest strategy using a species of meoization. The idea is this:

To calculate b^2n, if I’ve ever calculated b^n, just do b^n * b^n

Note how the number of transactions has now decreased sharply. Before, when reaching the conclusion of the value of b^n, you would still need to do more n multiplications to reach in b^2n. Now in only one operation you get b^2n. The pseudocode looks like this (already dealing with cases of odd exponent):

def pow(b, n):
  if n == 0:
    return 1
  b_to_half_n = pow(b, n//2)
  b_to_double_half_n = b_to_half_n * b_to_half_n
  if n % 2 == 1:
    b_to_double_half_n *= b
   return b_to_double_half_n

Another point would be... maybe recursion was considered a cheat? Well, then we would need to resort to ties. Fortunately tail recursion (like the first version of the algorithm it makes o(n) multiplications) is easy to turn into loop. We can use the following meta-algorithm:

1. takes the base case and stores it in the variable retorno
2. as a condition of while the condition of the basic case denied
3. accumulate the non-rerecursive part in the variable retorno according to the recursive formula, then make the parameters be updated before starting another iteration
4. return the return variable

Applying this meta-algorithm, we get this (already getting the basic case of exponent 0):

def pow(b, n):
  retorno = 1
  while n != 0:
    retorno *= b
    n -= 1
  return retorno

Well, it’s inefficient compared to another version but it’s definitely not cheating. So, there’s still one more edge?

Yes, there is. And this edge is a big one. I should even say that it was a prank by those who passed the activity. If you take the extreme case of the entrances (b == 49 and n == 49, as in the description of entries the numbers are under 50, therefore excluding equality), you need to 49 * log2(49) ~= 276 bits to represent the magnitude of that number! Taking into account that one of the bits is not used for value (the call of signal bit), 277 bits are needed! Only the case of 2^49 implies using numbers of at least 51 bits to be able to represent that number. These numbers exceed the typical 32 bits to store the integers in Portugol (source)

So, what does that mean? Basically it means that you should implement your own number using lists or vectors, an implementation called BigInteger. For this number, of all the luck you should initially implement the sum before even having the multiplication available to be used. And ask "how to implement a BigInteger from scratch?" is somewhat too broad for the website format.

Answer 2

I believe that’s what you’re looking for:

Follow below Code used:

algoritmo "semnome"
// Função : Exponenciação por Multiplicação
// Autor :  Paulo Vieira
// Data : 20/03/2018
// Seção de Declarações 
var
   Potencia, Base, Resultado, Contador: INTEIRO

inicio
// Seção de Comandos 
   Repita
       Limpatela
       Escreval("----------------------------")
       Escreva("Informe o número base:")
       Leia(Base)
   Ate Base < 51

   Repita
       Limpatela
       Escreval("----------------------------")
       Escreva("Informe a potência desejada:")
       Leia(Potencia)
   Ate Potencia < 51

   Limpatela
   Escreval("-----------")
   Escreva("A Base é")
   Escreval(Base)
   Escreval("-----------")
   Escreva("A Expoente é")
   Escreval(Potencia)
   Escreval("-----------")

   Resultado <- 0

   Para Contador de 1 ate Potencia Faca
        Se Resultado <> 0 entao
           Resultado <- Resultado * Base
        Senao
           Resultado <- Base * Base
        FimSe
   FimPara

   Escreval("-------------------------------")
   Escreva("O Resultado da operação é")
   Escreval(Resultado)
   Escreval("-------------------------------")
fimalgoritmo

Answer 3

I don’t know if that would help you, but the function would look something like this, using the power function.

By doing multiplication, you would have to multiply the value of your base by the amount of times of your power using a for:

//algoritmo "Potencia"
var
   numero1,numero2:INTEIRO
   potencia:INTEIRO

inicio
// Seção de Comandos
   Escreva("informe um numero para a base de uma potencia")
           Leia(base)
           Para aux de 1 ate 50 passo 1 FACA
           potencia<-numero1^numero2
           escreval("a potencia de " ,numero1, " elevado " ,numero2," e ",potencia)
           fimpara