Software engineer student here. Just had a test. Do Cred Forums consider the following question hard:

So pow(2,3) = 16? Seems a bit off there. Nevermind what happens if e is negative.

function Pow (Base : in Integer; Exp : in Natural) return Integer is
begin
if Exp = 0 then
return 1;
else
return Mult (Base, Pow (Base, Exp - 1));
end if;
end Pow;

>Create a recursive function of power - the second number is the power: ex. pow(2,3).
>You can use a pre wrote multiply function - ex: mult(2,2).
this is a problem from one of the early chapters of SICP.

The real test of quality is whether their solution is O(n) or more optimal. The "trivial" solution most people would submit is not the optimal one.

pow(2, 0)
pow(.5, -1)
pow(9, .5)

:^)

any way, here's how I did it
#BASE
pow(x,0) = 0
pow(x,1) = x

pow(x,n) = mult(x,pow(x,n-1))

thats basically how you do it

by the way, the function was for positive numbers only

x^0 = 1 you retard

felt pretty good about my self for coming up with that on the spot. =)

>induction
i think everyones missing this part

But what about if x = 0 user? :^)

ops

>Software engineer student
you probably should not call yourself this just yet

0^0 is undefined, so return a NaN

it's still 1, user

Check the OP again. Just says to create a recursive function. Doesn't say anything about the tools available, and by being a software engineering student implies that programming would be involved.

man, I had a a bit more than an hour to finish my exam, haha.

he said he had to use induction in a later post

(define (pow x y)
(if (= y 1)
x
(pow (mult x x) (- y 1)))

not very hard at all

(pow x 0)

ah I just realized this is iterative I guess I'm retarded

Christ user, you made the exact same mistakes as did.

Why recursive?
I just tried this and it ended up with some really inelegant shit just to prevent from clobbering the value i'm multiplying.
int pow_r(int b, int e, int result)
{
if (!e)
return result;
else
pow_r(b, e - 1, result * b);
}

Look how much nicer iteration is.
int pow_iter(int b, int e)
{
int result = b;
while (--e)
result *= b;
return result;
}

I do have a lot of them written in java some where, let me look.

because the question he was asked was prolly a math problem not a programming problem.

class Operacoes{

public static int Suc(int n){
return n+1;
}

public static int Ant(int n){
return n-1;
}
/* números positivos
public static int Add(int a, int b){
int soma;
if(a == 0 && b == 0){
soma = 0;
}else if(b != 0){
soma = Suc( Add(a,b-1) );
}else{
soma = Suc( Add(a-1,0) );
}
return soma;
}*/
public static int Add(int a, int b){
int soma;
if(b > 0){
soma = Suc( Add(a, b-1) );
}else if(b < 0){
soma = Ant( Add(a, b+1) );
}else{
soma = a;
}
return soma;
}

public static int Sub(int a, int b){
int subtracao;
if(b > 0){
subtracao = Ant( Sub(a, b-1) );
}else if(b < 0){
subtracao = Suc( Sub(a, b+1) );
}else{
subtracao = a;
}
return subtracao;
}

public static int Mult(int a, int b){
int multiplicacao;
if(b == 0){
multiplicacao = 0;
}else{
multiplicacao = Add(a, Mult(a, b-1) );
}
return multiplicacao;
}

public static int Pot(int a, int b){
int potencia;
if(b == 0){
potencia = 1;
}else{
potencia = Mult(a, Mult(a, b) );
}
return potencia;
}

public static int Div(int a, int b){
int divisao;
if(a < b){
divisao = 0;
}else{
divisao = Suc( Div(a-b, b) );
}
return divisao;
}

public static void main(String[] args){

System.out.println( Add(2,5) );
System.out.println( Mult(2,5) );
System.out.println( Pot(2,2) );
System.out.println( Div(10,2) );
System.out.println( Sub(4,2) );

}

}

Wait a minute...

>Software engineer
Code monkey.
>Do Cred Forums consider
>pre wrote multiply function
Broken English.
>ex. pow
>ex: mult
Inconsistent.

...PAJEET!

Never mind that writing such a function in terms of structural induction might as well be pseudocode. Fits right in with Haskell, for example.

int pow(float x, int n)
{
if (n == 0) {
return 1;
} else if (n == 1) {
return x;
} else if (n == -1) {
return 1/x;
} else if (n > 1) {
return x * pow(x, n-1);
} else {
return 1/x * pow(x, n+1);
}
}

Easy as shit... this exact problem is taught at most universities as a measure of runtime analysis comprehension

Wtf are you on?

nope

This guy gets it, except the trivial solution actually doesnt run (2^n recurrance)

>pow(x,0) = 0
How do retards like you get a job and I cant find one with a bachelors and a portfolio?

>DURRR Exponents are hard

>Why recursive?
Because the recursive solution in this case (for the efficient version) is easier implemented than an iterative variant

nope

What language are you using?

i just made a mistake on pow(x,0), i had an hour to complete my test

double pow(double x, int n)
{
if (n == 0) {
return 1;
} else if (n == 1) {
return x;
} else if (n == -1) {
return 1/x;
} else if (n > 1) {
return x * pow(x, n-1);
} else {
return 1/x * pow(x, n+1);
}
}

Not sure how to write pseudo-algorithms
pow(x,y):
if (y == 0) return 1
if (y % 2) return mult(x,pow(x,y-1))
p = pow(x,y/2)
return mult(p,p)

Sorry if wrong, typing on phone :-)

