`std.math.powi`: use standard definition of underflow/overflow, implement `u0`, `i0`, `i1` edge case #11499

leesongun · 2022-04-22T17:33:09Z

This PR changes std.math.powi

use standard definition of underflow/overflow, and document it.
implement u0, i0, i1 edge case
better short-circuit
more test cases

details :

I think underflow means 'being to insignificant', rather than 'too close to -Infinity'. (IEEE754 and wikipedia)
1 overflows for u0, i0, i1.
Using @bitSizeOf instead of 8 * @sizeOf.
pow(i32, -2, 31) shouldn't overflow, while pow(i31, -2, 30) and pow(i32, -2, 32) should.

matu3ba

Nice attempt. Math is tricky.

The semantics for underflow are abit brittle, as the return value may be <1 and additionally an overflow exists (which is not intuitive as people also refer to it as "integer underflow").

Aside, a bunch of test cases are missing, 1 optimization could be done and the "reasoning why this math works and correct" would be very nice..

matu3ba · 2022-04-23T17:14:17Z

lib/std/math/powi.zig

    }
+
+    return acc;
 }

 test "math.powi" {


Unfortunately this is missing a bunch of edge cases.
Using pseudo code related to python

0**0 == 1 // u0,i0,u1,i1 1**1 == 1 // same 1**0 == 1 1**y == 1, y any

it is on the first branch, if (x == 1 or y == 0

I dont understand. The special cases u0,u1,i0,i1, which you added in the PR, are not tested.

sorry, i misunderstood your comment.
now i added test cases on u0, i0, i1. u1 is not special cases as it can represent 1.

matu3ba · 2022-04-23T17:15:22Z

lib/std/math/powi.zig

+        if (y > 0) {
+            return 0;
+        } else {
+            // not overflow in strict sense


I dont understand this. Please be more specific.

changed comment to
// Infinity/NaN, not overflow in strict sense

matu3ba · 2022-04-23T17:15:45Z

lib/std/math/powi.zig

-                }
-            }
+    if (x == 0) {
+        if (y > 0) {


It must be y >= 0, as 0^0 == 0.

0^0 is 1. added doc-comment on edge cases.

matu3ba · 2022-04-23T17:23:11Z

lib/std/math/powi.zig

-///  - powi(-1, y)    = 1 for y an even integer
-///  - powi(x, y)     = Overflow for y >= @sizeOf(x) - 1 or y > 0
-///  - powi(x, y)     = Underflow for y > @sizeOf(x) - 1 or y < 0
+///  - powi(x, 0)   = 1 unless T is i1, i0, u0


nit: please use ascending sorting by x, then y.
T is not explained before T is i1, i0, u0. I guess its the type for x, but then I still dont understand what the result semantics are from the text.

It is ordered by precedence, added comment

Are those missing u1?

u1 can represent 1, so no need for special case

matu3ba · 2022-04-23T17:23:36Z

lib/std/math/powi.zig

+///  - powi(x, 0)   = 1 unless T is i1, i0, u0
+///  - powi(0, x)   = 0
+///  - powi(0, x)   = Overflow when x < 0
+///  - powi(1, y)   = 1 unless T is i1, i0, u0


same argument.

matu3ba · 2022-04-23T17:25:17Z

lib/std/math/powi.zig

-    //  powi(x, +-0)   = 1 for any x
-    if (y == 0 or y == -0) {
-        return 1;
+    // integer value 1 cannot be coerced to type 'i1'


I dont see the coercion here. please be more specific. As I understand it, you try to special case any operation on u0,i0,u1,i1.

However, const t1: u1 = 0; const t2: u1 = 0; with 0**0 and y being anything is a valid operation. And same for i1.

i added comment on why naive code won't compile when T is i1

matu3ba · 2022-04-23T17:32:39Z

lib/std/math/powi.zig

+        }
+    }
+    // x >= 2 or x <= -2
+    if (y >= bit_size) {


counterexample: x**1 with x=1 for u1.

powi(u1, 1, 1) is checked at the first branch, if (x == 1

my bad, mark as resolved then.

matu3ba · 2022-04-23T17:35:21Z

lib/std/math/powi.zig

+    if (y >= bit_size) {
+        return error.Overflow;
+    }
+    if (y < 0) {


should be checked first to remove the x==0 and y<0` branch.

0^(-1) should be an overflow, not an underflow?

Julia thinks 0^(-1) is Inf.

which is overflow per the code's definition? I don't see how that would remove branch, as x==0 and y<0 and x !=0 and y<0 (and implictly x != -1 and x !=1, because it is already checked) should give different result (Overflow and Underflow respectively)

correct, my bad then.

matu3ba · 2022-04-23T17:39:50Z

lib/std/math/powi.zig

+    var exp = y;
+    var acc: T = if (does_one_overflow) unreachable else 1;
+
+    while (exp > 1) {


can you write as comment the used approach? ideally with invariant(s) to show why this works?

added one invariant. a direct invariant would require another tracked variable to be concise, so i hope this would be sufficient.

did you forget to push? The rest is looking decent now.

matu3ba · 2022-04-23T17:44:52Z

lib/std/math/powi.zig

-    try testing.expectError(error.Underflow, powi(i64, -2, 64));
-    try testing.expectError(error.Underflow, powi(i17, -2, 17));
-    try testing.expectError(error.Underflow, powi(i42, -2, 42));
+    try testing.expectError(error.Overflow, powi(i8, -2, 8));


-2**8 is in python -256, which clearly is < 1. But this gives Overflow. Probably renaming the error into something different than Underflow would help.

(-2)**8 is 256. also, abs(-256) is 256, which is larger than 1

ups. my bad. mark as resolved then.

andrewrk

Two small fixups requested, other than that, looks ready to merge.

andrewrk · 2022-05-02T21:32:34Z

lib/std/math/powi.zig

+    const bit_size = @bitSizeOf(T);

    comptime assert(@typeInfo(T) == .Int);


Suggested change

const bit_size = @bitSizeOf(T);

comptime assert(@typeInfo(T) == .Int);

const bit_size = @typeInfo(T).Int.bits;

andrewrk · 2022-05-02T21:39:03Z

lib/std/math/powi.zig

-    if (y == 0 or y == -0) {
-        return 1;
+    // `y & 1 == 0` won't compile when `does_one_overflow`.
+    const does_one_overflow = bit_size == 0 or T == i1;


Suggested change

const does_one_overflow = bit_size == 0 or T == i1;

const does_one_overflow = math.maxInt(T) < 1;

…ment `u0`, `i0`, `i1` edge case (#11499)

leesongun added 10 commits April 23, 2022 02:24

merge 0 and -0

a649e32

conform to usual definition of overflow/underflow

6651f34

handle -2 further

2834ce5

fix test cases

133d37e

implement u0, i0, i1 special case; document errors

3f494ae

fix i1 handling

80570ad

remove rarely triggered short-circuit

dd61a8b

move test cases to align with test name

c9afd1b

add underflow test cases

5ce215a

align special cases comment with actual behavior

51e301f

matu3ba suggested changes Apr 23, 2022

View reviewed changes

leesongun added 8 commits April 24, 2022 03:27

document edge case ordering

db8c214

update comment to be more specific

1fd9012

add T to every edge case doc-comment

42862be

document invariant

e82e023

reword priority to precedence

54c76ba

test u0, i0, i1 cases

d21a7b5

remove unnecessary edge case

d0dc637

separate test case

3fb1f58

andrewrk requested changes May 2, 2022

View reviewed changes

implement suggested fixes

c2c40b0

andrewrk merged commit 1de7b8d into ziglang:master May 16, 2022

andrewrk pushed a commit that referenced this pull request Jul 19, 2022

std.math.powi: use standard definition of underflow/overflow, imple…

d642f6e

…ment `u0`, `i0`, `i1` edge case (#11499)

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

`std.math.powi`: use standard definition of underflow/overflow, implement `u0`, `i0`, `i1` edge case #11499

`std.math.powi`: use standard definition of underflow/overflow, implement `u0`, `i0`, `i1` edge case #11499

leesongun commented Apr 22, 2022 •

edited

matu3ba left a comment

matu3ba Apr 23, 2022

leesongun Apr 23, 2022

matu3ba Apr 23, 2022

leesongun Apr 23, 2022

matu3ba Apr 23, 2022

leesongun Apr 23, 2022

matu3ba Apr 23, 2022

leesongun Apr 23, 2022 •

edited

matu3ba Apr 23, 2022

leesongun Apr 23, 2022 •

edited

matu3ba Apr 23, 2022

leesongun Apr 23, 2022

matu3ba Apr 23, 2022

matu3ba Apr 23, 2022

leesongun Apr 23, 2022 •

edited

matu3ba Apr 23, 2022

leesongun Apr 23, 2022

matu3ba Apr 23, 2022

matu3ba Apr 23, 2022

leesongun Apr 23, 2022

matu3ba Apr 23, 2022

leesongun Apr 23, 2022

matu3ba Apr 23, 2022

matu3ba Apr 23, 2022

leesongun Apr 23, 2022

matu3ba Apr 23, 2022

matu3ba Apr 23, 2022 •

edited

leesongun Apr 23, 2022 •

edited

matu3ba Apr 23, 2022

andrewrk left a comment

andrewrk May 2, 2022

andrewrk May 2, 2022

		const bit_size = @bitSizeOf(T);

		comptime assert(@typeInfo(T) == .Int);

	const does_one_overflow = bit_size == 0 or T == i1;
	const does_one_overflow = math.maxInt(T) < 1;

std.math.powi: use standard definition of underflow/overflow, implement u0, i0, i1 edge case #11499

std.math.powi: use standard definition of underflow/overflow, implement u0, i0, i1 edge case #11499

Conversation

leesongun commented Apr 22, 2022 • edited

matu3ba left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

leesongun Apr 23, 2022 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

leesongun Apr 23, 2022 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

leesongun Apr 23, 2022 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

matu3ba Apr 23, 2022 • edited

Choose a reason for hiding this comment

leesongun Apr 23, 2022 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

andrewrk left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

`std.math.powi`: use standard definition of underflow/overflow, implement `u0`, `i0`, `i1` edge case #11499

`std.math.powi`: use standard definition of underflow/overflow, implement `u0`, `i0`, `i1` edge case #11499

leesongun commented Apr 22, 2022 •

edited

leesongun Apr 23, 2022 •

edited

leesongun Apr 23, 2022 •

edited

leesongun Apr 23, 2022 •

edited

matu3ba Apr 23, 2022 •

edited

leesongun Apr 23, 2022 •

edited