Make Int::pow() take exp as u32 instead usize #22087

GuillaumeGomez · 2015-02-08T13:22:28Z

Fixes issue #22016

rust-highfive · 2015-02-08T13:22:41Z

(rust_highfive has picked a reviewer for you, use r? to override)

dotdash · 2015-02-08T17:59:34Z

It would be great if the commit subject mentioned what's being done here, for example:

Make Int::pow() take exp as Self instead usize

And then just put the "Fixes #22016" in the commit message body.

GuillaumeGomez · 2015-02-08T18:01:44Z

My bad, I change that !

dotdash · 2015-02-08T18:07:08Z

It should be possible keep the implementation as a default method if you switch from 0 to Int::zero() and 1 to Int::one() and exp /= 2 to exp = exp >> 1.

But one might argue that using >> there obscures things too much. Let's wait what others say about it.

GuillaumeGomez · 2015-02-08T18:11:06Z

As long as it's not merged, I can modify. However, yes, I think that the "clear" code is better in this case. It makes the reading easier (even if that's not a big problem in this case). Whatever, let's wait others' opinion.

pczarn · 2015-02-09T09:58:23Z

Consider negative exponents. With this PR, 123.pow(-x) == 1.

I think you can write exp = exp / (one + one). But >> is fine too, as long as exp is not negative.

GuillaumeGomez · 2015-02-09T10:00:04Z

@pczarn: I was actually wondering if the negative powers should be handled...

pczarn · 2015-02-09T10:20:06Z

In my opinion

return 1 if base = 1
return 0 if base > 1 and exp < 0
panic!("attempted to divide by zero") if base = 0 and exp < 0

Add tests to libcoretest if you choose to add these conditions.

GuillaumeGomez · 2015-02-09T10:26:39Z

I'll wait other opinions before doing anything but that seems a good idea.

alexcrichton · 2015-02-09T18:55:07Z

It's a bit of an open question as to what the best option for an argument here is. Strictly speaking I'm not sure that we need a range outside of u8, but that seems like an odd argument to take. I do agree that usize probably isn't appropriate here, but requiring an unsigned exponent sounds like it would be a good idea (to handle what @pczarn mentioned). This may want to wait for the integer conventions to shake out (note that this is why the API is #[unstable]).

GuillaumeGomez · 2015-02-10T19:24:50Z

I added the changes proposed by @pczarn and tests. Now waiting for something definitive.

Diggsey · 2015-02-11T00:15:09Z

Using "Self" is wrong, because exponentiation is fundamentally different from addition/multiplication (think about units, you can't have 1m ^ 1m, it just doesn't make sense).

You can use any non-negative integer as the exponent without necessarily overflowing even the smallest type (1^n == 1). You might think that's not particularly useful if the only valid base is either "1" or "0", but it means you don't have to handle that case specially.

Similarly the type of the exponent doesn't affect the return type (u8 ^ u64 == u8) so you don't suffer from larger integer types "leaking" into the rest of the program, as you would do if you applied this logic to the other integer operations.

You may as well use the largest integer type which won't harm performance (ie. either usize or u64).

Another way of looking at it, is by considering it as repeated multiplication:

let mut result = 1
for i in 0..n
    result *= base

There's absolutely no reason why the type of "n" should relate to the type of "base". It's limit is only related to the maximum number of times a loop can be expected to iterate (for which one would normally use the largest built-in integer type).

(somewhat related: C is going to be using intmax_t for its pown function, which performs integer exponentiation on floats: http://stackoverflow.com/a/23872884)

GuillaumeGomez · 2015-02-11T08:28:56Z

I think the proposition of @alexcrichton is actually the best one. Limit the pow to u8 would be more than enough. But it's nice to create a little debate sometimes !

alexcrichton · 2015-02-11T17:08:04Z

@GuillaumeGomez oh to be clear I was not advocating for u8, only mentioning that there are no real limits here (the smallest unsigned type works for us). I would personally advocate for u32 here.

GuillaumeGomez · 2015-02-12T16:03:55Z

The big question which remains is: do we pass Self as exp or not ?

brson · 2015-02-18T23:20:44Z

On IRC I chimed in to suggest this should be u32, along with the other shifting and counting methods on Int.

Also that overflow doesn't appear to be handled #22506.

GuillaumeGomez · 2015-02-18T23:22:12Z

That's what @alexcrichton came along with too. So I think I'll do it with u32. Now, it remains the following question: panic or not when overflow ?

Gankra · 2015-02-19T05:00:19Z

It makes sense to me to have whatever panic semantics integer overflow has for any other arithmetic operation. This may involve cfgs for debug/ndebug, though I honestly haven't tracked what the settled integer overflow behaviour is.

GuillaumeGomez · 2015-02-19T10:59:12Z

Okay ! Then I just have to implement it !

GuillaumeGomez · 2015-02-19T16:10:18Z

@pnkfelix posted an interesting gist post here.

pnkfelix · 2015-02-23T16:50:19Z

cc #22240

alexcrichton · 2015-02-24T01:09:17Z

src/libcore/num/mod.rs

+                        acc = acc * base;
+                        if did_base_overflow {
+                            panic!("overflow detected");
+                        }


I'm a little confused by these overflow semantics. How come the overflow is only registered on the next iteration of the loop? Additionally, how come overflow is registered at all? In theory this has the same overflow semantics as a * b which is actually listed below (with base * base) so isn't overflow naturally detected?

When the base overflows on the last iteration, it does not corrupt the returned result and should not cause a panic. This is an edge case I discovered working on the arith-overflow branch.

(Having said that, I prefer my encoding of this semantics, given in the gist linked above)

That's I what I couldn't completely understand : if we panic, why should we
give attention to the returned result ?
Le 24 févr. 2015 09:54, "Felix S Klock II" notifications@github.com a
écrit :

In src/libcore/num/mod.rs
#22087 (comment):

@@ -464,6 +452,30 @@ macro_rules! uint_impl {
v => Some(self / v),
}
}
+

