19 ms·

Convolution is digit-based multiplication, so why not start with that? 100101 * 23 = 2302323. If you defer the carry over to the end, the digit-based steps we

by sriku 6y ago

Convolution is digit-based multiplication, so why not start with that? 100101 * 23 = 2302323. If you defer the carry over to the end, the digit-based steps we do is convolution. That said, giving lots of examples like those in the article is useful. Next up looking at multiplying two polynomials in a single variable. Edit: changed digit-wise to digit-based to make it clear that I'm not asking to multiply corresponding digits.

jaggirs 6y ago
Woha This is cool. It literally is the same, if you use base-infinity digits (not binary, or decimal, but infinity-ary?). How do you multiply two polynomials with a single variable?
- rualca 6y ago
  > This is cool I don't agree the example has anything to do with convolution. The example is explained with plain old primary school multiplication. 100101 * 23 = (100000+100+1)*23 = 2300000+2300+23 There isn't any fantastic property, only cherry-picked number which works as decimal left-shifts. Convolution is not a number. Convolution is an operator that outputs a function.
  - Tomminn 6y ago
    The parents point is that when you do the primary school multiplication algorithm, you are actually performing a discrete convolution.
    - rualca 6y ago
      You really aren't. That assertion is like commenting that elementary arithmetics is discrete signal analysis because 1+1=2, which happens to match the amplitude of a resonance of a normalized vibration mode. It isn't. It's a cherry picked example. A broken clock which coincides with the current time.
      - enriquto 6y ago
        > It isn't. It's a cherry picked example. A broken clock which coincides with the current time. No. It really is. Look at the example. Nobody can convince you if you are already set up against that idea, but look at what happens when you multiply two polyomials P(z)Q(z). You obtain a polynomial whose coefficients are the convolution of those of P and Q. Now, a decimal number is "just" a polynomial evaluated on z=10. And a vibrating string is "just" a polynomial evaluated at z=exp(it). The algebra of convolutions and products is exactly the same in all three cases.
  - jaggirs 6y ago
    The only cherry picking is that the numbers need to be small enough that the decimal digit does not overflow (4 times 2 is fine but 4 times 3 is not). A more 'convolved' example: 121 * 23 = 2783 If you use hex instead it also works for larger digits like 0x42 * 0x31 = 0xCA2 = [12, 10, 2] So, if you convert to a digit of a large enough base you can do any multiplication with just a convolution and no carry.
    - rualca 6y ago
      > The only cherry picking is that the numbers need to be small enough that the decimal digit does not overflow Aren't you restating my point? > So, if you convert to a digit of a large enough base you can do any multiplication with just a convolution and no carry. There is no convolution at all. There's only a cherry-picked example of how plain old multiplication feels similar to a sliding dot product, which for some reason some people confuse with convolution. This is not helpful, and only adds to the confusion already expressed.
      - antonfire 6y ago
        The first few Google results for "sliding dot product" basically describe it as a convolution with the domain of one of the functions reversed. (Note as far as whether or not to reverse one of the functions, multiplication in base-b agrees with "convolution" and not with "sliding dot product".) Elsewhere in the thread you seem to be suggesting that convolution is a way to convert between a frequency domain and a time domain, which suggests that you are confusing convolution with Fourier transforms. There's some nice relationships between these things, so they are often discussed together, but even then a single convolution happens either entirely in the time domain or entirely in the frequency domain, not as a way of going from one of those domains to the other. E.g. the pointwise product (in the frequency domain) of the Fourier transforms of two functions is the Fourier transform of the convolution (in the time domain) of those two functions. There's also a chance you are focused on the difference between functions with a discrete domain and functions with a continuous domain. The term "convolution" is often applied to both.
      - AdhemarVandamme 6y ago
  - sriku 6y ago
    (sum_i ai x^i)(sum_j bj x^j) when you expand that, the coefficient of x^k is the sum of aibj such that i+j=k which is discrete convolution. Set x=10 and you're dealing with decimal representation of numbers.
    - rualca 6y ago
      > Set x=10 and (...) ...and you no longer have a function, only the image of a function at a specific point of its domain. Convolutions are functions, not functions evaluated at a specific, and cherry-picked point.
- sriku 6y ago
  Ref reply below - https://news.ycombinator.com/item?id=25195046 https://news.ycombinator.com/item?id=25195046
- antonfire 6y ago
  A polynomial with a single variable is more or less what you would mean by "use base-infinity digits" in the first place. Roughly, in base 10, the number represented by the sequence of digits d_0, d_1, ..., d_n is d_0 + d_1 * 10 + d_2 * 10^2 + ... + d_n * 10^n. In "base infinity", the "number" represented by the sequence of digits d_0, d_1, ..., d_n is the polynomial d_0 + d_1 * x + d_2 * x^2 + ... + d_n * x^n. Multiplying these "numbers" (polynomials) is like decimal multiplication, except the digits can be arbitrarily high and you do no carrying at all.
