# On the Optimal Calculation of the Rice Coding Parameter
## 3 General Selection of the Golomb Parameter for Rice Coding
### Algorithm for Finding the Optimal Parameter  
In Algorithm 1, we propose a search heuristic for finding the optimal Rice parameter starting from our approximation values. It starts by comparing the bit-lengths of the Rice coding of the input sequence when the parameters are \(\lfloor S(\mathbf{n})\rfloor\) and \(\lceil S(\mathbf{n})\rceil\). If the total bit-length resulting from Rice coding using the first parameter (\(\lfloor S(\mathbf{n})\rfloor\)) is smaller than when the second value (\(\lceil S(\mathbf{n})\rceil\)) is used, the search continues using values smaller than \(\lfloor S(\mathbf{n})\rfloor\) until the bit-length starts increasing again. If the total bit-length caused by the first parameter is greater than when the second value is used, the search continues using values greater than \(\lceil S(\mathbf{n})\rceil\) until the bit-length starts increasing again. If the total bit-lengths are the same, an optimum has been reached. The function FindBestRiceParameter--defined between Lines 17 and 37 in Algorithm 1--is our main function in the heuristic. It shall be invoked with the input data sequence, \(n\), and the number of elements in the input data sequence, \(N\). The subroutine PrecalculateRiceQ--defined between Lines 1 and 12 in Algorithm 1--has a complexity of \(O(L_{max}\cdot N)\), since each one of the \(n_{i}\in\mathbf{n}\) input data values is considered, and for each one of them, the value of \(Q(r)\) is calculated for all potential values of \(r\), i.e., \(0\leq r\leq L_{\max}\). The operator \(a>>b\) is the right-shift-bit operator or, in other words, the integer division by a power of two. The subroutine CalculateF--defined between Lines 13 and 16 in Algorithm 1--has a complexity of \(O(1)\), since it is a mathematical evaluation with no iterative calls on the input data. The loop defined between Lines 30 and 35--within the subroutine FindBestRiceParameter--has only a complexity of \(O(L_{\max})\), since the subroutine is evaluating the function \(f\) with all the possibles values of \(r\) in constant time. As a consequence, the complexity of the subroutine FindBestRiceParameter is defined by the invocation of the subroutine PrecalculateRiceQ in Line 18, which has a higher complexity than the aforementioned loop. The subroutine FindBestRiceParameter has a complexity of \(O(L_{max}\cdot N)\). ```
1:functionPrecalculateRiceQ(\(n\))
2:\(Q\leftarrow\mathbf{0}\)
3:for\(n_{i}\in n\)do
4:\(r\gets 0\)
5:while\(r\leq L(n_{i})\)do\(\triangleright\) see (10) for \(L(x)\)
6:\(Q(r)\gets Q(r)+n_{i}\)
7:\(n_{i}\gets n_{i}>>1\)
8:\(r\gets r+1\)
9:endwhile
10:endfor
11:return\(Q\)
12:endfunction
13:functionCalculateF(\(r,Q,N\))
14:\(f\gets N\cdot(r+2)+Q(r)\)
15:return\(f\)
16:endfunction
17:functionFindBestRiceParameter(\(n\),\(N\))
18:\(Q\leftarrow\textsc{PrecalculateRiceQ}(\mathbf{n})\)
19:\(S\leftarrow\log_{2}\left((\ln 2)\cdot Q(0)/N\right)\)
20:\(r^{\prime}\leftarrow\lfloor S\rfloor\)
21:\(f^{\prime}\leftarrow\textsc{CalculateF}(r^{\prime},Q,N)\)
22:\(r^{\prime\prime}\leftarrow\lceil S\rceil\)
23:\(f^{\prime\prime}\leftarrow\textsc{CalculateF}(r^{\prime\prime},Q,N)\)
24:\(t\leftarrow-1\)
25:if\(f^{\prime}<f^{\prime\prime}\)then
26:\(t\leftarrow-1\)
27:SwapVariables(\(f^{\prime},f^{\prime\prime}\))
28:SwapVariables(\(f^{\prime},f^{\prime\prime}\))
29:endif
30:while\(f^{\prime}>f^{\prime\prime}\)do
31:\(r^{\prime}\gets r^{\prime\prime}\)
32:\(f^{\prime}\gets f^{\prime\prime}\)
33:\(r^{\prime\prime}\leftarrow r^{\prime\prime}+t\)
34:\(f^{\prime\prime}\leftarrow\textsc{CalculateF}(r^{\prime\prime},Q,N)\)
35:endwhile
36:return\(r^{\prime}\)
37:endfunction
```  
**Algorithm 1** Online calculation of the Rice-code with complexity \(O(L_{max}\cdot N)\). In practice, as will be presented later in Section 4.4, the approximation described in Section 3.2 (used as a starting search point in our algorithm) provides the optimal solution.