Common ratio maths is incomplete about mp-units HOT 17 CLOSED

Ahh yes the ratio is mathematically equivilant but it is not the simplest form. Looking at the code of common_ratio_impl it is trying to calculate the rational gcd of two rational numbers in the form n1/d1 x 10^e1, n2/d2 x 10^e2. It currently does not do this correctly, it instead calculates the gcd of n1/d1 , n2/d2 and takes the minimum of the exponents, this is a common divisor but not the greatest common divisor. This leads to the unexpected consequence that for certain units which have a greatest common divisor equal to one of the ratios i.e some ratios of the form r, kr with k an integer not producing the 'correct' output when summed. e.g if you sum 1m and 1cm and got 1010mm instead of 101cm you would be surprised. Furthermore the larger numbers produce integer oveflows sooner.

from mp-units.

I'll take a look at this.

I believe the "missing" concepts header is require for gcc < 10 only and is contained the the "ranges" dependency:
https://github.com/mpusz/units/blob/master/doc/INSTALL.md

gcc >= 10 shoudn't need it

from mp-units.

OK, I have spent a (short) while looking at this. I am currently struggling to come to the same conclusion as you based on your godbolt example. These ratios can be non-trivial and "unintuitve".

The easiest way might be to study the attached Spreadsheet. (xlsx file -- why does github not support ods?)
ratio_check.xlsx

That shows, that both your suggested answer "6001 small" and the mpusz::units answer "30005 [1/3 x 10^-3] s" are "correct". They are the same. They are equivalent.

from mp-units.

@ConorWilliams I think this is open to interpretation. mpusz::ratios are designed to not have multiples of 10 in their numerator or denominator. It does that. You answer doesn't.

I understood your original report to say "the answer is wrong". But actually "they are alternative representations". We can debate all day which is better, but at best this is QoI.

Do we have an actual example which breaks? 1m + 1cm = 101cm

from mp-units.

Anther example 1in + 1yd != 37in. I'm sure the resultant fraction is correct (numerically) but the reason it's not triggering the downcasting to inches is because the gcd is not being calculated correctly. I leave it to you to decide weather [127/125 × 10⁻³] m is the 'correct' representaton.

from mp-units.

Thanks for the motivating example. It may well be that the gcd is part of the issue in that case, as you say. To be clear, I am not claiming that the std::min based common_ratio routine is "correct" (in isolated mathematical terms). I know it not to be.

However, as I mentioned earlier, and I haven't investigated this fully, I think there may well be some other issues to be considered.

• ratio is normalised
• type matching can be brittle already (that's why we normalize, but it's not a silver bullet).
• considering value and ratio together to find "a match" which suits the user.
• I am generally unconvinced that we will get the appropriate auto downcast in all situations anyway (there is not even such a thing as an authoritative unit to downcast to in some cases).
• how do we know that the user wants inches? maybe they want yards or lightyears... or multiples of King Arthur's big toe lengths (approx an inch?). If I definitely want inches I would do this: https://godbolt.org/z/Gx3NXh and I would only do it at the end of calculation, because before that: It doesn't matter, and that's the whole point of such a library.

Have you managed to compile the code?

If you drop your gcd routine in there. Does it solve the 37in testcase?

from mp-units.

I have tried to follow the tutorial but alas I am still missing headers (im new to conan), I discovered this problem whilst copying (greatest form of flattery!) your common_ratio implementation for my own unit lib code and the afformentioned gcd_frac function works as expected for all my above examples. Some thoughts on your points:

• nomalised ratio should make no difference to a correctly working gcd_frac like function. It may make a difference to the downcasting however, this is not the case in the ft-inch example where the gcd ratio has been computed as 127/125*10^-3 = 0.04 inches when it should have been one inch.
• not sure what you mean by this one.
• this is not possible at compile time which is required for type manipulation?
• true
• the user wants inches because thats a common divisor and will therefore cause no divisons (for integer types important) and more importantly the gcd and will result in the value having the minimum possible magnitude without divison which will help to supress integer overflow (39 < 925 in the inches example). Even if using quantity cast or assigning to known unit the temopraries will have these undesirable properties

from mp-units.

I have tried to follow the tutorial but alas I am still missing headers (im new to conan), I discovered this problem whilst copying (greatest form of flattery!) your common_ratio implementation for my own unit lib code and the afformentioned gcd_frac function works as expected for all my above examples.

Just for the record, I don't want to take false credit, for "my common_ratio code": This is not very accurate. I have only made some tiny contributions to this code base. I added exponents to ratio, that's why I answered.

You really need gcc10/trunk for this codebase. It will "just about" work with 9.2, but barely. So, OK when I get a chance, I will see if can adapt your gcd code, which definitely looks more mathematically complete, without causing havoc.

Some thoughts on your points:

* nomalised ratio should make no difference to a correctly working gcd_frac like function. It may make a difference to the downcasting however,  this is not the case in the ft-inch example where the gcd ratio has been computed as 127/125*10^-3 = 0.04 inches when it should have been one inch.

