OSDev.org

Brendan wrote:To work out powers, there's the simple way like this:

Code: Select all

int pow(int a, int b) {
    int result = 1;

    while(b < 0) {
        result /= a;
        b++;
    }
    while(b > 0) {
        result /= a;
        b--;
    }
    return result;
}

A faster way might go something like this:

Code: Select all

int pow(int a, int b) {
    int result;

    if(b == 0) return 1;
    if(b > 0) {
        temp = a;
    } else {
        temp = 1 / a;
    }
    do {
        if( (b & 1) != 0) result *= temp;
        b = b >> 1;
        temp *= temp;
    } while(b != 0);
    return result;
}

2 problems (1 addressed I think though). In your first code, I'm no mathematician, but don't you actually have to multiply eventually to reach a power of an integer? I think you're using negative integer algorithms on both negative and positive integers. =)
The other is that you use result undefined in the optimized function, I'm assuming it should be 1?

Regardless, thanks. I should have read through this thread a little closer. I'm going to implement this in assembly and hope I transcribe it correctly. =)

Brendan wrote: Note: I did test a few positive exponents using this method (on paper) and got the right answer; and there is a bug for negative exponents in the code I posted (for negative exponents, you'd need to negate the exponent before doing the final loop). I'd also assume that (for e.g.) a maximum of 31 multiplications instead of a maximum of over 2 billion multiplications would make a significant performance difference (e.g. enough to make it worth researching/testing my theory).

lol agreed, I think that would be a decent performance increase.
Although, I'm still impressed by the increase from moving my code from C to assembly and using the carry flags.

Brendan wrote: However, this code won't work in some cases - the exponent must be an integer (e.g. something like "5 ** 2.25" won't work). I'm not sure if there's a trick I'm missing or some other way to handle this case. I do realize that (for e.g.) "5 ** 2.25 = (5 ** 2) * (5 ** 0.25)" and that "5 ** (-2.25) = (5 ** (-2) ) * (5 ** (-0.25) )", but I can't think of an easy way to calculate the result when the exponent is between -1 and 0 or between 0 and 1.

this is probably a stupid question, but how exactly would one have a multi-precision non-integer? how can there be a fraction in an integer array posing as one big integer?

Hi,

01000101 wrote:this is probably a stupid question, but how exactly would one have a multi-precision non-integer? how can there be a fraction in an integer array posing as one big integer?

Hehe - I forgot we we talking about integers (the subject heading implies floating point formats).

Also note that things like "multi-precision" and "arbitrary precision" imply floating point; because for floating point changing the size of the significand changes how precisely numbers can be represented without really effecting the range of numbers that can be represented; and because for variable width integers changing the size of the integer only effects the range of numbers that can be represented without really effecting precision. Note: An arbitrary precision floating point number with a zero width exponent would have a range from -1 to 1 (regardless of significand size), which is entirely different from a variable width integer despite the lack of exponent in both cases.


Cheers,

Brendan