I have an image with the size 5575x9440
and I'm implementing a modified version of the algorithm used in this paper on it, but because the code performance is low right now, I have divided the image to 52628
submatrices of the size 25x40 (1000 pixels)
and my first experiments show that some lines of code that are marked in the following picture as yellow are not needed at all (meaning that the 2 and 3 degree polynomials always have at least one real positive root) and so there's no need to check it. (Deleting these ten lines will make the code 3rd times faster and I have other plans to accelerate the code further)
Because the code is slow right now, I cannot experiment all of these 52628
matrices and I have to choose a sample size and choose some random matrices to try. But how to calculate the sample size?
What comes below is just to show my effort. And if you're not willing to read it, there's no necessity.
I've already done as follows
This is for lines 121 and 122. The approach for the other two lines (134 and 135) is the same.
We want to test the following hypothesis.
Hypothesis: the line 121, 122 will not be run even one time for the whole image.
Hypothesis(scientifically): We can be 95% or 99% (confidence level) sure that those lines will be run just for 0.25% pixels (confidence interval) of the image.
Up to know I have tried this way:
First of all we have a random variable X = two lines of code that can have just two values: they will run (1) or they will not run(0). So the random variable will have the Bernoulli distribution
For each pixel, this experiment is done 62271
times and so in each submatrix, it will be done 62271000
times independently. So the random variable X = Number of times that the 2 lines are run that its value can be an integer number in the range $[0,62271000]$ is the sum of a huge number (62271000
) of bernoulli distributed variables
and so X will have a normal distribution according to the Central limit theorem so the random variable Z:
$$Z=\frac{X-np}{\sqrt{npq}}$$
Edit: (Based on the discussion between me and @Wiley in the comments) I should say that from the theoretic concepts of my model, I know that $\Delta>0$ for 2d and 3d polynomials. So the roots are real but it is their sign that determines whether the highlighted cod is needed or not
For 2D Polynomials: there are 4 cases
if there's at least one positive root, the highlighted code is not needed ($p=\frac{3}{4}$)
if all of the roots are negative, the highlighted code is needed. ($q=\frac{1}{4}$)
For 3D Polynomials: there are 8 cases
if there's at least one positive root, the highlighted code is not needed ($p=\frac{7}{8}$)
if all of the roots are negative, the highlighted code is needed. ($q=\frac{1}{8}$)
will have a Standard normal distribution
So for the 3d polynomial we have: $p=\frac{7}{8}\;,q=\frac{1}{8}$ and also $n = 62271000$, so we will have:
$$Z = \frac{X-54487125}{5219}\qquad 0\le X\le 62271000\Rightarrow -10440\le Z\le 1491$$
But from now on, I thinking I'm making some mistakes.
Our confidence interval is 0.25% of pixels
$$0.25\times 0.01\times 5575\times 9440 = 131570$$
meaning that the number of pixels that do not fit our hypothesis should be less than 131570
If we assume that these pixels are distributed homogeneously across the whole image, then the number of pixels in each submatrix that do not fit our hypothesis should be less than:
$$\frac{131570}{52628}=2.5$$
so $0\le X\le 155677.5\Rightarrow -10440\le Z\le -10410$
so our confidence interval is $-10410-(-10440)=30$
and our confidence level is 95% or 99%, means that the probability that $Z$ lies in the above range should be 0.95
or 0.99
.
$$p(Z)=N(0,1)=\frac{1}{\sqrt{2\pi}}\exp(-\frac{z^2}{2})$$
$$p(-10440\le Z\le -10410)=\frac{1}{\sqrt{2\pi}} \int_{-10440}^{-10410}\exp(-\frac{z^2}{2})\,dz = 0.95\; \text{or}\; 0.99$$
Then if we consider 52628
matrices as a stochastic process as a collection of 52628
(population) random variables with standard normal distribution
, how many members of this process should be experimented (sample size)?
Code lines that did not run: 2
and those lines areroot=0;end;
. Because the if statement is never true. (meaning that the 2d/3d polynomials always have at least 1 positive root). Now I say because the code is written for polynomials of $\Delta>0$, which have real roots, the are two possibilities. For a 3d polynomial 1- at least one of the roots is positive ($p=\frac{7}{8}$) the code will not run 2-all of the roots are negative ($q=\frac{1}{8}$) the code will run. And for a 2d polynomial 1- at least one of the roots is $\endgroup$