You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2020/08/27 12:12:02 UTC
[commons-numbers] 01/03: [NUMBERS-151] performance refine for
ArithmeticUtils.pow
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-numbers.git
commit 42ebc644ff46e0cef75a59512390c9b78fa16a04
Author: XenoAmess <xe...@gmail.com>
AuthorDate: Wed Aug 26 01:35:29 2020 +0800
[NUMBERS-151] performance refine for ArithmeticUtils.pow
---
.../commons/numbers/core/ArithmeticUtils.java | 52 ++++++++++++++++++++++
.../commons/numbers/core/ArithmeticUtilsTest.java | 19 ++++++++
2 files changed, 71 insertions(+)
diff --git a/commons-numbers-core/src/main/java/org/apache/commons/numbers/core/ArithmeticUtils.java b/commons-numbers-core/src/main/java/org/apache/commons/numbers/core/ArithmeticUtils.java
index b2bb256..bbd8292 100644
--- a/commons-numbers-core/src/main/java/org/apache/commons/numbers/core/ArithmeticUtils.java
+++ b/commons-numbers-core/src/main/java/org/apache/commons/numbers/core/ArithmeticUtils.java
@@ -266,6 +266,16 @@ public final class ArithmeticUtils {
/**
* Raise an int to an int power.
*
+ * <p>Special cases:</p>
+ * <ul>
+ * <li>{@code k^0} returns {@code 1} (including {@code k=0})
+ * <li>{@code k^1} returns {@code k} (including {@code k=0})
+ * <li>{@code 0^0} returns {@code 1}
+ * <li>{@code 0^e} returns {@code 0}
+ * <li>{@code 1^e} returns {@code 1}
+ * <li>{@code (-1)^e} returns {@code -1 or 1} if {@code e} is odd or even
+ * </ul>
+ *
* @param k Number to raise.
* @param e Exponent (must be positive or zero).
* @return \( k^e \)
@@ -278,6 +288,22 @@ public final class ArithmeticUtils {
throw new IllegalArgumentException(NEGATIVE_EXPONENT_1 + e + NEGATIVE_EXPONENT_2);
}
+ if (k == 0) {
+ return e == 0 ? 1 : 0;
+ }
+
+ if (k == 1) {
+ return 1;
+ }
+
+ if (k == -1) {
+ return (e & 1) == 0 ? 1 : -1;
+ }
+
+ if (e >= 31) {
+ throw new ArithmeticException("integer overflow");
+ }
+
int exp = e;
int result = 1;
int k2p = k;
@@ -300,6 +326,16 @@ public final class ArithmeticUtils {
/**
* Raise a long to an int power.
*
+ * <p>Special cases:</p>
+ * <ul>
+ * <li>{@code k^0} returns {@code 1} (including {@code k=0})
+ * <li>{@code k^1} returns {@code k} (including {@code k=0})
+ * <li>{@code 0^0} returns {@code 1}
+ * <li>{@code 0^e} returns {@code 0}
+ * <li>{@code 1^e} returns {@code 1}
+ * <li>{@code (-1)^e} returns {@code -1 or 1} if {@code e} is odd or even
+ * </ul>
+ *
* @param k Number to raise.
* @param e Exponent (must be positive or zero).
* @return \( k^e \)
@@ -312,6 +348,22 @@ public final class ArithmeticUtils {
throw new IllegalArgumentException(NEGATIVE_EXPONENT_1 + e + NEGATIVE_EXPONENT_2);
}
+ if (k == 0L) {
+ return e == 0 ? 1L : 0L;
+ }
+
+ if (k == 1L) {
+ return 1L;
+ }
+
+ if (k == -1L) {
+ return (e & 1) == 0 ? 1L : -1L;
+ }
+
+ if (e >= 63) {
+ throw new ArithmeticException("long overflow");
+ }
+
int exp = e;
long result = 1;
long k2p = k;
diff --git a/commons-numbers-core/src/test/java/org/apache/commons/numbers/core/ArithmeticUtilsTest.java b/commons-numbers-core/src/test/java/org/apache/commons/numbers/core/ArithmeticUtilsTest.java
index 5a4bb73..5f466a2 100644
--- a/commons-numbers-core/src/test/java/org/apache/commons/numbers/core/ArithmeticUtilsTest.java
+++ b/commons-numbers-core/src/test/java/org/apache/commons/numbers/core/ArithmeticUtilsTest.java
@@ -422,6 +422,25 @@ class ArithmeticUtilsTest {
}
@Test
+ void testPowEdgeCases() {
+ Assertions.assertEquals(0, ArithmeticUtils.pow(0, 2));
+ Assertions.assertEquals(0L, ArithmeticUtils.pow(0L, 2));
+ Assertions.assertEquals(0, ArithmeticUtils.pow(0, 1));
+ Assertions.assertEquals(0L, ArithmeticUtils.pow(0L, 1));
+ Assertions.assertEquals(1, ArithmeticUtils.pow(0, 0));
+ Assertions.assertEquals(1L, ArithmeticUtils.pow(0L, 0));
+
+ for (int i = 20; i <= 35; i++) {
+ final int ti = i;
+ Assertions.assertThrows(ArithmeticException.class, () -> ArithmeticUtils.pow(3, ti));
+ }
+ for (int i = 40; i <= 70; i++) {
+ final int ti = i;
+ Assertions.assertThrows(ArithmeticException.class, () -> ArithmeticUtils.pow(3L, ti));
+ }
+ }
+
+ @Test
void testIsPowerOfTwo() {
final int n = 1025;
final boolean[] expected = new boolean[n];