Question

How do I make a method that takes methods as parameters for a convolution oh great and powerful @wio ?

Answer 1

First you create a simple function interface:
```
public interface Function<I, O> {
O call(I x);
}
```
You're going to have to hard code the functions, you can either define them as nested classes, define them in their own file, or define them through anonymous classes.

For example:
```
int sum(Function<int, int> f, int start, int end) {
int result = 0;
for (var i = start; i <= end; i++) {
result += f.call(i);
}
return result;
}
```
Now if you wanted to call this function with anonymous classes you would do:
```
sum(new Function<int, int> {
int call(int x) {
return x * x;
}
}, 5, 20);
```
This would should return \(\sum_{k=5}^{20} x^2\)

Answer 2

I put `var i`, but it should be `int i`.
Also, result should be \(\sum_{i=5}^{20}i^2\)

Answer 3

I don't really have any experience with anonymous classes so I'm not really sure what I'm doing with them. The only thing I can guess at is that I need to implement that interface to the anonymous class.

Also, was this line supposed to be
```
int sum(Function<Integer, Integer> f, int start, int end) {
```

Answer 4

Yeah, if `int` doesn't work use `Integer`

Answer 5

For convolution, you likely want something like:
```
int convolution(Function<Integer, Integer> f,
Function<Integer, Integer> g,
Iterator<Integer[]> i) {
int result = 0;
for (Integer[] pair : i) {
result += f(pair[0]) * g(pair[1]);
}
return result;
}
```
I've made it somewhat generalized.

Answer 6

```
class FactorIterator implements Iterator<Integer[]> {
private int product;
private int sqrt;
private int factor;

public FactorIterator(int product) {
this.product = product;
this.sqrt = Math.floor(Math.sqrt(product)); // Calculate once and store
this.factor = 1;
}

boolean hasNext() {
return (this.factor1 < this.sqrt);
}

Integer[] next() {
Integer[] factors = { this.factor, this.product / this.factor };
this.factor++;
while (hasNext() && this.product % this.factor != 0) {
this.factor++;
}
return factors;
}
}
```

Answer 7

This is how I'm thinking you would implement the iterator for finding integer factors.

Answer 8

Okay, `hasNext` should probably use `factor <= sqrt`

Answer 9

Wait, the problem with my iterator though is that it'll only iterate through unique factors.
Hmmm

Answer 10

I'm playing around with it, but I feel like I got lost somewhere along the way and I haven't been able to get anything to run yet. I'm pretty much totally clueless, can you tell me what's bad.

```
public static interface Function<I, O> {
O call(I x);
}

public class FunctionClass implements Function<Integer, Integer> {
@Override
public Integer call(Integer x) {
return null;
}
}

public static int sum(Function<Integer, Integer> f, int start, int end) {
int result = 0;
for (int i = start; i <= end; i++) {
result += f.call(i);
}
return result;
}

public static void main(String... args) throws Exception {
Function<Integer, Integer> f = new Function<Integer,Integer>();
sum(f, 5, 20);
}
```

Answer 11

This is all within a class file

Answer 12

Ok

Answer 13

Why does `FunctionClass` return `null`?

Answer 14

Oh that's not really something I had gotten to yet, it should probably return like a number or something, I haven't dealt with that yet.

Answer 15

right now assume it returns 1; what I'm really concerned with is this line
```
Function<Integer, Integer> f = new Function<Integer,Integer>();
```
It's not working out for me.

Answer 16

Shouldn't it be `f = new FunctionClass()`?

Answer 17

If you want to do `new Function` then you're doing an anonymous function and you have to implement all of its methods.

Answer 18

Can you possibly draw a picture or diagram of this whole concept, like showing me a class with an arrow implementing an interface and where my method-with-methods-parameters and where my methods-as-parameters are?

Answer 19

You can't instantiate an interface, you have to implement it. Anonymous classes just let's you create an implementation on the fly.

Answer 20

In your case, `FunctionClass` is the implementation.

Answer 21

I see, so I need a new class for every method-parameter then?

Answer 22

An interface is just a list of methods, it's used to guarantee a class will have those methods.

Answer 23

Right, so I guess the confusion I'm having is does the interface contain the name of the method that will take methods as parameters or does it contain the name of the methods I will be using as parameters?

Answer 24

If you can just give me a working version of this code I could probably wiggle it and figure it out that way but right now I'm just struggling to piece it together so I'm not really seeing how it works, there are too many new things here for me.

Answer 25

Ok ok I think I am starting to get it. I need some time to play with it, but I have this other working. I'll hold off on asking questions for a while and try to figure this out.