Tomminn 6y ago
This example is great, hope you don't mind if I spell it out how your impulse weight f(d) and impulse response functions g(d) are functions over d (each associated with 10^d): f(0) = 1 g(0) = 3 f*g(0) = 3 f(1) = 0 g(1) = 2 f*g(1) = 2 f(2) = 1 f*g(2) = 3 f(3) = 0 f*g(3) = 2 f(4) = 0 f*g(4) = 0 f(5) = 1 f*g(5) = 3 f*g(6) = 2 You can see how when there is an impulse weight "x" in digit space entry d, the impulse response "3x" comes at d, and the impulse response "2x" comes at d+1. Note how f and g can be anything and it convolution (f * g) is still their multiplication (except for the obvious rub when f*g(d) is greater than 9, so you need to add a rule about that).
rualca 6y ago
> Convolution is digit-based multiplication, It really isn't, and I don't understand the level of confusion that leads to this assertion. Is it because the elementary school algorithm for multiplication decomposes a number in it's decimal places before multiplying? > so why not start with that? Because it would be wrong, misguided, and it would fail to demonstrate the logic behind convolution. Let's take a step back and think about it. Convolution is mainly and primarily used as a convenient way to covert signals between time and frequency domain, within the scope of Fourier transforms. Who in their right mind associates elementary school multiplications with conversions to/from the frequency domain?
- sriku 6y ago
  Ref comment https://news.ycombinator.com/item?id=25195046 https://news.ycombinator.com/item?id=25195046 about this. Further to that, if you replace x with complex variable z^-1, you get what is usually called the z-transform. Set z to a specific complex root of unity exp(i2pi/N) and you have your discrete FT. One of the algorithms for multiplying large arbitrary precision numbers uses multiplication of the discrete transform of the digit sequences (in a different base) iirc. Same thing.
  - sriku 6y ago
    Correction: exp(i2πm/N) .. which gives you Fourier coefficients at m.
- sriku 6y ago
  > Convolution is mainly and primarily used as a convenient way to covert signals between time and frequency domain Btw that isn't true. That operation is called a "transform" as in "Fourier transform" and "z-transform". The property of those transforms is that element-wise multiplication in one domain becomes convolution in the transformed domain. Element-wise multiplication in "time" domain is convolution in "frequency" domain and element-wise multiplication in "frequency" domain is convolution in "time" domain.

by sriku 6y ago

jaggirs 6y ago

Woha This is cool. It literally is the same, if you use base-infinity digits (not binary, or decimal, but infinity-ary?). How do you multiply two polynomials with a single variable?

rualca 6y ago
> This is cool I don't agree the example has anything to do with convolution. The example is explained with plain old primary school multiplication. 100101 * 23 = (100000+100+1)*23 = 2300000+2300+23 There isn't any fantastic property, only cherry-picked number which works as decimal left-shifts. Convolution is not a number. Convolution is an operator that outputs a function.
- Tomminn 6y ago
  The parents point is that when you do the primary school multiplication algorithm, you are actually performing a discrete convolution.
  - rualca 6y ago
    You really aren't. That assertion is like commenting that elementary arithmetics is discrete signal analysis because 1+1=2, which happens to match the amplitude of a resonance of a normalized vibration mode. It isn't. It's a cherry picked example. A broken clock which coincides with the current time.
    - enriquto 6y ago
      > It isn't. It's a cherry picked example. A broken clock which coincides with the current time. No. It really is. Look at the example. Nobody can convince you if you are already set up against that idea, but look at what happens when you multiply two polyomials P(z)Q(z). You obtain a polynomial whose coefficients are the convolution of those of P and Q. Now, a decimal number is "just" a polynomial evaluated on z=10. And a vibrating string is "just" a polynomial evaluated at z=exp(it). The algebra of convolutions and products is exactly the same in all three cases.
