converting a c++ formula into javascript

Question

Whilst studying recursion, I attempted to get a C++ example function working in javascript.

The original function (from Stanford CS106B) is here:

int Raise (int base, int exp)
{
    if (exp == 0)
        return 1;

    else
    {
        int half = Raise(base, exp/2);  
        if (exp % 2 === 0)
            return half * half;
        else
            return base * half * half;
    }
}

Raise(3,5);

My version below recurses far too many times. What fundamental thing have I messed up? I bet it's the line with var half... I've never tried to assign a function to a variable, so that's also new territory...

function Raise (base, expo)
{
    if (expo === 0)
        return 1;

    else
    {
        var half = Raise(base, (expo/2));  

        if (expo % 2 === 0)
            return half * half;
        else
            return base * half * half;
    }
}

Raise(3,5);

Ted Hopp · Accepted Answer · 2013-08-19 07:36:42Z

9

JavaScript does not have integer division, so this line:

var half = Raise(base, (expo/2));

does not do the same thing in JavaScript as the corresponding line in C++. (If, for instance, expo === 5, it would recurse with a value of 2.5 for the second argument instead of the intended 2.) You can have the same effect as integer division by 2 if you use the >> operator:

var half = Raise(base, expo >> 1);

P.S. I should mention that in the general case, you can do integer division using Math.floor (or Math.ceil if the numerator and denominator have opposite signs). The bit-level operators also convert their arguments to integers if necessary, so you can use ((a/b)|0) to get the integer part of the quotient a / b. You then don't have to worry about signs.

P.P.S. It would probably be a tiny bit faster to use

if ((expo & 1) === 0)

rather than

if (expo % 2 === 0)

to test whether expo is even. (A similar thing goes for the C++ code.)

edited Aug 19, 2013 at 7:36

answered Aug 19, 2013 at 7:10

Ted Hopp

235k48 gold badges412 silver badges533 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Elias Van Ootegem Over a year ago

+1, beat me to it. I was off writing a rant on Raise needing to be underCased, and JS's number type vs int, double and float

dwilbank Over a year ago

ah - embarrassing - I should have known javascript didn't have integer division after all my other exercises. Thanks!

Oleg Over a year ago

Just in case OP/someone else is not attached to division by 2: remember that Math.floor() rounds towards negative infinity, which may be an unexpected result. E.g.: Math.floor(5/2) evals to 2 while Math.floor(-5/2) evals to -3! In case you were after "more conventional" rounding towards zero, you can use either ~~(5/2) or (5/2) >> 0; both look cool :)

Ted Hopp Over a year ago

@o.v. - That was what my P.S. was about, but I expanded it to include your point. If the numerator and denominator of the division have opposite sign, the quotient will be negative and Math.ceil will then truncate (round toward +Infinity, which will also be toward 0 as desired). The bit tricks (~~, >> 0, |0, etc.) can also be very confusing to someone casually reading the code.

Collectives™ on Stack Overflow

converting a c++ formula into javascript

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related