PerThing: from_rational and mul odd behaviour

[ggwpez]

PS probably fixed by #13660

A benchmarking failure in paritytech/polkadot#6780 prompted an investigation of the arithmetics of PerThing.

There are two observations:

1. The mathematical sentence $\lfloor {Amount \over Denom} * Denom \rfloor <= Amount$ always holds.
   Now implementing this with Perquintill:

assert!(Perquintill::from_rational(amount, denom).unwrap().mul_floor(denom) <= amount);

This is not the case for these numbers:

#[test]
fn regress() {
	let amount = 218461045528156970819068829320184091938_u128;
	let denom = 282042398685736967680636164088585662015_u128;
	let approx_amount = Perquintill::from_rational_with_rounding(amount, denom, Rounding::Down)
		.unwrap().mul_floor(denom);

	assert!(approx_amount <= amount, "approx: {}, amount: {}", approx_amount, amount);
}

So it sometimes overshoots although it should round Down.

2. One problem seems to already be in the from_rational, since it rounds Up instead of Down. Wolfram Alpha output.

#[test]
fn regress() {
	let amount = 218461045528156970819068829320184091938_u128;
	let denom = 282042398685736967680636164088585662015_u128;
	let parts = Perquintill::from_rational_with_rounding(amount, denom, Rounding::Down)
		.unwrap().deconstruct();
	
	assert_eq!(parts, 774568102335475778_u64); // Fails with 774568102335475779
}

Extended tests to check these requirements.

Test 1

/// Test that this is never true:
/// from_rational_with_rounding(amount, denom, Rounding::Down) * denom > amount
#[test]
fn brute_force() {
	use f128::f128;
	use rand::{Rng, SeedableRng};
	use rayon::prelude::*;
	use sp_arithmetic::{Perquintill, Rounding};
	use sp_runtime::PerThing;

	(0..320).into_par_iter().for_each(|i| {
		let mut rng = rand::rngs::SmallRng::seed_from_u64(i);

		for _ in 0..10_000_000 {
			let amount: u128 = rng.gen::<u128>().saturating_add(1);
			let denom: u128 = rng.gen::<u128>().saturating_add(amount);

			let approx_ratio =
				Perquintill::from_rational_with_rounding(amount, denom, Rounding::Down)
					.expect(format!("{:?} / {}", amount, denom).as_str());
			let approx_amount = approx_ratio.mul_floor(denom);

			if approx_amount > amount {
				panic!(
					"TOO LARGE amount: {:?}, denom: {:?}, approx_amount: {:?}, diff: {:?}",
					amount,
					denom,
					approx_amount,
					approx_amount - amount,
				);
			}
		}
	});
}

Test 2

/// Test that the generated parts are correct.
#[test]
fn brute_force_amount_check() {
	new_test_ext().execute_with(|| {
		use f128::f128;
		use num_traits::{float::Float, ToPrimitive};
		use rand::{Rng, SeedableRng};
		use rayon::prelude::*;
		use sp_arithmetic::{Perquintill, Rounding};
		use sp_runtime::PerThing;

		(0..320).into_par_iter().for_each(|i| {
			let mut rng = rand::rngs::SmallRng::seed_from_u64(i);

			for _ in 0..10_000_000 {
				let amount: u128 = rng.gen::<u128>().saturating_add(1);
				let denom: u128 = rng.gen::<u128>().saturating_add(amount);

				let perfect_ratio = f128::from(amount) / f128::from(denom);
				let perfect_parts =
					(f128::from(Perquintill::ACCURACY) * perfect_ratio).floor().to_u128().unwrap();

				let approx_ratio =
					Perquintill::from_rational_with_rounding(amount, denom, Rounding::Down)
						.expect(format!("{:?} / {}", amount, denom).as_str());
				let approx_parts = approx_ratio.clone().deconstruct();

				if approx_parts != perfect_parts as u64 {
					panic!(
						"WRONG PARTS amount: {:?}, denom: {:?}, perfect_parts: {:?}, approx_parts: {:?}",
						amount, denom, perfect_parts, approx_parts
					);
				}
			}
		});
	});
}

[gavofyork]

fixed in #13660