-2
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?
-2
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?
2
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
]:
- if
n == 1
, returnb
- 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 calculatedb^n
, just dob^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:
retorno
while
the condition of the basic case deniedretorno
according to the recursive formula, then make the parameters be updated before starting another iterationApplying 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.
0
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
-2
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
I think you don’t understand the question. The allowed operation is multiplication, you used exponentiation. 50 is also unrelated to the amount of steps in the program (therefore it should not be directly in the for
), but maximum limits for input numbers.
Browser other questions tagged mathematics portugol
You are not signed in. Login or sign up in order to post.
What have you tried?
– Leandro Angelo