How to do exponentiation using as an arithmetic operation the multiplication in Portugol? [closed]

Do you want to exponentiate two natural numbers? Luckily, I already dealt with a problem recently that involved calculating the exponential of two real numbers. For this, I needed the definition of exponentiation, which is given using non-zero natural exponent and, only after definition, is extrapolated to all other numbers. It pays to check answer given , is great and deals with a variety of mathematical subjects.

On the other answer, I defined exponentiation like this:

  

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

     

If n == 1 , return b

  

otherwise, return b * b^(n-1)

  

This can be turned into pseudo-code like this (using Python as a base):

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

In a 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 one arrives at the convention that any number other than 0 raised 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 % with% multiplications. This algorithm assumes the strategy of division and achievement using a species of meoisation . The idea is as follows:

  

To calculate o(log n) , if I have already calculated b^2n , just do b^n

Notice how the number of operations has now declined sharply. Before reaching the b^n * b^n value, you'd still need to do%% of% multiplication until you get b^n . Now in only one operation you get n . 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 that ... maybe recursion was considered cheating? Well, then we would have to resort to ties. Fortunately tail recursion (as the first version of the algorithm that does b^2n multiplications) is easy to turn into loop. We can use the following meta-algorithm:

Applying this meta-algorithm, we get this (already taking 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 sure is not cheating. So, does it still have one more edge?

Yes, there is. And that edge is great. I might even say that it was a trick of the person who passed the activity. If you take the extreme case of the entries ( while and retorno , since in the description of the entries the numbers are less than 50 , therefore excluding equality), you need b == 49 bits to represent the magnitude of that number! Given that one of the bits is not used for value (the signal bit in>), it takes 277 bits! Only the case of n == 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 integers in Portugol ( source )

So what does that mean? Basically it means you should implement your own number using lists or vectors, an implementation called 49 * log2(49) ~= 276 . For this number, of all luck you should initially implement the sum before even having the multiplication available to be used. And ask "how do you implement a 2^49 of zero?" is a little too broad for the format of the site.

I think that's what you're looking for:

FollowbelowCodeused:

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

I do not know if this would help, but the function would look more or less like this, using the power function.

Doing with multiplication, you would have to multiply the value of your base by the amount of times its power by 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