## digitalmars.D - Re: Semantics of ^^

- bearophile <bearophileHUGS lycos.com> Dec 08 2009
- Don <nospam nospam.com> Dec 08 2009
- bearophile <bearophileHUGS lycos.com> Dec 08 2009
- BCS <none anon.com> Dec 08 2009
- KennyTM~ <kennytm gmail.com> Dec 08 2009

Don:Based on everyone's comments, this is what I have come up with:

Looks good.* If y == 0, x ^^ y is 1. * If both x and y are integers, and y > 0, x^^y is equivalent to { auto u = x; foreach(i; 1..y) { u *= x; } return u; }

You can rewrite both of those as: { typeof(x) u = 1; foreach (i; 0 .. y) { u *= x; } return u; }(1) Although the following special cases could be defined... * If x == 1, x ^^ y is 1 * If x == -1 and y is even, x^^y == 1 * If x == -1 and y is odd, x^^y == -1 ... they are not sufficiently useful to justify the major increase in complexity which they introduce.

This is not essential: (-1)**n is a common enough shortcut to produce an alternating +1 -1, you can see it used often enough in Python code (and in mathematics). This search gives 433 results: http://www.google.com/codesearch?q=\%28-1\%29\s*\*\*\s*[0-9a-zA-Z%28]+lang%3Apython When used for this purpose (-1) is always compile time constant, so the compiler can grow a simple rule the rewrites: (-1) ^^ n as (n & 1) ? -1 : 1 Bye, bearophile

Dec 08 2009

bearophile wrote:Don:Based on everyone's comments, this is what I have come up with:

Looks good.* If y == 0, x ^^ y is 1. * If both x and y are integers, and y > 0, x^^y is equivalent to { auto u = x; foreach(i; 1..y) { u *= x; } return u; }

You can rewrite both of those as: { typeof(x) u = 1; foreach (i; 0 .. y) { u *= x; } return u; }(1) Although the following special cases could be defined... * If x == 1, x ^^ y is 1 * If x == -1 and y is even, x^^y == 1 * If x == -1 and y is odd, x^^y == -1 ... they are not sufficiently useful to justify the major increase in complexity which they introduce.

This is not essential: (-1)**n is a common enough shortcut to produce an alternating +1 -1, you can see it used often enough in Python code (and in mathematics). This search gives 433 results: http://www.google.com/codesearch?q=\%28-1\%29\s*\*\*\s*[0-9a-zA-Z%28]+lang%3Apython When used for this purpose (-1) is always compile time constant, so the compiler can grow a simple rule the rewrites: (-1) ^^ n as (n & 1) ? -1 : 1

That's an interesting one. With this proposal, that optimisation could still be made when it is known that n>=0. We *could* make a special rule for compile-time constant -1 ^^ n, to allow the optimisation even when n<0. But then you have to explain why: x = -1; y = x^^-2; is illegal, but y = -1^^-2 is legal. Can that be justified?

Dec 08 2009

Don:But then you have to explain why: x = -1; y = x^^-2; is illegal, but y = -1^^-2 is legal. Can that be justified?

Probably not :-) Bye, bearophile

Dec 08 2009

Hello Don,bearophile wrote:Don:Based on everyone's comments, this is what I have come up with:

* If y == 0, x ^^ y is 1. * If both x and y are integers, and y > 0, x^^y is equivalent to { auto u = x; foreach(i; 1..y) { u *= x; } return u; }

{ typeof(x) u = 1; foreach (i; 0 .. y) { u *= x; } return u; }(1) Although the following special cases could be defined... * If x == 1, x ^^ y is 1 * If x == -1 and y is even, x^^y == 1 * If x == -1 and y is odd, x^^y == -1 ... they are not sufficiently useful to justify the major increase in complexity which they introduce.

(-1)**n is a common enough shortcut to produce an alternating +1 -1, you can see it used often enough in Python code (and in mathematics). This search gives 433 results: http://www.google.com/codesearch?q=\%28-1\%29\s*\*\*\s*[0-9a-zA-Z%28] +lang%3Apython When used for this purpose (-1) is always compile time constant, so the compiler can grow a simple rule the rewrites: (-1) ^^ n as (n & 1) ? -1 : 1

With this proposal, that optimisation could still be made when it is known that n>=0. We *could* make a special rule for compile-time constant -1 ^^ n, to allow the optimisation even when n<0. But then you have to explain why: x = -1; y = x^^-2; is illegal, but y = -1^^-2 is legal. Can that be justified?

Maybe. I think it's worth looking into.

Dec 08 2009

On Dec 8, 09 19:16, bearophile wrote:Don:Based on everyone's comments, this is what I have come up with:

Looks good.* If y == 0, x ^^ y is 1. * If both x and y are integers, and y> 0, x^^y is equivalent to { auto u = x; foreach(i; 1..y) { u *= x; } return u; }

You can rewrite both of those as: { typeof(x) u = 1; foreach (i; 0 .. y) { u *= x; } return u; }

This is not essential: (-1)**n is a common enough shortcut to produce an alternating +1 -1, you can see it used often enough in Python code (and in mathematics). This search gives 433 results: http://www.google.com/codesearch?q=\%28-1\%29\s*\*\*\s*[0-9a-zA-Z%28]+lang%3Apython When used for this purpose (-1) is always compile time constant, so the compiler can grow a simple rule the rewrites: (-1) ^^ n as (n& 1) ? -1 : 1 Bye, bearophile

Other non-essential special cases are 2^^n == 1<<n and x^^2 == x*x, but these should be put in the optimizer, not the language. (And an integer power algorithm http://www.c2.com/cgi/wiki?IntegerPowerAlgorithm should be used instead of a simple foreach loop implementation-wise.)

Dec 08 2009