```
public static interface Foo { // this is the interface declaration
public void doThing(int a, int b);
}

public static class Bar implements Foo { // Bar is an implementing class
public void doThing(int a, int b) {
System.out.println(a * b);
}
}

public static class Bee implements Foo {
public void doThing(int a, int b) {
System.out.println(a + b);
}
}

public static void test(Foo foo, int n, int m) { // the method accepts an
// interface
foo.doThing(n, m); // and invokes it, the implementing class' print()
// will be
}

public static void main(String... args) {
test(new Bar(), 5, 6);
test(new Bee(), 5, 6);
}
```

Answer 26

But if you have any advice on how to make this better (if you have the patience with this haha) tell me so I can try to mull it over and figure it out when I get back.

Answer 27

```
class Main {

public static interface Function<I, O> {
O call(I x);
}

public static class SquaringFunction implements Function<Integer, Integer> {
@Override
public Integer call(Integer x) {
return x * x;
}
}

public static int sum(Function<Integer, Integer> f, int start, int end) {
int result = 0;
for (int i = start; i <= end; i++) {
result += f.call(i);
}
return result;
}

public static void main(String... args) throws Exception {
Function<Integer, Integer> f = new SquaringFunction();
int result = sum(f, 5, 20);
System.out.println(result);
}
}
```

Answer 28

Anonymous class version:
```
class Main {

public static interface Function<I, O> {
O call(I x);
}

public static int sum(Function<Integer, Integer> f, int start, int end) {
int result = 0;
for (int i = start; i <= end; i++) {
result += f.call(i);
}
return result;
}

public static void main(String... args) throws Exception {
Function<Integer, Integer> f = new Function<Integer, Integer>() {
@Override
public Integer call(Integer x) {
return x * x;
}
};
int result = sum(f, 5, 20);
System.out.println(result);
}
}
```

Answer 29

Awesome thanks man, this is really going to help me understand anonymous classes. Just out of curiosity do you ever deal with lambdas in Java or is that pretty uncommon since it's Java 8?

Answer 30

It's very new thing, so they're just a matter of convenience.

Answer 31

Ok I see how it works, I think the thing that was throwing me off is I didn't quite understand that I had to use a new class for each method and I also didn't understand the anonymous class, but this makes much more sense now.

To be honest, this method seems kind of obnoxious, is this the kind of thing Haskell would be better at doing? I mean you know I like playing with math a lot, do you know of any languages that might be better suited for me?

Answer 32

```
import java.util.Iterator;

class Main {

static class UniqueFactorIterator implements Iterator<Integer[]>, Iterable<Integer[]>{
private int product;
private int factor;

public UniqueFactorIterator(int product) {
this.product = product;
this.factor = 1;
}

public boolean hasNext() {
return (this.factor * this.factor <= this.product);
}

public Integer[] next() {
Integer[] factors = { this.factor, this.product / this.factor };
this.factor++;
while (hasNext() && this.product % this.factor != 0) {
this.factor++;
}
return factors;
}

public Iterator<Integer[]> iterator() {
return this;
}
}

static class FactorIterator extends UniqueFactorIterator {
UniqueFactorIterator iter;
Integer[] last;
public FactorIterator(int product) {
super(product);
}

@Override
public boolean hasNext() {
return (super.hasNext() || (last != null && last[0] != last[1]));
}

@Override
public Integer[] next() {
Integer[] result;
if (last == null) {
last = super.next();
result = last;
} else {
result = new Integer[]{last[1], last[0]};
last = null;
}
return result;
}
}


public static void main(String... args) throws Exception {
FactorIterator i = new FactorIterator(16);
for (Integer[] pair : i) {
System.out.print(pair[0]);
System.out.print(", ");
System.out.println(pair[1]);
}
}
}
```

This will output
```
1, 16
16, 1
2, 8
8, 2
4, 4
```

Answer 33

By the way, this type of convolution seems a bit weird.

Answer 34

I thought convolutions were along the lines of: \[
\sum_{k=0}^{b}f(x)g(b-x)
\]

Answer 35

Yeah, so the way convolutions come up is when you multiply two series together and want to reexpress their product as a single series. You need a formula for the coefficients. That particular convolution works great for this:

\[\left( \sum_{n=0}^\infty f(n)x^n \right) \left( \sum_{m=0}^\infty g(m)x^m \right) = \sum_{k=0}^\infty h(k) x^k \] You can combine the two series just like you can combine two integrals and then you will get a \(x^{n+m}\) term that you can make a substitution \(n+m=k\) and from there you can see the convolution.