#[inline]

fn pow(self, mut exp: u32) -> Self {

let mut base = self;

let mut acc: Self = Int::one();

let mut did_base_overflow = false;

while exp > 0 {

if (exp & 1) == 1 {

acc = acc \* base;

if did_base_overflow {

panic!("overflow detected");

}

(Having said that, I prefer my encoding of this semantics, given in the
gist linked above)

—
Reply to this email directly or view it on GitHub
https://github.com/rust-lang/rust/pull/22087/files#r25236519.

@GuillaumeGomez I fear I do not understand your question.

It seems like you are asking "why do we care about the returned result in the cases where we panic?" When we panic, of course there is no returned result. I care about enforcing the following rule: panic if and only if the accumulated acc (the "to-be-returned result") has been corrupted by an overflow. If we panic, then I want the reason to be because the accumulated value has become useless. I do not want to panic merely because the computation base * base overflows when its resulting value is never actually used.

From @alexcrichton 's comment, it sounds like he is assuming that your code was written in the context of a version of Rust that panics on overflow from operations like base * base. (While on the other hand, you have written your code to still panic on overflow even in a context where base * base itself does not.) If you look at my gist, it deliberately uses a version of multiply for the base * base squaring computation at the end of each iteration that does not cause a panic when that squaring overflows. You would need to change your code to also use that variant if you want to ensure that the base * base computation does not itself immediately panic.

You perfectly replied to my question ! @alexcrichton gave me doubts.
Le 24 févr. 2015 11:09, "Felix S Klock II" notifications@github.com a
écrit :

In src/libcore/num/mod.rs
#22087 (comment):

@@ -464,6 +452,30 @@ macro_rules! uint_impl {
v => Some(self / v),
}
}
+

#[inline]

fn pow(self, mut exp: u32) -> Self {

let mut base = self;

let mut acc: Self = Int::one();

let mut did_base_overflow = false;

while exp > 0 {

if (exp & 1) == 1 {

acc = acc \* base;

if did_base_overflow {

panic!("overflow detected");

}

@GuillaumeGomez https://github.com/GuillaumeGomez I fear I do not
understand your question.

It seems like you are asking "why do we care about the returned result in
the cases where we panic?" When we panic, of course there is no returned
result. I care about enforcing the following rule: panic if and only if
the accumulated acc (the "to-be-returned result") has been corrupted by
an overflow. If we panic, then I want to to be because the accumulated
value has become useless. I do not want to panic merely because the
computation base * base overflows when its resulting value is never
actually used.

From @alexcrichton https://github.com/alexcrichton 's comment, it
sounds like he is assuming that your code was written in the context of a
version of Rust that panics on overflow from operations like base * base.
(While on the other hand, you have written your code to still panic on
overflow even in a context where base * base itself does not.) If you
look at my gist, it deliberately uses a version of multiply for the base

base squaring computation at the end of each iteration that does not
cause a panic when that squaring overflows. You would need to change your
code to also use that variant if you want to ensure that the base * base
computation does not itself immediately panic.

—
Reply to this email directly or view it on GitHub
https://github.com/rust-lang/rust/pull/22087/files#r25241010.

alexcrichton · 2015-02-24T18:37:07Z

@GuillaumeGomez can you change this PR to only update uint to u32? I think @pnkfelix can probably handle the overflow semantics part in #22532

GuillaumeGomez · 2015-02-24T18:40:43Z

As soon as I have a computer, I do that. Oterwise he can just rebase on my
PR and make whatever changes he wants, no ? If he does it that way, I'll
close this PR.
Le 24 févr. 2015 19:37, "Alex Crichton" notifications@github.com a écrit :

@GuillaumeGomez https://github.com/GuillaumeGomez can you change this
PR to only update uint to u32? I think @pnkfelix
https://github.com/pnkfelix can probably handle the overflow semantics
part in #22532 #22532

—
Reply to this email directly or view it on GitHub
#22087 (comment).

pnkfelix · 2015-02-24T18:59:40Z

@GuillaumeGomez i don't know how long its going to take me to get arith-oflo landed. Please land this change on its own, in a rollup if you like, I guess.

pnkfelix · 2015-02-24T19:02:53Z

@GuillaumeGomez (or, if you will not have access to time or a computer in the near future, I can take over this PR for you. I largely don't want to mix this API change in with the arith-oflo work; they are distinct efforts.)

GuillaumeGomez · 2015-02-24T19:02:57Z

Ok I do that (tomorrow) !
Le 24 févr. 2015 20:00, "Felix S Klock II" notifications@github.com a
écrit :

@GuillaumeGomez https://github.com/GuillaumeGomez i don't know how long
its going to take me to get arith-oflo landed. Please land this change on
its own, in a rollup if you like, I guess.

—
Reply to this email directly or view it on GitHub
#22087 (comment).

GuillaumeGomez · 2015-02-24T19:08:03Z

My actual computer is dead, i'm supposed to receive the new one by the end
of the week. Let us hope !
Le 24 févr. 2015 20:03, "Felix S Klock II" notifications@github.com a
écrit :

@GuillaumeGomez https://github.com/GuillaumeGomez (or, if you will not
have access to time or a computer in the near future, I can take over this
PR for you. I largely don't want to mix this API change in with the
arith-oflo work; they are distinct efforts.)

—
Reply to this email directly or view it on GitHub
#22087 (comment).

GuillaumeGomez · 2015-02-26T23:55:17Z

I removed the under/overflow handling. @pnkfelix: you can take it on now ! @alexcrichton: waiting for you now.

alexcrichton · 2015-02-27T00:33:41Z

src/libcore/num/mod.rs

+                    exp /= 2;
+                }
+                acc
+            }


Would it be possible to leave the default method implementation for these methods? It looks like both impls are the same currently.

It was in prevision for under/overflow handling. But if you want yes I can.

GuillaumeGomez · 2015-02-27T20:18:03Z

@alexcrichton: squashed

alexcrichton · 2015-02-27T20:20:00Z

Did some extra commits leak in?

GuillaumeGomez · 2015-02-27T21:01:34Z

Finally solved...

alexcrichton · 2015-02-27T21:20:47Z

It looks like there are still some extra commits here (there should probably just be one)

GuillaumeGomez · 2015-02-27T22:33:02Z

There isn't anymore.

alexcrichton · 2015-02-27T22:39:18Z

src/libcore/num/mod.rs

@@ -1672,6 +1673,7 @@ macro_rules! from_str_radix_int_impl {
                let is_signed_ty = (0 as $T) > Int::min_value();

                match src.slice_shift_char() {
+                    Some(('-', "")) => Err(PIE { kind: Empty }),


This seems to be leaking over from #22747

GuillaumeGomez · 2015-02-27T22:48:52Z

Done.

GuillaumeGomez · 2015-02-28T00:05:13Z

I squashed the remaining commits and rename it.

alexcrichton · 2015-02-28T00:05:41Z

@bors: r+ 73ce70807e6c5f97206323429463018ab40a2eec

bors · 2015-02-28T02:21:54Z

⌛ Testing commit 73ce708 with merge c1e597c...

bors · 2015-02-28T03:37:19Z

💔 Test failed - auto-mac-32-opt

Manishearth · 2015-02-28T06:00:00Z

assert_eq! is a macro, not a function

/Users/rustbuild/src/rust-buildbot/slave/auto-mac-32-opt/build/src/libcoretest/num/int_macros.rs:11:1: 217:3 note: in expansion of int_module!
/Users/rustbuild/src/rust-buildbot/slave/auto-mac-32-opt/build/src/libcoretest/num/int.rs:11:1: 11:23 note: expansion site
/Users/rustbuild/src/rust-buildbot/slave/auto-mac-32-opt/build/src/libcoretest/num/int_macros.rs:213:9: 213:18 error: unresolved name `assert_eq`
/Users/rustbuild/src/rust-buildbot/slave/auto-mac-32-opt/build/src/libcoretest/num/int_macros.rs:213         assert_eq(r.exp(3u32), 8i32);

(snippet of error, there are more)

GuillaumeGomez · 2015-03-01T01:43:22Z

I updated to master and I fixed tests. Waiting for rollup. @alexcrichton @Manishearth

alexcrichton · 2015-03-01T06:55:46Z

@bors: r+ 1c4fb90

bors · 2015-03-01T08:59:29Z

⌛ Testing commit 1c4fb90 with merge 0eb0ba3...

Fixes issue #22016

bors · 2015-03-01T11:25:11Z

☀️ Test successful - auto-linux-32-nopt-t, auto-linux-32-opt, auto-linux-64-nopt-t, auto-linux-64-opt, auto-linux-64-x-android-t, auto-mac-32-opt, auto-mac-64-nopt-t, auto-mac-64-opt, auto-win-32-nopt-t, auto-win-32-opt, auto-win-64-nopt-t, auto-win-64-opt

`Int::pow()` takes u32 instead of usize; see rust-lang/rust#22087.

rust-highfive assigned alexcrichton Feb 8, 2015

GuillaumeGomez changed the title ~~Fixes issue #22016~~ Make Int::pow() take exp as Self instead usize Feb 8, 2015

nikomatsakis mentioned this pull request Feb 19, 2015

Audit integer types in the standard library #22240

Closed

40 tasks

alexcrichton reviewed Feb 24, 2015
View reviewed changes

alexcrichton reviewed Feb 27, 2015
View reviewed changes

alexcrichton changed the title ~~Make Int::pow() take exp as Self instead usize~~ Make Int::pow() take exp as u32 instead usize Feb 27, 2015

Make Int::pow() take exp as u32 instead usize

1c4fb90

bors added a commit that referenced this pull request Mar 1, 2015

Auto merge of #22087 - GuillaumeGomez:int-pow, r=alexcrichton

0eb0ba3

Fixes issue #22016

bors merged commit 1c4fb90 into rust-lang:master Mar 1, 2015

bors mentioned this pull request Mar 1, 2015

Implement arithmetic overflow changes #22532

Merged

zsiciarz added a commit to zsiciarz/slow_primes that referenced this pull request Mar 4, 2015

Update to (b4c965ee8 2015-03-02) (built 2015-03-03)

1f93467

`Int::pow()` takes u32 instead of usize; see rust-lang/rust#22087.

zsiciarz mentioned this pull request Mar 4, 2015

Update to (b4c965ee8 2015-03-02) (built 2015-03-03) huonw/slow_primes#10

Merged

Make Int::pow() take exp as u32 instead usize #22087

Make Int::pow() take exp as u32 instead usize #22087

Conversation

GuillaumeGomez commented Feb 8, 2015

rust-highfive commented Feb 8, 2015

dotdash commented Feb 8, 2015

GuillaumeGomez commented Feb 8, 2015

dotdash commented Feb 8, 2015

GuillaumeGomez commented Feb 8, 2015

pczarn commented Feb 9, 2015

GuillaumeGomez commented Feb 9, 2015

pczarn commented Feb 9, 2015

GuillaumeGomez commented Feb 9, 2015

alexcrichton commented Feb 9, 2015

GuillaumeGomez commented Feb 10, 2015

Diggsey commented Feb 11, 2015

GuillaumeGomez commented Feb 11, 2015

alexcrichton commented Feb 11, 2015

GuillaumeGomez commented Feb 12, 2015

brson commented Feb 18, 2015

GuillaumeGomez commented Feb 18, 2015

Gankra commented Feb 19, 2015

GuillaumeGomez commented Feb 19, 2015

GuillaumeGomez commented Feb 19, 2015

pnkfelix commented Feb 23, 2015

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

alexcrichton commented Feb 24, 2015

GuillaumeGomez commented Feb 24, 2015

pnkfelix commented Feb 24, 2015

pnkfelix commented Feb 24, 2015

GuillaumeGomez commented Feb 24, 2015

GuillaumeGomez commented Feb 24, 2015

GuillaumeGomez commented Feb 26, 2015

Choose a reason for hiding this comment

Choose a reason for hiding this comment

GuillaumeGomez commented Feb 27, 2015

alexcrichton commented Feb 27, 2015

GuillaumeGomez commented Feb 27, 2015

alexcrichton commented Feb 27, 2015

GuillaumeGomez commented Feb 27, 2015

Choose a reason for hiding this comment

GuillaumeGomez commented Feb 27, 2015

GuillaumeGomez commented Feb 28, 2015

alexcrichton commented Feb 28, 2015

bors commented Feb 28, 2015

bors commented Feb 28, 2015

Manishearth commented Feb 28, 2015

GuillaumeGomez commented Mar 1, 2015

alexcrichton commented Mar 1, 2015

bors commented Mar 1, 2015

bors commented Mar 1, 2015