4
$\begingroup$

I am trying to write a simple algorithm given below in mathematical notation. I wrote the formula up to a certain point, but I have no idea of restrictions. For example, I used the NULL statement even though it was not "else". It also needs a "break" statement or equivalent.

    var thr = 0.5;
    var M = 100;
    var sum = 0;
    var T = 0;

    for i 0 to G
    {
      sum = sum + i;
      if sum/M >= thr then
      {
        T = i;
        break;
      }
    }

  return T;

My math notations; I defined "sum" in equation as follows. $$sum = \sum_{j=0}^{i}j$$

(Eq.1)$$T = \sum_{i=0}^{G}f={ \begin{cases} i & \frac{\sum_{j=0}^{i}j}{M}\geq thr\\ \mathrm{NULL} & \text{otherwise} \end{cases}}$$ (Eq.2)$$T = \sum_{i=0,f\neq \mathrm{NULL}}^{G}f={ \begin{cases} i & \frac{\sum_{j=0}^{i}j}{M}\geq thr\\ \mathrm{NULL} & \text{otherwise} \end{cases}}$$

Thank you very much for your help already.

$\endgroup$
4
  • $\begingroup$ What is the value you wish to get out? $\endgroup$ Jul 27 '18 at 4:02
  • $\begingroup$ I want to get the value of the "i" that provides the condition. This is actually the P-tile algorithm. I use histogram information for this, but I've assigned constant variables to simplify the syntax. $\endgroup$ Jul 27 '18 at 4:10
  • $\begingroup$ what is G ? ${}$ $\endgroup$
    – mercio
    Jul 27 '18 at 7:37
  • $\begingroup$ G can be selected as a number greater than 10. That is, it's big enough to provide the "if" condition. $\endgroup$ Jul 27 '18 at 22:21
3
$\begingroup$

The idea here is that $T$ is equal to $i$, where $i$ is the first index in the loop for which $\verb|sum|\,/M \ge \verb|thr|$. This can be written in a formula as follows: $$ T = \begin{cases}0 &\tfrac1M\textstyle\sum_{j=0}^Gj<\verb|thr|\\\min\{i\mid i\in \{0,1,\dots,G\},\tfrac1M\textstyle\sum_{j=0}^ij\ge \verb|thr|\} & \text{Otherwise} \end{cases} $$ So you take the set of $i$ for which the loop would have stopped by the $i^\text{th}$ iteration, and declare $T$ to be the smallest (minimum) of this set.

$\endgroup$
4
  • $\begingroup$ Thank you very much, Mike. $\endgroup$ Jul 27 '18 at 4:37
  • 1
    $\begingroup$ @AbdullahELEN By the way, see my edit, I originally forgot about what would happen if the loop ended before the sum got large enough. $\endgroup$ Jul 27 '18 at 4:41
  • $\begingroup$ It's exactly what I wanted. Thank you again :) $\endgroup$ Jul 27 '18 at 4:47
  • $\begingroup$ I think we have a little problem. $T$ needs to be equal to $i$. As a result, the function must return $i$ value. Can i define it as follows? $\displaystyle \operatorname*{argmin}_i \{i|i\in \{0,1,\dots,G\},\tfrac1M\textstyle\sum_{j=0}^ij\ge \verb|thr|\}$ $\endgroup$ Jul 29 '18 at 1:27
1
$\begingroup$

You need to think about what the code is doing, not just translate the code. Wehn you write $$sum = \sum_{j=0}^{i}i$$ there is a small error that the iteration variable is $j$ so you should write $$sum = \sum_{j=0}^{i}j$$ More importantly, $sum$ is changing through the computation, so it would be better to write $$sum(i) = \sum_{j=0}^{i}j$$ then you should perform the sum and write $$sum(i)=\frac 12i(i+1)$$ Then $T$ is the $i$ for which $sum$ exceeds $M\cdot thr$. Some analysis will show that $$T=\left\lceil\frac 12(-1+\sqrt{1+8\cdot M\cdot thr}) \right \rceil$$ which is much more useful for someone trying to understand your code. This last shows a way to get the result without iteration as well.

$\endgroup$
6
  • $\begingroup$ First of all thank you for your quick response. Oh yes. I wrote i instead of j and am going to fix it immediately. However, the "sum" statement does not need to be stored in stages. You can see this in the algorithm. I could express this mathematically. $\endgroup$ Jul 27 '18 at 4:21
  • $\begingroup$ My point is that you are trying to find the $i$ where the sum exceeds $M\cdot thr$. That is the first thing you should say-it is the spec for the algorithm. Then you don't compute sum all the way up to $G$, which just needs to be some large number. You compute it in stages and compare at each stage. Whether you store it or not is not important, the important thing is the value as a function of $i$. Writing it as a sum shows how you do it, writing it as $\frac 12i(i+1)$ shows what it is. $\endgroup$ Jul 27 '18 at 4:29
  • $\begingroup$ Yes. If you look at "if conditional", you can see the "break" statement there. For this reason, the loop does not operate until G. $\endgroup$ Jul 27 '18 at 4:36
  • $\begingroup$ Yes, I understood that. You asked about expressing the algorithm mathematically but you continue to talk about how the code works. The important thing is to say what value of $T$ is returned based on the input parameters. Mike Earnest's expression is very close to your code. I think it is much less useful to a reader. $\endgroup$ Jul 27 '18 at 4:47
  • $\begingroup$ You're right. Not everybody has coding knowledge. For this reason, I should have written with a clearer expression. $\endgroup$ Jul 27 '18 at 4:53
1
$\begingroup$

Your code is iterating $i$ from $0$ to $G$ and cumulatively incrementing the $\text{sum}$ by that iterator, breaking when $\text{sum}/M\geq \text{thr}$ (or $\text{sum}\geq M\times\text{thr}$ when rounding is not an issue ). Only when breaking is $T$ set to the iterator, otherwise it is left at zero.

Since $\sum_{i=0}^n i =\tfrac{n\,(n+1)}2$ , and the values of $M$ and $\text{thr}$ are hard coded constants: $100$ and $0.5$, that code should result in

$$\begin{align}T & =\begin{cases} 0 &:& {G\,(G+1)}< 100\\ \min\{t\in\{0..G\}: t(t+1)\geqslant 100\} &:&\text{otherwise} \end{cases} \\ &= \begin{cases} 0 &:& G<10\\ 10 &:& G\geq 10\end{cases}\end{align}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.