def pow(b,p):
if (p == 1): return b
if (b == 0): return 0
if (p%2 == 1) :
return mult(b,pow(mult(b,b),mult(p,0.5)))
else:
return pow(mult(b,b),mult(p,0.5))

Assuming things like:
a) you must multiply using the "prewrote" function and
b) you will not be getting negative or fractional powers

this is a math problem that is used in computer science. if youre solving this problem without using a base case and an induction step the question is wrong.

yes, I used them.

My Computer Science One exams were pretty weird. In the first exam for Computer Science One he asked for a Haskell function that could change a decimal number into a number of every other number system like the octal system for example. Thing is my professor expected everybody to know how to do that without explaining the method. He had to go around during the exam and explain how you calculate such things.

Another programming task which looked for the best combination could be solved by writing five nested for loops.

I naturally failed and had to go into the second try. It seemed like the professor lost his faith in us since the tasks this time consisted in returning the first and the last element of a list in Haskell and similar easy questions. 60% got the best grade. Me included. Must have sucked for those who passed it the first time. I've never had an easier exam again.

Its not just a test of a base case, though... this is a famous CS problem because it test a coder's ability to take into account the number of steps (as an asymptotic function of input size).

For example:

def pow(b,p):
if p == 1: return b
if b == 0: return 0
if (p%2 == 1): return b*(pow(b,p/2)*pow(b,p/2))
else: return pow(b,p/2)*pow(b,p/2)

Is a technically* correct mathematical answer, but if you look closely, what happens from a CS standpoint is the following:

Consider a small "b" (1+ε) and a very large p (100 or greater should do the trick for a test run). There is essentially a call to pow() for every *unit* of p, which is bad, because in computer world, that means that the algorithm takes O(2^n) steps to complete, or in other words, every time you increase the input value by 1, the time it takes to complete this algorithm effectively doubles.

I was going to post my entire exam here, but it's in Portuguese so, never mind.

>this is a famous CS problem
>that means that the algorithm takes O(2^n) steps to complete

right thats what theyre trying to show but if a student is asked to specifically use induction they need to show logically why the algorithm does what it does not just write the algorithm. in order to do this is need to define the base case and induction step because the problem is rooted in logic and math not in programming.

I should note *why* this algorithm takes 2^n steps to complete.

Basically, a number can be stored in binary in log_2(n) bits for a number n. Consider 1024, which is 2^10. You can store this in 10 bits, because 2^(log_2(k)) = k. Thus, the problem we have with this algorithm is that at each step, if you were to "break" the work into two recursive function calls (consider only p's which are powers of 2, for simplicity) each "arm" is going to do half the work, but what have you really done? The same amount of work is being done on both sides (which is wasteful to say the least) but each of those works in the same way... by breaking up the work in half (until the base case is reached). In essence, no "work" is actually being saved.

If you divide 64 into two halves, you get 2 "arms" of 32... repeat and you will eventually get 16 calls to pow(2,2), which is a lot (just to compute '4' over and over again!) If you draw it out, though, you will see that you get a multiplication for each "unit" of p... meaning that if p=1024, you will take 1024 multiplications (and calls to pow() which are expensive!). This is bad because, while in our scenario, p is relatively small, if we were to amp up p to 1,000,000,000,000, our program would take quite a bit of time.

To contrast, the alg I posted here:
Does log_2(n) multiplications, total, which is obviously better. If each operation takes 1 CPU clock cycle, for p=1,000,000,000,000,000, my alg would take roughly 50 units of time (technically less, since 10^15 < 1024 ^ 5) whereas the other one would take 1,000,000,000,000,000 clock cycles

wtf are you on about? You don't need induction to prove the recurrence in this problem... you can use the recurrence...

T(n) = 2 * T(n/2) = 2^k * T(1), k=log_2(n)

Errr... fucked that up

T(n) = 2*T(n-1) = 2^k*T(1),k=n
-> T(n) = O(2^n)

yea you can use recurrence but if you read in a later post user said he had to use induction

you can't use *. Just + to increment until the algorithm is finished. you can write a function MULTIPLY or SUM, etc... and call it inside another function recursively.

>Java

You got me xD

not enough sir desu

en.wikipedia.org/wiki/Recursive_definition

just an example I did when I was studying for the test

>creative a recursive function
>recursive
>>recursion
D r o p p e d
r
o
p
p
e
d

So you want something better than O(n)/O(n) time/space? 'Kay.

function Pow (Base : in Integer; Exp : in Natural) return Integer is

function Pow_Tail (Base, Result : in Integer; Exp : in Natural) return Integer is
begin
if Exp = 0 then
return Result;
elsif Exp mod 2 = 1 then
return Pow_Tail (Base * Base, Base * Result, Exp / 2);
else
return Pow_Tail (Base * Base, Result, Exp / 2);
end if;
end Pow_Tail;

begin

return Pow_Tail (Base, 1, Exp);

end Pow;

>algorithm takes O(2^n)
Only applies for languages with side effects where the compiler can't assume referential transparency.

that's pretty easy bro.