Non-recursive version of pow algorithm

You *can* write a version which doesn't require extra storage (storage = O(1)):

function pow(b, n){
  a = 1;
  while(n != 0){
	if(n & 1 == 0){
	  b = b * b;
	  n = n / 2;
	}else{
	  a = a * b;
	  n = n - 1;
	}
  }
  return a;
}

Sorry for bad markup…

Edited to improve layout — Kirit

Jules said

You *can* write a version which doesn't require extra storage (storage = O(1)):

function pow(b, n){
  a = 1;
  while(n != 0){
	if(n & 1 == 0){
	  b = b * b;
	  n = n / 2;
	}else{
	  a = a * b;
	  n = n - 1;
	}
  }
  return a;
}

Sorry for bad markup…

Edited to improve layout — Kirit

That's a brilliant solution!

I've had a quick go of it in with the others. I'm not 100% convinced that it is doing exactly the same algorithm yet. I'll have to look at it closer. First off though I've re-named the variables to make it fit in with my versions. I don't think I broke it as it gives the same results as my versions. Here is what I tested:

function power_for_quicker( value, power ) {
	var result = 1;
	while ( power != 0 ) {
		if ( power & 1 == 0 ) {
			value = value * value;
			power = power / 2;
		} else {
			result = result * value;
			power = power - 1;
		}
	}
	return result;
}

Here is a table comparing it to the others for the first one hundred powers:

As you can see it competes very well, but then goes very slow for higher n. I don't know if this is due to some Javascript weirdness or because it is doing something different. I'll have to analyse it more fully.

K

This nonrecursive one 'loops' more than the 'quicker recursive' version. The recursve version does power = ( power - 1 ) / 2 and the related math in one pass, the nonrecursive uses two.

Jules said

You *can* write a version which doesn't require extra storage (storage = O(1)):

The fast recursive version is incorrect. You should swap the then and the else part ;-).

I converted the fast recursive algorithm to a while loop:

This is the original function (cleaned up a little):

function pow1(b, n){
 if(n == 0)
   return 1
 else{
   if(n & 1) == 0
     return pow2(b**2, n / 2)
   else
     return b * pow2(b**2, n / 2)
 }
}

Now the recursive call is in tail position by adding a variable to collect the multiplications (b * pow2(b**2, n / 2)):

function pow2(b, n, m = 1){
 if n == 0
   return m
 else{
   if n & 1 == 0
     return pow2(b**2, n / 2, m)
   else
     return pow2(b**2, n / 2, b * m)
 }
}

Convert to while loop:

def pow3(b, n){
 m = 1
 while(n != 0){
   if n & 1 != 0
     m = b * m
   b = b**2
   n = n / 2  
 }
 return m
}

I haven't tested this so it could be wrong, but I think the idea/method is correct.

Edited the function presentation so they're all in pre tags — Kirit

I've put pow3 in to the harness and had a go with that. I changed a few things, name, def to function and what I presume is a power operator where you had:

b = b**2

I presume that this means:

b = b * b;

And not:

b = b * 2;

In any case the first produces the correct answer and the second the wrong answer. I ended up with this version:

function power_for_quicker_corrected( b, n ) {
	var m = 1;
	while( n != 0 ) {
		if ( ( n & 1 ) != 0 )
			m = b * m;
		b = b * b;
		n = n / 2;
	}
	return m;
}

You've clearly got a different language in mind when you go through this. Just out of curiosity which is it?

This version though has something seriously up with it. Take a look at the timings below:

I can't see why the times should be quite as bad as this. It simply doesn't make any sense at all. There are a couple of things to note:

1. The division by 2 is going to produce fractional results. Changing these lines to use Math.floor() gives incorrect results.
2. I'm not sure how the bitwase and operator works on fractions. I presume that this is meant to detect even/odd values which means it should be equivalent to the modulus operator, but they return different results.

I expect that these two are working together in some way. The bitwise and somehow causing the extra loops to cancel out. Replacing both of these constructs to give these version of your algorithms gives substantialy different results.

function power_for_quicker( value, power ) {
	var result = 1;
	while ( power != 0 ) {
		if ( power % 2 == 0 ) {
			value = value * value;
			power = Math.floor( power / 2 );
		} else {
			result = result * value;
			power = power - 1;
		}
	}
	return result;
}

function power_for_quicker_reworked( value, power ) {
	var m = 1;
	while ( power != 0 ) {
		if ( power % 2 )
			m *= value;
		value *= value;
		power = Math.floor( power / 2 );
	}
	return m;
}

And the timings are now more like this:

I guess that there is an important lesson here about knowing the types that weakly typed languages return from expressions.

Anyway, I promised a prize for working out a correct version with constant memory overhead. I'll contact you by email about that though.

Kirit Sælensminde said

function power_for_quicker_corrected( b, n ) {
	var m = 1;
	while( n != 0 ) {
		if ( ( n & 1 ) != 0 )
			m = b * m;
		b = b * b;
		n = n / 2;
	}
	return m;
}

This is basically the way I've implemented this algorithm in the past. (Mine was actually tail-recursive but it works out to the same thing. I'd post my code, but it's in Common Lisp, not javascript.)

1. The division by 2 is going to produce fractional results. Changing these lines to use <code>Math.floor()</code> gives incorrect results.