- jaggirs 6y ago
  The only cherry picking is that the numbers need to be small enough that the decimal digit does not overflow (4 times 2 is fine but 4 times 3 is not). A more 'convolved' example: 121 * 23 = 2783 If you use hex instead it also works for larger digits like 0x42 * 0x31 = 0xCA2 = [12, 10, 2] So, if you convert to a digit of a large enough base you can do any multiplication with just a convolution and no carry.
  - rualca 6y ago
    > The only cherry picking is that the numbers need to be small enough that the decimal digit does not overflow Aren't you restating my point? > So, if you convert to a digit of a large enough base you can do any multiplication with just a convolution and no carry. There is no convolution at all. There's only a cherry-picked example of how plain old multiplication feels similar to a sliding dot product, which for some reason some people confuse with convolution. This is not helpful, and only adds to the confusion already expressed.
    - antonfire 6y ago
      The first few Google results for "sliding dot product" basically describe it as a convolution with the domain of one of the functions reversed. (Note as far as whether or not to reverse one of the functions, multiplication in base-b agrees with "convolution" and not with "sliding dot product".) Elsewhere in the thread you seem to be suggesting that convolution is a way to convert between a frequency domain and a time domain, which suggests that you are confusing convolution with Fourier transforms. There's some nice relationships between these things, so they are often discussed together, but even then a single convolution happens either entirely in the time domain or entirely in the frequency domain, not as a way of going from one of those domains to the other. E.g. the pointwise product (in the frequency domain) of the Fourier transforms of two functions is the Fourier transform of the convolution (in the time domain) of those two functions. There's also a chance you are focused on the difference between functions with a discrete domain and functions with a continuous domain. The term "convolution" is often applied to both.
    - AdhemarVandamme 6y ago
- sriku 6y ago
  (sum_i ai x^i)(sum_j bj x^j) when you expand that, the coefficient of x^k is the sum of aibj such that i+j=k which is discrete convolution. Set x=10 and you're dealing with decimal representation of numbers.
  - rualca 6y ago
    > Set x=10 and (...) ...and you no longer have a function, only the image of a function at a specific point of its domain. Convolutions are functions, not functions evaluated at a specific, and cherry-picked point.
sriku 6y ago
Ref reply below - https://news.ycombinator.com/item?id=25195046 https://news.ycombinator.com/item?id=25195046
antonfire 6y ago
A polynomial with a single variable is more or less what you would mean by "use base-infinity digits" in the first place. Roughly, in base 10, the number represented by the sequence of digits d_0, d_1, ..., d_n is d_0 + d_1 * 10 + d_2 * 10^2 + ... + d_n * 10^n. In "base infinity", the "number" represented by the sequence of digits d_0, d_1, ..., d_n is the polynomial d_0 + d_1 * x + d_2 * x^2 + ... + d_n * x^n. Multiplying these "numbers" (polynomials) is like decimal multiplication, except the digits can be arbitrarily high and you do no carrying at all.

Tomminn 6y ago

This example is great, hope you don't mind if I spell it out how your impulse weight f(d) and impulse response functions g(d) are functions over d (each associated with 10^d): f(0) = 1 g(0) = 3 f*g(0) = 3 f(1) = 0 g(1) = 2 f*g(1) = 2 f(2) = 1 f*g(2) = 3 f(3) = 0 f*g(3) = 2 f(4) = 0 f*g(4) = 0 f(5) = 1 f*g(5) = 3 f*g(6) = 2 You can see how when there is an impulse weight "x" in digit space entry d, the impulse response "3x" comes at d, and the impulse response "2x" comes at d+1. Note how f and g can be anything and it convolution (f * g) is still their multiplication (except for the obvious rub when f*g(d) is greater than 9, so you need to add a rule about that).

rualca 6y ago

> Convolution is digit-based multiplication, It really isn't, and I don't understand the level of confusion that leads to this assertion. Is it because the elementary school algorithm for multiplication decomposes a number in it's decimal places before multiplying? > so why not start with that? Because it would be wrong, misguided, and it would fail to demonstrate the logic behind convolution. Let's take a step back and think about it. Convolution is mainly and primarily used as a convenient way to covert signals between time and frequency domain, within the scope of Fourier transforms. Who in their right mind associates elementary school multiplications with conversions to/from the frequency domain?

sriku 6y ago
Ref comment https://news.ycombinator.com/item?id=25195046 https://news.ycombinator.com/item?id=25195046 about this. Further to that, if you replace x with complex variable z^-1, you get what is usually called the z-transform. Set z to a specific complex root of unity exp(i2pi/N) and you have your discrete FT. One of the algorithms for multiplying large arbitrary precision numbers uses multiplication of the discrete transform of the digit sequences (in a different base) iirc. Same thing.
- sriku 6y ago
  Correction: exp(i2πm/N) .. which gives you Fourier coefficients at m.
sriku 6y ago
> Convolution is mainly and primarily used as a convenient way to covert signals between time and frequency domain Btw that isn't true. That operation is called a "transform" as in "Fourier transform" and "z-transform". The property of those transforms is that element-wise multiplication in one domain becomes convolution in the transformed domain. Element-wise multiplication in "time" domain is convolution in "frequency" domain and element-wise multiplication in "frequency" domain is convolution in "time" domain.