# Algorithm as Equation

I have developed an algorithm that counts the number of times a particular block (within a 2D Matrix) crosses zero. Here's an example:

Matrix = {
1, 2, -1, -0.1,
4, 3, -6, -12,
12, 2, -5, 19,
8, -1, 12, -9,
}


Then the matrix is split into sub-matrices (or blocks)

B1 = {
1, 2,
4, 3
}

B2 = {
-1, -0.1,
-6, -12,
}

...,

...,

...


An example summing up each of the blocks is:

Ex=∑n|x[n]|2

Find the signum value of each element within the block (will return "1", "-1", "0") respectively.

If the signum value returns -1 then count increments by 1.

This will repeat until the there is no blocks, however, will only produce 1 value per block.

I am looking for a way to put all this process into an equation so I can demonstrate this rather than having to explain the processes in written text everytime. Is this possible?

-
I've added the "algorithms" tag, but I'm not entirely sure it's a good choice. Someone else please re-tag if you know of an appropriate one. –  Antonio Vargas Nov 21 '12 at 18:14
Suppose your data is $x_1,...x_n$, then $C(x) = |\{i | i = 0,...,n-1, \ \text{sgn} x_i \neq \text{sgn} x_{i+1} \} |$. –  copper.hat Nov 21 '12 at 18:18
I don't understand at all. What do you mean by "block" - a polygon in the plane? What do you mean "crosses zero"? –  gt6989b Nov 21 '12 at 18:19
@gt6989b Basically, a block as in I have a 2D matrix containing 1D blocks of data. By "crosses zero" I mean simply the number of negative values, like in the example, there is 3 negative values so there ZC = 3; –  Phorce Nov 21 '12 at 18:23
I still don't understand what you mean by 1D and 2D blocks. I presume that $0,-1,0$ is not a crossing either. –  copper.hat Nov 21 '12 at 18:46

Suppose your data is $x_1,...,x_n$, then let $C(x) = | \{i | i=0,...,n-1,\ \mathbb{sgn}\, x_i \neq \mathbb{sgn}\, x_{i+1} \} |$.

Unfortunately the above is wrong when $x$ contains zeros. The fix is cumbersome: $$C(x) = | \{i | i < n,\, \exists j >i,\, j\leq n,\, |\mathbb{sgn}\, x_i -\mathbb{sgn}\, x_j|=2, \, x_{i+1} = \cdots = x_{j-1} = 0 \} |$$ This presumes that $\mathbb{sgn}\, 0 = 0$.

-
Hey thanks, I just don't understand this bit: "𝕤𝕘𝕟xi≠𝕤𝕘𝕟xi+1" sign(x[i]) which would give either 1, or -1... But why do you have the NOT EQUAL symbol x[i]+1? –  Phorce Nov 21 '12 at 18:40
To find zero crossings, you find the sign of each value and look for when the sign changes, hence the $\neq$. However, there is an error in the formula above when dealing with zero values. I will fix it or delete it when I get a chance to look at it. –  copper.hat Nov 21 '12 at 18:44
Thank you :)! Let me have a think about this, and see if I can come up with an equation based upon yours. –  Phorce Nov 21 '12 at 18:45
I think @Mohsen's suggestion of removing zeros first is the simplest fix. –  copper.hat Nov 21 '12 at 18:48
but why = 2? I understand the math just not the 2 ha! Is there any test values that I can use to test this? –  Phorce Nov 21 '12 at 19:03

If data is $B=(b_1, b_2, \ldots, b_n)$ and all numbers are nonzero then the number of zero cross-overs will be

$N(B)=\sum_{i=1}^{n-1} \frac{1}{2}|\mathrm{sgn} b_i - \mathrm{sgn} b_{i+1} |$

If you have zeros in the data, you should remove them before applying this, otherwise a closed-form equation would be too cumbersome.

-
Thank you. But, I don't understand why there is no if statement in the equation (if value[x] == -1)) etc.. Or am I missing the point? –  Phorce Nov 21 '12 at 18:32
The if is implied in $\frac{1}{2}|\mathrm{sgn} x_i - \mathrm{sgn} x_{i+1} |$. If two consecutive values have similar sign (both positive or negative) this value will be zero, otherwise it will be 1. So summation over this will give you the number of zero cross-overs. –  Mohsen Nosratinia Nov 21 '12 at 18:47
Ok, I understand it.. Just the "−" between the two sgn .. are you representing the values with this line? –  Phorce Nov 21 '12 at 19:50