In my version, I used bit shifting to divide by two. It has the advantages of being fast and of always returning an integer.

The language I used doesn't exist. My Javascript-fu is in bad condition ;-).

I assumed that n / 2 is integer division. So if n = 5: 5 / 2 = 2. This is the same as using Math.floor.

n & 1 is faster than n % 2. It works because if you bitwise and an integer with 1 you'll get 1 if the number is odd and 0 if the number is even.

After thinking about it I concluded that the function I wrote doesn't use the same algorithm.

Your algoritm is based on this:

a^b = (a^(b/2))^2

the one I wrote is based on this:

a^b = (a^2)^(b/2)

I think the algorithms perform the same number of steps, but your version squares the result of the pow function: pow(value, power / 2)**2, but mine does this: pow(value**2, power / 2). Your algorithm is better because there are more multiplications with small numbers and less multiplications with large numbers.

Is this correct?

Jules said

The language I used doesn't exist. My Javascript-fu is in bad condition ;-).

I assumed that n / 2 is integer division. So if n = 5: 5 / 2 = 2. This is the same as using Math.floor.

I think somebody else (on Reddit) suggested using the bitshift operator. I must admit that never occured to me in Javascript.

n & 1 is faster than n % 2. It works because if you bitwise and an integer with 1 you'll get 1 if the number is odd and 0 if the number is even.

Yup. And they're provably equavalent — and give different answers. So much for that. I guess the modulus on a float is fine, but the bitwise and isn't. I wonder what the Javascript interpreter was doing with. And it was strange that the bugs together cancel out so neatly.

After thinking about it I concluded that the function I wrote doesn't use the same algorithm.

Your algoritm is based on this:

a^b = (a^(b/2))^2

the one I wrote is based on this:

a^b = (a^2)^(b/2)

I think the algorithms perform the same number of steps, but your version squares the result of the pow function: pow(value, power / 2)**2, but mine does this: pow(value**2, power / 2). Your algorithm is better because there are more multiplications with small numbers and less multiplications with large numbers.

Is this correct?

I'm not sure. I'd have to work it out and right now I need to be getting on with some other, less interesting, things. I'm planning an article on the uses (and abuses) of order calculations for measuring complexity and I'll include these in there.

Jules said

You *can* write a version which doesn't require extra storage (storage = O(1)):

function pow(b, n){
   a = 1;
   while(n != 0){
 	if(n & 1 == 0){
 	  b = b * b;
 	  n = n / 2;
 	}else{
 	  a = a * b;
 	  n = n - 1;
 	}
   }
   return a;
 }

Sorry for bad markup…

Edited to improve layout — Kirit

Question: Is this using integer or floating point math by default? (If the former, then the extra variable does not require O(1) storage, and the functions shouldn't be compared with builtin_pow.)

Edited to improve layout — Kirit

Question: Is this using integer or floating point math by default? (If the former, then the extra variable does not require O(1) storage, and the functions shouldn't be compared with builtin_pow.)

It doesn't require O(1) storage because the numbers are too big? Then every pow(b,n) requires at least

log2 b^n — the number of bits in b^n, the result of pow(b,n) log2 b^n = n * log2 b =~ n

storage to store the result, so it's at least O(n).

I think it uses floating point once the numbers are too big for machine ints (but as I said: my JavaScript knowledge is small). You can test this by trying pow(2, 1024), which should be too big for IEEE floating point (max value is pow(2,1023)). If JavaScript says “infinity” it's using floating point, and if JavaScript says 1.8*10^308 it's using bignums (variable length integers).

Here's one using bit shifts (untested of course ;-)).

function pow(b,n){
    var m = 1
    while(n){
        if(n&1) m *= b
        b *= b
        n >>= 1
    }
    return m
}

(yay I mastered the markup…)

I don't know if bit shifts are faster than division using floating point in JS, and I don't know if n&1 is faster than n%2 (both should be faster, but high level languages can be weird). So you may be able to speed this up by using /= 2 instead of >>= 1 and n%2 instead of n&1.

ralphmerridew said

Question: Is this using integer or floating point math by default? (If the former, then the extra variable does not require O(1) storage, and the functions shouldn't be compared with builtin_pow.)

I think Javascript uses some sort of type promotion for handling the values. I'm pretty certain that it does not have any big number support as (assuming that'd be slower than floats) it would show up in the timings. This of course means that the functions as tested are useless for giving actual results as nearly all of the answers will be infinity. The timing seems to show that multiplying infinity by anything takes about the same amount of time as multiplying two numbers together.

I think we can probably rule out Javascript using 32 bit floats, but I don't know whether it uses 64 or 80 bit ones. As for the type promotion I would expect that it would go something like this:

4 / 2 = 2 (int)
2 / 2 = 1 (int)
1 / 2 = 0.5 (float)

There should be a similar change as the numbers go above whatever maximum the integer type can store (almost certainly 32 bit).

ralphmerridew said

Question: Is this using integer or floating point math by default? (If the former, then the extra variable does not require O(1) storage, and the functions shouldn't be compared with builtin_pow.)

My previous answer was completely wrong. Turns out that JavaScript uses 64 bit floating numbers and converts to 32 bit integers when doing bit operations (source The Complete Javascript Number Reference).

I now no longer know if that solves your riddle or not :(