Add binary-op pow #79

MirkoDziadzka · 2017-01-09T17:58:40Z

added an implementation of the pow operator (**) for python. This should fix #36

Fixed the implemenation for int, trying a fast path first and then fall back to Long. Adding implementation for Long and Float

ns-cweber · 2017-01-09T18:52:33Z

runtime/float.go

 }

+func floatPow(f *Frame, v, w *Object) (*Object, *BaseException) {
+	return floatArithmeticOp(f, "__pow__", v, w, func(v, w float64) float64 { return math.Pow(v, w) })


math.Pow() already takes 2 floats and returns another, so I think this could be reduced:

func floatPow(f *Frame, v, w *Object) (*Object, *BaseException) { return floatArithmeticOp(f, "__pow__", v, w, math.Pow) }

Same goes for RPow below.

RPow below can not changed this way, because the order of the arguments is reversed.

ns-cweber · 2017-01-09T18:57:57Z

testing/pow_test.py

@@ -0,0 +1,4 @@
+


Add the file header:

// Copyright 2016 Google Inc. All Rights Reserved. // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // http://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License.

Minor nit, but I don't think we need to create a whole new file for just this one pow test. Put it in testing/op_test.py, maybe?

ns-cweber · 2017-01-09T18:58:34Z

This looks great! Just a couple comments. 👍

trotterdylan · 2017-01-10T00:28:54Z

compiler/expr_visitor_test.py

  testBinOpArithmeticMod = _MakeExprTest('9 % 5')
  testBinOpArithmeticMul = _MakeExprTest('3 * 2')
  testBinOpArithmeticOr = _MakeExprTest('2 | 6')
+  testBinOpArithmeticPow = _MakeExprTest('2 ** 16')


A couple more test cases would be good here, e.g. negative numbers, floats, etc.

This is the parser part. Does this really need more test?

You're right, this is consistent with what's there. It's fine to leave it the way it is.

trotterdylan · 2017-01-10T00:29:21Z

runtime/core_test.go

 		{Mul, newObject(ObjectType), newObject(fooType), nil, mustCreateException(TypeErrorType, "unsupported operand type(s) for *: 'object' and 'Foo'")},
 		{Or, NewInt(-42).ToObject(), NewInt(244).ToObject(), NewInt(-10).ToObject(), nil},
 		{Or, NewInt(42).ToObject(), NewStr("foo").ToObject(), nil, mustCreateException(TypeErrorType, "unsupported operand type(s) for |: 'int' and 'str'")},
+		{Pow, NewInt(2).ToObject(), NewInt(16).ToObject(), NewInt(65536).ToObject(), nil},


Again, a few more test cases would be nice.

trotterdylan · 2017-01-10T00:30:25Z

runtime/float_test.go

 		{Mul, NewFloat(math.Inf(1)).ToObject(), NewInt(-5).ToObject(), NewFloat(math.Inf(-1)).ToObject(), nil},
 		{Mul, False.ToObject(), NewFloat(math.Inf(1)).ToObject(), NewFloat(math.NaN()).ToObject(), nil},
 		{Mul, None, NewFloat(1.5).ToObject(), nil, mustCreateException(TypeErrorType, "unsupported operand type(s) for *: 'NoneType' and 'float'")},
+		{Pow, NewFloat(2.0).ToObject(), NewInt(10).ToObject(), NewFloat(1024.0).ToObject(), nil},


The "unsupported operand type" case would be good here.

trotterdylan · 2017-01-10T00:32:01Z

runtime/int.go

 }