I haven't double checked, but are you sure? When I force downcast it to inches (godbolt above), it gives the correct answer?

* not sure what you mean by this one.

It's not super obvious how to decide that "2 types" are "the same". 2 / 4 x10^1 === 10/2 x10^0 ??? We have been fighting this effect in some of the many tests. Have a look at the "rather unnatural" way in which we have specified the "correct" answer in the tests. I would say (and did at the time): "It makes the tests pass" ;-)

* this is not possible at compile time which is required for type manipulation?

Indeed. And i haven't thought this through, but it worried me, in the above spreadsheet of mine that our two versions of the "ratio" only "cleanly cancelled down to the same value" when considered in the context of the runtime value of the quantity.

* the user wants inches because thats a common divisor and will therefore cause no divisons (for integer types important) and more importantly the gcd and will result in the value having the minimum possible magnitude without divison which will help to supress integer overflow (39 < 925 in the inches example). Even if using quantity cast or assigning to known unit the temopraries will have these undesirable properties

Larger values => Yes, agreed

Less divisions =-> Maybe, not 100% convinced. I have other concerns about exclusive integer use of the lib. Those may get more fully tested and potentially addressed. In principle it can work, but I am not sure it does at the moment.

from mp-units.

Thank you for your time, some good points in the last post that I unfortunatly don't have the answers to. I think the changes made should only be needed in the common_ratio_impl function so hopefully not too much havoc!

from mp-units.

@ConorWilliams Interesting update.

Merged in your code. Had to do a bunch of static casting arount signed/unsigned because that was throwing warnings and we are compiling with -Werror.

Now for Irony.....

It works..... and produces "37 in" without force quantity casting it, BUT! Only if I use quantities with a double representation, ie

auto small = 1.0q_in;
auto big = 1.0q_yd;

If I leave it with an int representation it throws a wall of errors which I currently do not understand. The only way I found this, was by staring at the screen and meditating for half an hour, and then making that exact change speculatively, Apparently that is a well proven debug technique.

If I were to guess I would say it's to do with that "runtime/compile time ratio +value cancelling", but that is a guess and it's going to be tricky to debug.

from mp-units.

That is indeed a very strange bug, I can think of no reason the quantity representation and the common ratio code should even be interacting, my only thought is running the output of gcd_frac through your ratio simplification code to make sure it's in the same form as all the other ratios.

I am happy the code gave 37 inches though!

from mp-units.

I haven't fully studied and understood your code.

How similar in principle is it to this, which was added recently and separately from common_ration, and is currently unusued: https://github.com/mpusz/units/blob/f618529451b84d613c138a8b7bd48ed04bd8b391/src/include/units/ratio.h#L82

I am not sure how efficient the above is against overflow of the numerator intermediate result, but in your opinion, is it "more correct" than the common_ratio_impl code? -- You clearly having spent much more time thinking about this particular problem.

from mp-units.

Thanks for handling this problem :-). I am really not the expert in maths and I am happy that you are eager to help me here. Said that I think that gcd is the way to go and this is how chrono works too. We should find the best way to implement it with our ratio type that takes exponent.

from mp-units.

Ok I've had a read of ratio_add_detail and think I understand it. If you where to apply this align exponents procedure to your ratios before calculating there gcd with your current formula it would give you the correct result (i.e the actual gcd). However, I do not recommend this procedure as it is very suseptable to integer overflow (i.e 1eV + 1J = 6.242e+18 ev).

I will outline how gcd_frac sidesteps this overflow problem:

Therefore we just need to solve . This can be done without overflow as follows:

The only hard bits here are the multiplication before the last modulo which can be done without overflow (gcdpow) through a standard recursive application of the above mod algebra identity (see mulmod). The exponential modulo operation, fortunatly this is a common cryptographic problem and can be solved again by repeated expansions of the above identity (see modpow).

from mp-units.

Also in responce to:

It's not super obvious how to decide that "2 types" are "the same". 2 / 4 x10^1 === 10/2 x10^0 ???

In my lib I put all ratios in standard form i.e 1.xxx 10^e to make them uniquely specified. To prevent this causing issues during multimplication/divison with overflow they must first be denormalised by removing all powers of ten from the num/den 's then muliplied (removing cross terms gcd first) then converted back to standard form.... maybe a bit much!

from mp-units.

Also in responce to:

It's not super obvious how to decide that "2 types" are "the same". 2 / 4 x10^1 === 10/2 x10^0 ???

In my lib I put all ratios in standard form i.e 1.xxx 10^e to make them uniquely specified. To prevent this causing issues during multimplication/divison with overflow they must first be denormalised by removing all powers of ten from the num/den 's then muliplied (removing cross terms gcd first) then converted back to standard form.... maybe a bit much!

We do something similar, see top of ratio.h

from mp-units.

will outline how gcd_frac sidesteps this overflow

Yes I saw your code was working hard to avoid this, but didn't spend time to understand the detail, so this is helpful for documentation, should we end up committing your code.

need to meditate more first.

from mp-units.