Return to Page

Non-recursive version of pow algorithm Jules 8th August, 2006 08:13 (UTC)

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
Non-recursive version of pow algorithm Kirit Sælensminde 8th August, 2006 08:42 (UTC)
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:

power_recursepower_recurse_quickerpower_forpower_for_quickerpower_builtin
0172ms188ms187ms187ms250ms
1187ms203ms203ms203ms297ms
2344ms500ms219ms235ms265ms
3531ms531ms219ms250ms282ms
4656ms734ms234ms296ms296ms
5781ms750ms266ms297ms282ms
6938ms735ms281ms328ms281ms
71062ms750ms281ms328ms266ms
81219ms953ms281ms360ms296ms
91375ms968ms313ms390ms266ms
101469ms985ms312ms407ms281ms
202968ms1203ms469ms625ms297ms
304437ms1297ms641ms890ms281ms
406047ms1484ms828ms1203ms282ms
507624ms1562ms1109ms1547ms296ms
609266ms1703ms1297ms1844ms282ms
7010874ms1813ms1578ms2218ms281ms
8012530ms1875ms1812ms2531ms297ms
9014203ms1968ms2094ms2906ms312ms
10015733ms1891ms2344ms3266ms281ms

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

To join in the discussion you should register or log in
Non-recursive version of pow algorithm Jim Lebeau 8th August, 2006 16:05 (UTC)

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

Non-recursive version of pow algorithm Jules 8th August, 2006 17:52 (UTC)

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
Non-recursive version of pow algorithm Kirit Sælensminde 9th August, 2006 10:51 (UTC)

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:

power_ recursepower_ recurse_ quickerpower_ forpower_ for_ quickerpower_ for_ quicker_ reworkedpower_ builtin
0297ms281ms266ms265ms281ms407ms
1328ms266ms312ms328ms75293ms406ms
2547ms703ms313ms344ms74497ms437ms
3781ms719ms328ms391ms74605ms453ms
4907ms1062ms359ms406ms73888ms485ms
51265ms1110ms375ms437ms74341ms500ms
61453ms1109ms391ms485ms73653ms562ms
71578ms1140ms422ms500ms72904ms485ms
81719ms1469ms437ms531ms73325ms484ms
91953ms1703ms516ms547ms72419ms453ms
102125ms1563ms515ms594ms81794ms422ms
204343ms2046ms719ms921ms76731ms437ms
306875ms1922ms938ms1266ms80154ms438ms
408843ms1563ms1234ms1703ms76825ms437ms
509265ms1578ms1625ms2312ms73778ms422ms
6013264ms1625ms1906ms2750ms79466ms438ms
7013734ms2406ms1594ms2891ms75950ms437ms
8018686ms2875ms1906ms2656ms78075ms453ms
9017999ms2812ms2390ms3093ms79107ms438ms
10021186ms2750ms3422ms4735ms76840ms500ms

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:

power_ recursepower_ recurse_ quickerpower_ forpower_ for_ quickerpower_ for_ quicker_ reworkedpower_ builtin
0266ms313ms328ms328ms297ms281ms
1281ms312ms328ms422ms578ms281ms
2484ms547ms344ms578ms750ms313ms
3703ms516ms375ms625ms703ms281ms
4907ms765ms375ms766ms859ms297ms
51062ms797ms391ms766ms875ms281ms
61453ms797ms406ms750ms844ms281ms
71656ms781ms406ms749ms875ms297ms
82063ms1031ms422ms844ms984ms281ms
92265ms1047ms453ms969ms1000ms313ms
102281ms1047ms469ms953ms1016ms281ms
204188ms1297ms656ms1156ms1187ms297ms
306296ms1359ms906ms1188ms1219ms281ms
408937ms2313ms1234ms875ms1391ms297ms
5010719ms2515ms1563ms890ms1375ms312ms
6013531ms2391ms1875ms938ms1406ms282ms
7015890ms2749ms2250ms1015ms1656ms328ms
8018140ms2719ms2578ms1000ms1703ms297ms
9016452ms2797ms3047ms1031ms1703ms296ms
10022983ms2750ms3390ms1063ms1688ms297ms
2003437ms6875ms1437ms1906ms313ms
3003844ms10531ms2078ms1656ms297ms
4003578ms11874ms1907ms1375ms328ms
5003703ms16828ms2046ms1437ms312ms
6004015ms20968ms2063ms1516ms297ms
7004406ms26327ms2203ms1594ms328ms
8004297ms29686ms2047ms1499ms438ms
9003250ms34733ms2109ms1750ms531ms
10002875ms39592ms2219ms2469ms594ms
20003156ms2703ms2500ms656ms
30003765ms3156ms2765ms594ms
40005203ms2781ms2891ms562ms
50005297ms2719ms2797ms547ms
60005422ms2046ms2890ms531ms
70005734ms2047ms3047ms500ms
80005375ms2047ms3062ms531ms
90005718ms2062ms3078ms500ms
100005937ms2813ms3157ms500ms

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.


To join in the discussion you should register or log in
Non-recursive version of pow algorithm phil_g 9th August, 2006 14:15 (UTC)
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.

Non-recursive version of pow algorithm Jules 9th August, 2006 20:28 (UTC)

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?

Non-recursive version of pow algorithm Kirit Sælensminde 10th August, 2006 05:23 (UTC)
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.


To join in the discussion you should register or log in
Non-recursive version of pow algorithm ralphmerridew 1st March, 2007 15:18 (UTC)
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
Non-recursive version of pow algorithm Jules 1st March, 2007 19:59 (UTC)

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.

Non-recursive version of pow algorithm Kirit Sælensminde 2nd March, 2007 05:02 (UTC)
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).


To join in the discussion you should register or log in
Non-recursive version of pow algorithm Kirit Sælensminde 24th May, 2007 08:40 (UTC)
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 :(


To join in the discussion you should register or log in
kirit.com