You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2013/05/28 18:04:32 UTC
svn commit: r1486982 - in /commons/proper/math/trunk/src:
changes/changes.xml main/java/org/apache/commons/math3/util/MathArrays.java
test/java/org/apache/commons/math3/util/MathArraysTest.java
Author: tn
Date: Tue May 28 16:04:32 2013
New Revision: 1486982
URL: http://svn.apache.org/r1486982
Log:
[MATH-851] Added method MathArrays.convolve, thanks to Clemens Novak for the patch.
Modified:
commons/proper/math/trunk/src/changes/changes.xml
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/MathArrays.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/MathArraysTest.java
Modified: commons/proper/math/trunk/src/changes/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/changes/changes.xml?rev=1486982&r1=1486981&r2=1486982&view=diff
==============================================================================
--- commons/proper/math/trunk/src/changes/changes.xml (original)
+++ commons/proper/math/trunk/src/changes/changes.xml Tue May 28 16:04:32 2013
@@ -51,6 +51,10 @@ If the output is not quite correct, chec
</properties>
<body>
<release version="x.y" date="TBD" description="TBD">
+ <action dev="tn" type="add" issue="MATH-851" due-to="Clemens Novak">
+ Added method "MathArrays#convolve(double[], double[])" to compute the
+ discrete, linear convolution of two sequences.
+ </action>
<action dev="tn" type="add" issue="MATH-977">
Added low-discrepancy random generator "HaltonSequenceGenerator".
</action>
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/MathArrays.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/MathArrays.java?rev=1486982&r1=1486981&r2=1486982&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/MathArrays.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/MathArrays.java Tue May 28 16:04:32 2013
@@ -29,6 +29,7 @@ import org.apache.commons.math3.exceptio
import org.apache.commons.math3.exception.MathArithmeticException;
import org.apache.commons.math3.exception.MathIllegalArgumentException;
import org.apache.commons.math3.exception.MathInternalError;
+import org.apache.commons.math3.exception.NoDataException;
import org.apache.commons.math3.exception.NonMonotonicSequenceException;
import org.apache.commons.math3.exception.NotPositiveException;
import org.apache.commons.math3.exception.NotStrictlyPositiveException;
@@ -1352,4 +1353,51 @@ public class MathArrays {
return array;
}
+ /**
+ * Calculates the convolution between two sequences.
+ * <p>
+ * The solution is obtained via straightforward computation of the convolution sum (and not via FFT; for longer sequences,
+ * the performance of this method might be inferior to an FFT-based implementation).
+ *
+ * @param x the first sequence (double array of length {@code N}); the sequence is assumed to be zero elsewhere
+ * (i.e. {x[i]}=0 for i<0 and i>={@code N}). Typically, this sequence will represent an input signal to a system.
+ * @param h the second sequence (double array of length {@code M}); the sequence is assumed to be zero elsewhere
+ * (i.e. {h[i]}=0 for i<0 and i>={@code M}). Typically, this sequence will represent the impulse response of the system.
+ * @return the convolution of {@code x} and {@code h} (double array of length {@code N} + {@code M} -1)
+ * @throws NullArgumentException if either {@code x} or {@code h} is null
+ * @throws NoDataException if either {@code x} or {@code h} is empty
+ *
+ * @see <a href="http://en.wikipedia.org/wiki/Convolution">Convolution (Wikipedia)</a>
+ * @since 4.0
+ */
+ public static double[] convolve(double[] x, double[] h) throws NullArgumentException, NoDataException {
+ MathUtils.checkNotNull(x);
+ MathUtils.checkNotNull(h);
+
+ final int N = x.length;
+ final int M = h.length;
+
+ if (N == 0 || M == 0) {
+ throw new NoDataException();
+ }
+
+ // initialize the output array
+ final int totalLength = N + M - 1;
+ final double[] y = new double[totalLength];
+
+ // straightforward implementation of the convolution sum
+ for (int n = 0; n < totalLength; n++) {
+ double yn = 0;
+ for (int k = 0; k < M; k++) {
+ final int j = n - k;
+ if ((j > -1) && (j < N) ) {
+ yn = yn + x[j] * h[k];
+ }
+ }
+ y[n] = yn;
+ }
+
+ return y;
+ }
+
}
Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/MathArraysTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/MathArraysTest.java?rev=1486982&r1=1486981&r2=1486982&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/MathArraysTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/MathArraysTest.java Tue May 28 16:04:32 2013
@@ -13,12 +13,15 @@
*/
package org.apache.commons.math3.util;
+import static org.junit.Assert.fail;
+
import java.util.Arrays;
import org.apache.commons.math3.TestUtils;
import org.apache.commons.math3.exception.DimensionMismatchException;
import org.apache.commons.math3.exception.MathArithmeticException;
import org.apache.commons.math3.exception.MathIllegalArgumentException;
+import org.apache.commons.math3.exception.NoDataException;
import org.apache.commons.math3.exception.NonMonotonicSequenceException;
import org.apache.commons.math3.exception.NotPositiveException;
import org.apache.commons.math3.exception.NotStrictlyPositiveException;
@@ -833,4 +836,62 @@ public class MathArraysTest {
Assert.fail("expecting MathIllegalArgumentException");
} catch (MathIllegalArgumentException ex) {}
}
+
+ @Test
+ public void testConvolve() {
+ /* Test Case (obtained via SciPy)
+ * x=[1.2,-1.8,1.4]
+ * h=[1,0.8,0.5,0.3]
+ * convolve(x,h) -> array([ 1.2 , -0.84, 0.56, 0.58, 0.16, 0.42])
+ */
+ double[] x1 = { 1.2, -1.8, 1.4 };
+ double[] h1 = { 1, 0.8, 0.5, 0.3 };
+ double[] y1 = { 1.2, -0.84, 0.56, 0.58, 0.16, 0.42 };
+ double tolerance = 1e-13;
+
+ double[] yActual = MathArrays.convolve(x1, h1);
+ Assert.assertArrayEquals(y1, yActual, tolerance);
+
+ double[] x2 = { 1, 2, 3 };
+ double[] h2 = { 0, 1, 0.5 };
+ double[] y2 = { 0, 1, 2.5, 4, 1.5 };
+
+ yActual = MathArrays.convolve(x2, h2);
+ Assert.assertArrayEquals(y2, yActual, tolerance);
+
+ try {
+ MathArrays.convolve(new double[]{1, 2}, null);
+ fail("an exception should have been thrown");
+ } catch (NullArgumentException e) {
+ // expected behavior
+ }
+
+ try {
+ MathArrays.convolve(null, new double[]{1, 2});
+ fail("an exception should have been thrown");
+ } catch (NullArgumentException e) {
+ // expected behavior
+ }
+
+ try {
+ MathArrays.convolve(new double[]{1, 2}, new double[]{});
+ fail("an exception should have been thrown");
+ } catch (NoDataException e) {
+ // expected behavior
+ }
+
+ try {
+ MathArrays.convolve(new double[]{}, new double[]{1, 2});
+ fail("an exception should have been thrown");
+ } catch (NoDataException e) {
+ // expected behavior
+ }
+
+ try {
+ MathArrays.convolve(new double[]{}, new double[]{});
+ fail("an exception should have been thrown");
+ } catch (NoDataException e) {
+ // expected behavior
+ }
+ }
}
Re: [Math] Accepting contributions (Was: svn commit: r1486982 - ...)
Posted by Thomas Neidhart <th...@gmail.com>.
On Wed, May 29, 2013 at 12:40 AM, Gilles <gi...@harfang.homelinux.org>wrote:
> On Tue, 28 May 2013 20:47:30 +0200, Thomas Neidhart wrote:
>
>> On 05/28/2013 08:20 PM, Gilles wrote:
>>
>>> On Tue, 28 May 2013 16:04:32 -0000, tn@apache.org wrote:
>>>
>>>> Author: tn
>>>> Date: Tue May 28 16:04:32 2013
>>>> New Revision: 1486982
>>>>
>>>> URL: http://svn.apache.org/r1486982
>>>> Log:
>>>> [MATH-851] Added method MathArrays.convolve, thanks to Clemens Novak
>>>> for the patch.
>>>>
>>>
>>> -1
>>>
>>> A significant part of this small patch (code and doc) contains formatting
>>> mistakes and non-conventional notations, as was indicated in the
>>> comments.
>>> If someone took the time to review something, please take it into
>>> account.
>>>
>>> The unit test is also not correctly defined; we agreed that newer code
>>> should test _one_ thing per test method.
>>> Also, precondition checks should use the "expected" attribute of the
>>> "@Test" annotation.
>>>
>>
>> Most of the suggestions were already corrected by the OP with an updated
>> patch, the rest I changed to the usual style I use when committing (see
>> the commit log).
>>
>
> My reply was based on reading the diff.
>
> [Are you really using capital letters as variable names?]
I thought it makes sense in this case (and did a grep before in the
codebase to see if there are other occurrences of it)
>
> Efficiency-wise, I wonder about the condition nested inside the
>>> double-loop:
>>>
>>> if ((j > -1) && (j < N) ) {
>>> yn = yn + x[j] * h[k];
>>> }
>>>
>>
>> yes I agree, this could be further improved.
>>
>> As was also suggested in the comments, a "real" application (and/or a
>>> discussion on the "dev" ML, preferably initiated by the OP) would have
>>> been welcome to assess the pertinence of including this code in the
>>> proposed form.
>>>
>>
>> It is also present in numpy (see
>>
>> http://docs.scipy.org/doc/**numpy/reference/generated/**
>> numpy.convolve.html<http://docs.scipy.org/doc/numpy/reference/generated/numpy.convolve.html>
>> )
>> so I guess there will be a practical use for it.
>>
>
> By this post, I ask whether it is sufficient reason for committing
> sub-par code that is currently not used by anyone.
> I suggested the OP 3 ways to start getting involved; the absence of
> reaction was IMHO reason enough not to rush including this code.
> [It has obviously nothing to do with judging that convolution is not
> worth implementing.]
>
> CM needs contributors, right; but it is quite unrelated to piling up
> unused/untested code.
> At one point, some years ago, there was a sort of acknowledgment that
> submitting a contribution was accompanied with an informal commitment
> to maintain it.
> Lacking that either gives more work to current committers or lowers
> the average quality of the library.
>
Well yes, I agree in general, but I did not expect to run into trouble with
this contribution: it's small and simple enough that everybody can dig into
it within minutes.
Also there are tests, and you can easily compare its result with other
implementations.
I think we do a pretty good job in maintaining the library, where we are
clearly lacking is documentation, and there I would like to see more
contributions from our users too if possible.
Thomas
Re: [Math] Accepting contributions (Was: svn commit: r1486982 - ...)
Posted by Gilles <gi...@harfang.homelinux.org>.
On Tue, 28 May 2013 20:47:30 +0200, Thomas Neidhart wrote:
> On 05/28/2013 08:20 PM, Gilles wrote:
>> On Tue, 28 May 2013 16:04:32 -0000, tn@apache.org wrote:
>>> Author: tn
>>> Date: Tue May 28 16:04:32 2013
>>> New Revision: 1486982
>>>
>>> URL: http://svn.apache.org/r1486982
>>> Log:
>>> [MATH-851] Added method MathArrays.convolve, thanks to Clemens
>>> Novak
>>> for the patch.
>>
>> -1
>>
>> A significant part of this small patch (code and doc) contains
>> formatting
>> mistakes and non-conventional notations, as was indicated in the
>> comments.
>> If someone took the time to review something, please take it into
>> account.
>>
>> The unit test is also not correctly defined; we agreed that newer
>> code
>> should test _one_ thing per test method.
>> Also, precondition checks should use the "expected" attribute of the
>> "@Test" annotation.
>
> Most of the suggestions were already corrected by the OP with an
> updated
> patch, the rest I changed to the usual style I use when committing
> (see
> the commit log).
My reply was based on reading the diff.
[Are you really using capital letters as variable names?]
>> Efficiency-wise, I wonder about the condition nested inside the
>> double-loop:
>>
>> if ((j > -1) && (j < N) ) {
>> yn = yn + x[j] * h[k];
>> }
>
> yes I agree, this could be further improved.
>
>> As was also suggested in the comments, a "real" application (and/or
>> a
>> discussion on the "dev" ML, preferably initiated by the OP) would
>> have
>> been welcome to assess the pertinence of including this code in the
>> proposed form.
>
> It is also present in numpy (see
>
> http://docs.scipy.org/doc/numpy/reference/generated/numpy.convolve.html)
> so I guess there will be a practical use for it.
By this post, I ask whether it is sufficient reason for committing
sub-par code that is currently not used by anyone.
I suggested the OP 3 ways to start getting involved; the absence of
reaction was IMHO reason enough not to rush including this code.
[It has obviously nothing to do with judging that convolution is not
worth implementing.]
CM needs contributors, right; but it is quite unrelated to piling up
unused/untested code.
At one point, some years ago, there was a sort of acknowledgment that
submitting a contribution was accompanied with an informal commitment
to maintain it.
Lacking that either gives more work to current committers or lowers
the average quality of the library.
Regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Accepting contributions (Was: svn commit: r1486982 - ...)
Posted by Thomas Neidhart <th...@gmail.com>.
On 05/28/2013 08:20 PM, Gilles wrote:
> On Tue, 28 May 2013 16:04:32 -0000, tn@apache.org wrote:
>> Author: tn
>> Date: Tue May 28 16:04:32 2013
>> New Revision: 1486982
>>
>> URL: http://svn.apache.org/r1486982
>> Log:
>> [MATH-851] Added method MathArrays.convolve, thanks to Clemens Novak
>> for the patch.
>
> -1
>
> A significant part of this small patch (code and doc) contains formatting
> mistakes and non-conventional notations, as was indicated in the comments.
> If someone took the time to review something, please take it into account.
>
> The unit test is also not correctly defined; we agreed that newer code
> should test _one_ thing per test method.
> Also, precondition checks should use the "expected" attribute of the
> "@Test" annotation.
Most of the suggestions were already corrected by the OP with an updated
patch, the rest I changed to the usual style I use when committing (see
the commit log).
> Efficiency-wise, I wonder about the condition nested inside the
> double-loop:
>
> if ((j > -1) && (j < N) ) {
> yn = yn + x[j] * h[k];
> }
yes I agree, this could be further improved.
> As was also suggested in the comments, a "real" application (and/or a
> discussion on the "dev" ML, preferably initiated by the OP) would have
> been welcome to assess the pertinence of including this code in the
> proposed form.
It is also present in numpy (see
http://docs.scipy.org/doc/numpy/reference/generated/numpy.convolve.html)
so I guess there will be a practical use for it.
Thomas
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Accepting contributions (Was: svn commit: r1486982 - ...)
Posted by Thomas Neidhart <th...@gmail.com>.
On 05/28/2013 08:20 PM, Gilles wrote:
> On Tue, 28 May 2013 16:04:32 -0000, tn@apache.org wrote:
>> Author: tn
>> Date: Tue May 28 16:04:32 2013
>> New Revision: 1486982
>>
>> URL: http://svn.apache.org/r1486982
>> Log:
>> [MATH-851] Added method MathArrays.convolve, thanks to Clemens Novak
>> for the patch.
>
> -1
>
> A significant part of this small patch (code and doc) contains formatting
> mistakes and non-conventional notations, as was indicated in the comments.
> If someone took the time to review something, please take it into account.
>
> The unit test is also not correctly defined; we agreed that newer code
> should test _one_ thing per test method.
> Also, precondition checks should use the "expected" attribute of the
> "@Test" annotation.
>
> Efficiency-wise, I wonder about the condition nested inside the
> double-loop:
>
> if ((j > -1) && (j < N) ) {
> yn = yn + x[j] * h[k];
> }
>
> As was also suggested in the comments, a "real" application (and/or a
> discussion on the "dev" ML, preferably initiated by the OP) would have
> been welcome to assess the pertinence of including this code in the
> proposed form.
I improved the code / javadoc. Do you now agree with it?
Thomas
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
[Math] Accepting contributions (Was: svn commit: r1486982 - ...)
Posted by Gilles <gi...@harfang.homelinux.org>.
On Tue, 28 May 2013 16:04:32 -0000, tn@apache.org wrote:
> Author: tn
> Date: Tue May 28 16:04:32 2013
> New Revision: 1486982
>
> URL: http://svn.apache.org/r1486982
> Log:
> [MATH-851] Added method MathArrays.convolve, thanks to Clemens Novak
> for the patch.
-1
A significant part of this small patch (code and doc) contains
formatting
mistakes and non-conventional notations, as was indicated in the
comments.
If someone took the time to review something, please take it into
account.
The unit test is also not correctly defined; we agreed that newer code
should test _one_ thing per test method.
Also, precondition checks should use the "expected" attribute of the
"@Test" annotation.
Efficiency-wise, I wonder about the condition nested inside the
double-loop:
if ((j > -1) && (j < N) ) {
yn = yn + x[j] * h[k];
}
As was also suggested in the comments, a "real" application (and/or a
discussion on the "dev" ML, preferably initiated by the OP) would have
been welcome to assess the pertinence of including this code in the
proposed form.
This is a perfect example of "someone, some day, might need this".
IMO, contributions should come from people who _actually_ use the
proposed
code; we should not accept them as a mere coding exercises that will
potentially increase the burden on regular contributors.
Gilles
> Modified:
> commons/proper/math/trunk/src/changes/changes.xml
>
>
> commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/MathArrays.java
>
>
> commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/MathArraysTest.java
>
> [...]
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org