2

I have a complicated algorithm that calculates 3 values, $\text{Low} \lt \text{High} \lt \text{Total}$ as real values (actually double-precision floating point) and I need to approximate them as 3 integers ($\text{32-bit} \implies \text{value} \in \mathopen{[}0, 2^{32}-1\mathclose{]}$)

$$ \begin{align} \text{IntLow} & \approx \text{Low}\\ \text{IntTotal} & \approx \text{Total}\\ \text{IntCount} & \approx \text{High} - \text{Low}\\ \text{IntCount} + \text{IntLow} & \approx \text{High}\\ \end{align} $$

The integer values need to maintain the following relationships as closely as possible. For convenence, let $\text{IntHigh} ≝ \text{IntCount} + \text{IntLow}$ $$ \begin{align} \frac{\text{Low}}{\text{High}} & \approx \frac{\text{IntLow}}{\text{IntHigh}}\\[6pt] \frac{\text{Low}}{\text{Total}} & \approx \frac{\text{IntLow}}{\text{IntTotal}}\\[6pt] \frac{\text{High}}{\text{Total}} & \approx \frac{\text{IntHigh}}{\text{IntTotal}}\\[6pt] \frac{\text{High} - \text{Low}}{\text{Total}} & \approx \frac{\text{IntCount}}{\text{IntTotal}} \end{align} $$

How can this minimization problem best be solved?

Below is an explanation of my current approach.


My current approach is to iterate: $$ \begin{align} \text{IntLow} & ≔ \operatorname{floor}\left(\text{Low} \times \text{Multiplier}\right)\\ \text{IntCount} & ≔ \operatorname{floor}\left((\text{High} - \text{Low}) \times \text{Multiplier}\right)\\ \text{IntTotal} & ≔ \operatorname{floor}\left(\text{Total} \times \text{Multiplier}\right) \end{align} $$ and compute the sum of absolute differences between the fractions for a multiplier that is a positive power of two. Then I refine the best found multiplier by trying the two multipliers $(\text{multiplier} \times 2^{1/2^x})$ and $(\text{multiplier} \div 2^{1/2^x})$ for $x \in \mathopen{[}1, 32\mathclose{]}$ and update the best multiplier after each 'round' as appropriate. This works, but it requires a lot of floating point division, and it seems likely there is a better way than 'brute forcing' the bits of the multiplier.

Extrarius
  • 273
  • 1
    I did a few corrections to your MathJax coding; maybe that will tell you what to do with the rest. Note the difference between $32{-}bit$ and $32\text{-bit}$, not only in the lack of italics but also in that the hyphen looks like a hyphen. Using an asterisk for ordinary multiplication in MathJax or LaTeX or the like is like being an invited guest at a state dinner hosted by the Queen at Buckingham Palace and eating mashed potatoes by shoving your face into the plate when silverware is available. – Michael Hardy Dec 07 '16 at 20:40
  • 1
    Thank you for you corrections. I believe I have propagated them everywhere. – Extrarius Dec 20 '16 at 16:30

0 Answers0