Software engineer student here. Just had a test. Do /g/ consider

File: DumbFrog.png (246KB, 550x535px) Image search: [Google]

246KB, 550x535px

>pre wrote

>>56722211
It seems pretty easy. Do you have to do it on paper or computer?

def pow(b,e):
    return pow(mult(b,b),e-1) if e > 1 else b

???

thats not hard. if youre just learning tho it can be.

>>56722244
oh wait this doesnt work
fuck

>>56722244
withou the use of code, anon.
just using deduction and induction

>>56722239
paper, with no actual code
just deduction and induction

induction tripped me up a lot in discrete math.

>>56722211
>>56722271
if b=1 return a
else return a * pow(a,b-1)

>>56722244
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;

>>56722211
>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.

>>56722312
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))

>>56722352
thats basically how you do it

by the way, the function was for positive numbers only

>>56722352
x^0 = 1 you retard

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

>>56722287
>induction
i think everyones missing this part

>>56722377
But what about if x = 0 anon? :^)

>>56722377
ops

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

>>56722399
0^0 is undefined, so return a NaN

>>56722399
it's still 1, anon

>>56722393
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.

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

>>56722425
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

>>56722458
(pow x 0)

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

>>56722458
Christ anon, you made the exact same mistakes as >>56722244 did.

>>56722211
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.

>>56722492
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 /g/ consider
>pre wrote multiply function
Broken English.
>ex. pow
>ex: mult
Inconsistent.

...PAJEET!

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

>>56722211

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);
    }
}

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

>>56722244
Wtf are you on?

>>56722332
nope

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

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

>>56722458
>DURRR Exponents are hard

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

>>56722512
nope

What language are you using?

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

>>56722582

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 :-)

>>56722716

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

>>56722716
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.

>>56722833
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.

>>56722833
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.

>>56722976
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:
>>56722831
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

>>56723123
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)

>>56723170
Errr... fucked that up

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

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

>>56723170
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.

>>56722521
>Java

>>56722530
You got me xD

>>56722530
not enough sir desu

https://en.wikipedia.org/wiki/Recursive_definition

>>56723251
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

>>56722716
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;

>>56722976
>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.