+func intCheckedPow(v, w int) (int, bool) {
+	// first try the shortcut - assuming the this operation is


Is this a reasonable assumption? I have no familiarity with the relative speed of float pow vs. a multiplication loop.

Also, please make comments full sentences (capitalize and period at the end.)

On my system measuring a simple math.Exp vs. big.NewInt(0).Pow gives 4µs vs. 16µs. I have not yet tested the full code with all the surrounding functions.

That's good enough for me. We can always tweak it later.

One other thing: doesn't it seem like on 64 bit systems there will be large integers that cannot be represented exactly by a float64 and therefore this won't work for some set of numbers?

Yes. And the implementation of python x ** y differs a lot from Go big.Exp and math.Pow when x or y are negative.

A complete implementation will need some more time ...

Strictly looking at math.Pow vs. float ** float, it seems like Go and Python are very similar:

Expression Restriction Go Python Pow(x, ±0.0) 1.0 1.0 Pow(1.0, y) 1.0 1.0 Pow(x, 1.0) x x Pow(NaN, y) NaN NaN Pow(x, NaN) NaN NaN Pow(±0.0, y) y an odd integer < 0 ±Inf ZeroDivisionError Pow(±0.0, y) finite y < 0 and not an odd integer +Inf ZeroDivisionError Pow(±0.0, y) y an odd integer > 0 ±0.0 ±0.0 Pow(±0.0, y) finite y > 0 and not an odd integer +0.0 +0.0 Pow(±0.0, -Inf) +Inf +Inf Pow(±0.0, +Inf) +0.0 +0.0 Pow(-1.0, ±Inf) 1.0 1.0 Pow(x, +Inf) |x| > 1 +Inf +Inf Pow(x, -Inf) |x| > 1 +0.0 +0.0 Pow(x, +Inf) |x| < 1 +0.0 +0.0 Pow(x, -Inf) |x| < 1 +Inf +Inf Pow(+Inf, y) y > 0 +Inf +Inf Pow(+Inf, y) y < 0 +0.0 +0.0 Pow(-Inf, y) y an odd integer < 0 -0.0 -0.0 Pow(-Inf, y) finite y < 0 and not an odd integer +0.0 +0.0 Pow(-Inf, y) y an odd integer > 0 -Inf -Inf Pow(-Inf, y) finite y > 0 and not an odd integer Inf Inf Pow(x, y) finite x < 0 and finite non-integer y NaN ValueError

trotterdylan · 2017-01-10T00:37:36Z

Thanks a lot for the PR! This looks very complete. Thanks for taking the time to dig into it. I have just a few comments.

Added some more test.

trotterdylan

Thanks for doing this! The implementation is shaping up really well. I have a few more comments and suggestions.

trotterdylan · 2017-01-17T05:00:18Z

compiler/expr_visitor_test.py

  testBinOpArithmeticMod = _MakeExprTest('9 % 5')
  testBinOpArithmeticMul = _MakeExprTest('3 * 2')
  testBinOpArithmeticOr = _MakeExprTest('2 | 6')
+  testBinOpArithmeticPow = _MakeExprTest('2 ** 16')


You're right, this is consistent with what's there. It's fine to leave it the way it is.

trotterdylan · 2017-01-17T05:02:30Z

runtime/int.go

+		// IEEE float64 has 52bit of precision, so the result should be
+		// less than MaxInt32 to be representable as an exact integer.
+		// This assumes that int is at least 32bit.
+		v_int := toIntUnsafe(v).Value()


use camelCase for vars: vInt, wInt

trotterdylan · 2017-01-17T05:03:06Z

runtime/int.go

+		w_int := toIntUnsafe(w).Value()
+		if 0 < v_int && v_int <= math.MaxInt32 && 0 < w_int && w_int <= math.MaxInt32 {
+			res := math.Pow(float64(v_int), float64(w_int))
+			// can the result be interpreted as an int?


Capitalize comments please

trotterdylan · 2017-01-17T05:04:35Z

runtime/int.go

+		if v_int == 0 {
+			if w_int < 0 {
+				return nil, f.RaiseType(ZeroDivisionErrorType, "0.0 cannot be raised to a negative power")
+			} else if w_int == 0 {


Omit else when it doesn't change the semantics:

if wInt < 0 { return nil, f.RaiseType(...) } if wInt == 0 { return ... } return ...

trotterdylan · 2017-01-17T05:14:25Z

runtime/long.go

 	LongType.slots.New = &newSlot{longNew}
 	LongType.slots.NonZero = longUnaryBoolOpSlot(longNonZero)
 	LongType.slots.Or = longBinaryOpSlot(longOr)
+	LongType.slots.Pow = &binaryOpSlot{longPow}


Is there a reason not to use longBinaryOpSlot() here? It's a well established pattern here and it takes care of a little bit of the type coercion for you.

longBinaryOpSlot expect a function which always return a Long. But in **, when the exponent is negative, we have to return a Float. So this function can not be used (or I'm missing something here).

I see. No I don't think you're missing anything. It's probably worth adding a comment about why we don't use longBinaryOpSlot for this method.

trotterdylan · 2017-01-17T05:24:35Z

runtime/long.go

+}
+
+func longRPow(f *Frame, v, w *Object) (*Object, *BaseException) {
+	return longPow(f, w, v)


w may not be a long which would cause an invalid unsafe cast on line 495. Incidentally, I think using longRBinaryOpSlot for the RPow slot will allow you to use a single longPow and handle swapping the operands for you.

Thanks for spotting the error. I will add a test for this and a fix.

trotterdylan · 2017-01-17T05:25:15Z

testing/pow_test.py

+assert large_number ** -1 == (1.0  / large_number), "large_number ** -1 == (1.0  / large_number)"
+assert large_number ** 0 == 1, "large_number ** 0 == 1"
+assert large_number ** 1 == large_number, "large_number ** 1 == large_number"
+


Remove excess trailing newlines (one is OK).

trotterdylan · 2017-01-17T05:26:00Z

testing/pow_test.py

+assert 2 ** -1 == 0.5, "2 ** -1"
+assert 2 ** 0 == 1, "2 ** 0"
+assert 2 ** 1 == 2, "2 ** 1"
+assert 2 ** 2 == 4, "2 ** 2"


Good to have some explicit long tests here, e.g. assert 2L ** 2 == 4, "2L ** 2"

trotterdylan · 2017-01-17T05:26:52Z

runtime/int_test.go

 		{Or, NewInt(-100).ToObject(), NewInt(50).ToObject(), NewInt(-66).ToObject(), nil},
 		{Or, NewInt(MaxInt).ToObject(), NewInt(MinInt).ToObject(), NewInt(-1).ToObject(), nil},
 		{Or, newObject(ObjectType), NewInt(-100).ToObject(), nil, mustCreateException(TypeErrorType, "unsupported operand type(s) for |: 'object' and 'int'")},
+		{Pow, NewInt(2).ToObject(), NewInt(128).ToObject(), NewLong(big.NewInt(0).Exp(big.NewInt(2), big.NewInt(128), nil)).ToObject(), nil},


A couple more test cases (e.g. TypeError case) wouldn't go amiss.

trotterdylan · 2017-01-17T05:27:13Z

runtime/long_test.go

 		{Or, -100, 50, NewLong(big.NewInt(-66)).ToObject(), nil},
 		{Or, MaxInt, MinInt, NewLong(big.NewInt(-1)).ToObject(), nil},
 		{Or, newObject(ObjectType), 100, nil, mustCreateException(TypeErrorType, "unsupported operand type(s) for |: 'object' and 'long'")},
+		{Pow, 2, 128, NewLong(big.NewInt(0).Exp(big.NewInt(2), big.NewInt(128), nil)).ToObject(), nil},


A couple more test cases would be good

- use camelCase for local variables - fix a problem in 1 ** 1L (and add a test) - add more test

trotterdylan · 2017-01-17T19:03:14Z

Is this code ready for another round of reviews then?

MirkoDziadzka · 2017-01-17T23:24:20Z

Yes, please review.

trotterdylan

This is great! Thanks for working on this. Merging shortly.

MirkoDziadzka added 2 commits January 5, 2017 14:23

add simple Pow implementation for int

9ad4a5a

A more complete implementation of Pow

4f3cdb7

Fixed the implemenation for int, trying a fast path first and then fall back to Long. Adding implementation for Long and Float

ns-cweber reviewed Jan 9, 2017

View reviewed changes

trotterdylan suggested changes Jan 10, 2017

View reviewed changes

MirkoDziadzka added 5 commits January 16, 2017 22:06

Improve the integer ** op.

7fc970a

Added some more test.

fix the Pow operation for long integer

9081d92

Improve test code

d10889b

add type error tests for pow / float

4ddaa4a

add copyright, document and improve test

c4f6976

trotterdylan suggested changes Jan 17, 2017

View reviewed changes

MirkoDziadzka added 2 commits January 17, 2017 18:45

fix code review issues

d8091a9

- use camelCase for local variables - fix a problem in 1 ** 1L (and add a test) - add more test

gofmt fixes

50fbe2e

trotterdylan approved these changes Jan 18, 2017

View reviewed changes

trotterdylan merged commit 3dc695e into google:master Jan 18, 2017

MirkoDziadzka deleted the add-binaryop-pow branch January 18, 2017 09:17

Add binary-op pow #79

Add binary-op pow #79

Uh oh!

Conversation

MirkoDziadzka commented Jan 9, 2017

Uh oh!

ns-cweber Jan 9, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ns-cweber commented Jan 9, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

trotterdylan commented Jan 10, 2017

Uh oh!

trotterdylan left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

trotterdylan commented Jan 17, 2017

Uh oh!

MirkoDziadzka commented Jan 17, 2017

Uh oh!

trotterdylan left a comment

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

ns-cweber Jan 9, 2017 •

edited

Loading