tools: fix integer scaling for metis/scotch

[hhirtz]

The idea is that we have weights

• in some [min; max] range,
• whose sum is S

and we want to scale them so

1. they fit into some integer type,
2. the output sum is below INTMAX
3. the output has no zeroes

basically we apply an affine function "y=scale*x+offset" where scale and offset depend on the max output value M:

     (M-1) * x + max - M*min
y = -------------------------
           max - min

y=1 for x=min and y=M for x=max

M is set so that the sum of all "y" is INTMAX (N is the number of weights):

     (max - min) * INTMAX + sum(x) - max * N
M = -----------------------------------------
               sum(x) - min * N

[codecov[bot]]

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Comparison is base (feb049a) 43.16% compared to head (3ad5b30) 43.04%. Report is 8 commits behind head on master.

:exclamation: Current head 3ad5b30 differs from pull request most recent head f037b8a. Consider uploading reports for the commit f037b8a to get more accurate results

Additional details and impacted files

```diff @@ Coverage Diff @@ ## master #298 +/- ## ========================================== - Coverage 43.16% 43.04% -0.13% ========================================== Files 52 52 Lines 8805 8788 -17 ========================================== - Hits 3801 3783 -18 - Misses 5004 5005 +1 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[cedricchevalier19]

M = \frac{(max - min) \times INTMAX + sum(x) - max \times N}{sum(x) - min \times N}

Be careful : $(max - min) \times INTMAX$ or $max \times N$ are likely to overflow if these computations are not done in floating point arithmetic.

[hhirtz]

scale and offset are computed using f64s exclusively, then weights are scaled with a fused multiply-add and then converted to the output integer type.

Opened a new issue for the clippy error: #299

[hhirtz]

There was indeed a possible overflow, in the computation of the criterion sums. I changed it to a compensated floating-point sum.

I also changed the way weights are scaled, min_input is set to 0 now, so that the ratios between weights are kept more or less the same as they were originally. For example, if all weights are close to some big number (eg [INTMAX-3, INTMAX-2, INTMAX-1]), it makes more sense to make them all equal than to "zoom in" to something like [1, INTMAX/3, 2/3*INTMAX]). Otherwise it won't represent the original weights faithfully.

Maybe there is a known way to move the inputs into integer range while keeping ratios.