9:01 a.m.
Hi,
while looking at the example scripts I've noticed convolve.inp, and then
also the paragraph about Convolution in the guide (cheat sheet chapter,
p. 154 for me).
I wonder if this should be wrapped in a hansl function and added to the
'extra' addon, like this:
<hansl>
function void padzeros(matrix *a, matrix *b)
a = vec(a)
b = vec(b)
outrows = rows(a) + rows(b) - 1
a |= zeros(outrows - rows(a), 1)
b |= zeros(outrows - rows(b), 1)
end function
function matrix convolve(matrix p, matrix q)
padzeros(&p, &q)
return filter(p, q)
end function
# And for comparison only:
function matrix convolve_fft(matrix p, matrix q)
padzeros(&p, &q)
f = fft(p ~ q)
return ffti(cmult(f[,1:2], f[,3:4]))
end function
<hansl>
As mentioned in the guide, the filter-based variant is indeed about 30%
faster in my examples.
BTW, I think there are some typos in the notation in the Convolution
paragraph: The sum indices i should start at 0, not 1, and the upper
bound for the R(x) index should be p + q - 1 instead of pq-1.
Any feedback welcome.
thanks,
sven
8:49 p.m.
On Tue, 19 Mar 2019, Sven Schreiber wrote:
Hi,
while looking at the example scripts I've noticed convolve.inp, and then
also the paragraph about Convolution in the guide (cheat sheet chapter,
p. 154 for me).
I wonder if this should be wrapped in a hansl function and added to the
'extra' addon, like this:
<hansl>
function void padzeros(matrix *a, matrix *b)
a = vec(a)
b = vec(b)
outrows = rows(a) + rows(b) - 1
a |= zeros(outrows - rows(a), 1)
b |= zeros(outrows - rows(b), 1)
end function
function matrix convolve(matrix p, matrix q)
padzeros(&p, &q)
return filter(p, q)
end function
# And for comparison only:
function matrix convolve_fft(matrix p, matrix q)
padzeros(&p, &q)
f = fft(p ~ q)
return ffti(cmult(f[,1:2], f[,3:4]))
end function
<hansl>
As mentioned in the guide, the filter-based variant is indeed about 30%
faster in my examples.
BTW, I think there are some typos in the notation in the Convolution
paragraph: The sum indices i should start at 0, not 1, and the upper
bound for the R(x) index should be p + q - 1 instead of pq-1.
I agree that the summation indices as stated do not seem to allow
for a constant term. One could either say
P(x) = \sum_{i=1}^p p_i x^{i-1}
for p = the degree of the polynomial + 1, or
P(x) = \sum_{i=0}^p p_i x^i
for p = the degree of the polynomial.
Not sure about the R(x) index at this point!
Allin
9:05 p.m.
On Tue, 19 Mar 2019, Allin Cottrell wrote:
On Tue, 19 Mar 2019, Sven Schreiber wrote:
> BTW, I think there are some typos in the notation in the Convolution
> paragraph: The sum indices i should start at 0, not 1, and the upper
> bound for the R(x) index should be p + q - 1 instead of pq-1.
I agree that the summation indices as stated do not seem to allow for a
constant term. One could either say
P(x) = \sum_{i=1}^p p_i x^{i-1}
for p = the degree of the polynomial + 1, or
P(x) = \sum_{i=0}^p p_i x^i
for p = the degree of the polynomial.
Notation can be a bugger, and not wanting to be excessively pedantic
here, but is it a problem in the cheatsheet exposition that 'p' is
implicitly used to refer to both an array of coefficients and the
length of that array?
Allin
2:47 a.m.
Am 20.03.2019 um 02:05 schrieb Allin Cottrell:
On Tue, 19 Mar 2019, Allin Cottrell wrote:
>
> for p = the degree of the polynomial.
Notation can be a bugger, and not wanting to be excessively pedantic
here, but is it a problem in the cheatsheet exposition that 'p' is
implicitly used to refer to both an array of coefficients and the length
of that array?
In principle yes and it could be changed in one go. However, there I
think the context is clear and one could say, the first p is in italics
and the second one in typewriter font, so not exactly the same.
cheers
sven
11:39 a.m.
On Wed, 20 Mar 2019, Sven Schreiber wrote:
Am 20.03.2019 um 02:05 schrieb Allin Cottrell:
> On Tue, 19 Mar 2019, Allin Cottrell wrote:
>>
>> for p = the degree of the polynomial.
>
> Notation can be a bugger, and not wanting to be excessively pedantic
> here, but is it a problem in the cheatsheet exposition that 'p' is
> implicitly used to refer to both an array of coefficients and the length
> of that array?
In principle yes and it could be changed in one go. However, there I
think the context is clear and one could say, the first p is in italics
and the second one in typewriter font, so not exactly the same.
I've tried a modification of the cheat sheet text -- please check that
I haven't messed things up!
Allin
5:41 p.m.
Am 20.03.2019 um 16:39 schrieb Allin Cottrell:
On Wed, 20 Mar 2019, Sven Schreiber wrote:
> Am 20.03.2019 um 02:05 schrieb Allin Cottrell:
>> On Tue, 19 Mar 2019, Allin Cottrell wrote:
>
>>>
>>> for p = the degree of the polynomial.
>>
>> Notation can be a bugger, and not wanting to be excessively pedantic
>> here, but is it a problem in the cheatsheet exposition that 'p' is
>> implicitly used to refer to both an array of coefficients and the length
>> of that array?
>
> In principle yes and it could be changed in one go. However, there I
> think the context is clear and one could say, the first p is in italics
> and the second one in typewriter font, so not exactly the same.
I've tried a modification of the cheat sheet text -- please check that I
haven't messed things up!
You write $r_k = \sum_{i=0}^k p_i q_{k-i}$ and I think that's basically
correct. Perhaps it's useful to clarify that within the sum it must also
hold $i \leq m$ and $k-i \leq n$ (equivalently $i \geq k-n$) because
otherwise the coefficients are zero; such that the sum index runs from
max(k-n, 0) to m, I believe.
cheers
sven
5:48 p.m.
On Wed, 20 Mar 2019, Sven Schreiber wrote:
Am 20.03.2019 um 16:39 schrieb Allin Cottrell:
> On Wed, 20 Mar 2019, Sven Schreiber wrote:
>
>> Am 20.03.2019 um 02:05 schrieb Allin Cottrell:
>>> On Tue, 19 Mar 2019, Allin Cottrell wrote:
>>
>>>>
>>>> for p = the degree of the polynomial.
>>>
>>> Notation can be a bugger, and not wanting to be excessively pedantic
>>> here, but is it a problem in the cheatsheet exposition that 'p' is
>>> implicitly used to refer to both an array of coefficients and the length
>>> of that array?
>>
>> In principle yes and it could be changed in one go. However, there I
>> think the context is clear and one could say, the first p is in italics
>> and the second one in typewriter font, so not exactly the same.
>
> I've tried a modification of the cheat sheet text -- please check that I
> haven't messed things up!
You write $r_k = \sum_{i=0}^k p_i q_{k-i}$ and I think that's basically
correct. Perhaps it's useful to clarify that within the sum it must also
hold $i \leq m$ and $k-i \leq n$ (equivalently $i \geq k-n$) because
otherwise the coefficients are zero; such that the sum index runs from
max(k-n, 0) to m, I believe.
Right, any coefficients beyond the degree of either of the two
polynomials are taken to be zero. Perhaps that should be explicit.
Jack?
Allin
2:28 a.m.
On Wed, 20 Mar 2019, Allin Cottrell wrote:
Right, any coefficients beyond the degree of either of the two
polynomials are taken to be zero. Perhaps that should be explicit.
Jack?
I don't think we have to be explicit on that; after all, that's the very
definition of order of a polynomial. IMO the text in its present form is
perfectly OK.
-------------------------------------------------------
Riccardo (Jack) Lucchetti
Dipartimento di Scienze Economiche e Sociali (DiSES)
Università Politecnica delle Marche
(formerly known as Università di Ancona)
r.lucchetti(a)univpm.it
http://www2.econ.univpm.it/servizi/hpp/lucchetti
-------------------------------------------------------
4:37 a.m.
Am 21.03.2019 um 07:28 schrieb Riccardo (Jack) Lucchetti:
On Wed, 20 Mar 2019, Allin Cottrell wrote:
> Right, any coefficients beyond the degree of either of the two
> polynomials are taken to be zero. Perhaps that should be explicit. Jack?
I don't think we have to be explicit on that; after all, that's the very
definition of order of a polynomial. IMO the text in its present form is
perfectly OK.
I agree the text is OK (present = git), but just to be clear while we're
at it: k-n will be negative for low k, and when for example p_{-1} is
not defined, it's not always totally obvious that it will also be
understood as zero, because sometimes people introduce tricky notation
with special meanings. IMO this is not 100% equivalent to the case of
p_{1000} which quite obviously is zero (most of the time).
cheers
sven
8:50 a.m.
On Thu, 21 Mar 2019, Sven Schreiber wrote:
Am 21.03.2019 um 07:28 schrieb Riccardo (Jack) Lucchetti:
> On Wed, 20 Mar 2019, Allin Cottrell wrote:
>
>> Right, any coefficients beyond the degree of either of the two
>> polynomials are taken to be zero. Perhaps that should be explicit. Jack?
>
> I don't think we have to be explicit on that; after all, that's the very
> definition of order of a polynomial. IMO the text in its present form is
> perfectly OK.
I agree the text is OK (present = git), but just to be clear while we're
at it: k-n will be negative for low k, and when for example p_{-1} is
not defined, it's not always totally obvious that it will also be
understood as zero [...]
Where does k-n arise? The r_k formula runs the p-index from 0 to k and
the q-index from k to 0, for each k in [0, m+n], so I don't see how
iteration could throw up a negative index.
Allin
10:53 a.m.
Am 21.03.2019 um 13:50 schrieb Allin Cottrell:
On Thu, 21 Mar 2019, Sven Schreiber wrote:
> I agree the text is OK (present = git), but just to be clear
while we're
> at it: k-n will be negative for low k, and when for example p_{-1} is
> not defined, it's not always totally obvious that it will also be
> understood as zero [...]
Where does k-n arise? The r_k formula runs the p-index from 0 to k and
the q-index from k to 0, for each k in [0, m+n], so I don't see how
iteration could throw up a negative index.
Yeah, you're right, I don't remember where I saw that. Seems I was lost
in notation...
cheers
sven
11:16 a.m.
Am 20.03.2019 um 01:49 schrieb Allin Cottrell:
On Tue, 19 Mar 2019, Sven Schreiber wrote:
>
> I wonder if this should be wrapped in a hansl function and added to the
> 'extra' addon, like this:
...
> As mentioned in the guide, the filter-based variant is indeed
about 30%
> faster in my examples.
The thread then diverged towards my "BTW" remark. So getting back to the
original question, should it go into 'extra'?
thanks
sven
11:52 a.m.
On Sat, 23 Mar 2019, Sven Schreiber wrote:
Am 20.03.2019 um 01:49 schrieb Allin Cottrell:
> On Tue, 19 Mar 2019, Sven Schreiber wrote:
>>
>> I wonder if this should be wrapped in a hansl function and added to the
>> 'extra' addon, like this:
...
>> As mentioned in the guide, the filter-based variant is indeed about 30%
>> faster in my examples.
The thread then diverged towards my "BTW" remark. So getting back to the
original question, should it go into 'extra'?
I don't have strong feelings either way. The "cheat sheet"
implementation of convolve is just a one-liner, which might suggest
that it's hardly worth adding a convolve function in its own right.
On the other hand the need for, and sizing of, the zero vector to be
appended to the first argument to filter() may not be transparent to
many users, so maybe it's worth hiding that.
Allin
2:22 p.m.
Am 24.03.2019 um 16:52 schrieb Allin Cottrell:
On Sat, 23 Mar 2019, Sven Schreiber wrote:
>
> The thread then diverged towards my "BTW" remark. So getting back to the
> original question, should it go into 'extra'?
I don't have strong feelings either way. The "cheat sheet"
implementation of convolve is just a one-liner, which might suggest that
it's hardly worth adding a convolve function in its own right.
On the other hand the need for, and sizing of, the zero vector to be
appended to the first argument to filter() may not be transparent to
many users, so maybe it's worth hiding that.
Right, I think this is indeed the case. Note that in the general case
you don't know whether p or q is the shorter vector, and by how much.
This already makes it difficult to keep it a one-liner.
I would have suggested a new optional argument for filter() to request
the zero-padding, but filter() already has three optional args, so I
think that would be too confusing.
At the very least the convolve.inp sample script should point to the
cheat sheet solution or perhaps include it. This is of course something
I can easily do myself.
And BTW, slightly OT, to make one-liners like "r = filter(p |
zeros(rows(q)-1, 1), q)" more economical -and other code as well-
wouldn't it be good if the column number argument of zeros() became
optional with a default of 1, such that zeros(rows(q)-1) would be
equivalent to zeros(rows(q)-1, 1)?
(And the same for: ones(), mnormal(), muniform(), and possibly also
mrandgen().)
thanks
sven
1883
days inactive
1888
days old
13 comments
3 participants
participants (3)
-
Allin Cottrell -
Riccardo (Jack) Lucchetti -
Sven Schreiber