• 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

bearophile <bearophileHUGS lycos.com> writes:

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

Don <nospam nospam.com> writes:

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?

bearophile <bearophileHUGS lycos.com> writes:

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

BCS <none anon.com> writes:

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.

KennyTM~ <kennytm gmail.com> writes:

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; }


 (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


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