The Dirichlet convolution is similar, except the series are now Dirichlet series, of which the Riemann zeta function is a particular instance.

\[\left( \sum_{n=0}^\infty \frac{f(n)}{n^x} \right) \left( \sum_{m=0}^\infty \frac{g(m)}{m^x} \right) = \sum_{k=0}^\infty \frac{h(k)}{k^x} \]

So deriving this is also similar except that the terms that will be the same and require us to combine the coefficients is \(\frac{1}{(nm)^x}\) so we need the requirement that \(n*m=k\).

So the thing about that the Dirichlet convolution is closed under multiplicative functions, which is a weird and nice property.

Answer 36

I sorta left out a lot of details, but essentially when I showed you this earlier:
```
public static int[] getDivisorArray(int number) {
int[] divArray = new int[number];
for (int n = 0; n < number; n++)
divArray[n] = 0;
for (int i = 1; i < number; i++)
for (int j = 1; j < number; j++)
if (i * j < number) // Dirichlet convolution
divArray[i * j]++;
return divArray;
}
```
It is just like multiplying two Dirichlet series together that have the simplest possible coefficients \(f(n)=1\) and \(g(n)=1\) in that i and j are the two summation indices of these series before hand and to get the new coefficients we have to multiplying (or adding if we wanted the power series) will get us the new one.

So this will return all the values of the divisor function in order:
```
0 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 2 6 2 6 4 4 2 8 3 4 4 6 2
```
So we see that this is spitting out the number of divisors according to the tau function (which is only defined for 1 and greater)

a fun thing about this is the index of every value here with 2 is prime. Also every odd number has a perfect square index. There are other multiplicative functions to play with as well, I'm just sorta having fun and thinking it might end up being useful for project euler possibly in the future.

Answer 37

Here @dan815 try it on www.repl.it or some online compiler. It'll print out the total divisors for a bunch of numbers.
```
class Main {
public static interface Function {
int call(int x);
}

public static class UnitFunction implements Function {
@Override
public int call(int x) {
return 1;
}
}

// Dirichlet Convolution
public static int convolve(Function f,
Function g, int n) {
int result = 0;
for (int i = 1; i <= n; i++)
// Only divisors of n
if (((float) n) / i == (float) (n / i))
result += f.call(i) * g.call(n / i);
return result;
}

public static void main(String[] args) {
Function u = new UnitFunction();
for(int n = 1; n< 20; n++)
System.out.format("T(%d) = %d%n", n, convolve(u,u,n));
}
}
```

Answer 38

Here fixed it up
```
class Main{
public static interface Function {
int call(int x);
}

public static Function convolve(final Function f, final Function g) {
Function h = new Function() {
@Override
public int call(int n) {
int result = 0;
for (int i = 1; i <= n; i++)
// Only divisors of n
if (((float) n) / i == (float) (n / i))
result += f.call(i) * g.call(n / i);
return result;
}
};
return h;
}

public static class UnitFunction implements Function {
@Override
public int call(int x) {
return 1;
}
}

public static void main(String... args) throws Exception {
Function u = new UnitFunction();
Function tau = convolve(u, u);
for (int n = 1; n < 20; n++)
System.out.format("T(%d) = %d%n", n, tau.call(n));
}
}
```

Answer 39

You could consider using a nested class instead of returning an anonymous class.
```
class Main{
public static interface Function {
int call(int x);
}

public static class ConvolveFunction implements Function {
private Function f;
private Function g;

public ConvolveFunction(Function f, Function g) {
this.f = f;
this.g = g;
}

@Override
public int call(int n) {
int result = 0;
for (int i = 1; i <= n; i++)
// Only divisors of n
if (((float) n) / i == (float) (n / i))
result += f.call(i) * g.call(n / i);
return result;
}
}

public static class UnitFunction implements Function {
@Override
public int call(int x) {
return 1;
}
}

public static void main(String... args) throws Exception {
Function u = new UnitFunction();
Function tau = new ConvolveFunction(u, u);
for (int n = 1; n < 20; n++)
System.out.format("T(%d) = %d%n", n, tau.call(n));
}
}
```

Your anonymous class relies on two functions that are passed as parameters. Those parameters had to be declared as `final` due to the fact that Java doesn't create closures. You'd store them as class members if you didn't want the functions to be final.

Functions typically aren't mutable anyway, so I suppose it is not a big deal.

Answer 40

Ahhh thanks, I was kind of bothered by it since I do plan on using this sort of pattern in the future for other things which might not do so well to have final, but like you said for this particular instance it wasn't much of a problem.