pallet_staking_reward_curve/
log.rs

1// This file is part of Substrate.
2
3// Copyright (C) Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: Apache-2.0
5
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// 	http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18/// Simple u32 power of 2 function - simply uses a bit shift
19macro_rules! pow2 {
20	($n:expr) => {
21		1_u32 << $n
22	};
23}
24
25/// Returns the k_th per_million taylor term for a log2 function
26fn taylor_term(k: u32, y_num: u128, y_den: u128) -> u32 {
27	let _2_div_ln_2: u128 = 2_885_390u128;
28
29	if k == 0 {
30		(_2_div_ln_2 * (y_num).pow(1) / (y_den).pow(1)).try_into().unwrap()
31	} else {
32		let mut res = _2_div_ln_2 * (y_num).pow(3) / (y_den).pow(3);
33		for _ in 1..k {
34			res = res * (y_num).pow(2) / (y_den).pow(2);
35		}
36		res /= 2 * k as u128 + 1;
37
38		res.try_into().unwrap()
39	}
40}
41
42/// Performs a log2 operation using a rational fraction
43///
44/// result = log2(p/q) where p/q is bound to [1, 1_000_000]
45/// Where:
46/// * q represents the numerator of the rational fraction input
47/// * p represents the denominator of the rational fraction input
48/// * result represents a per-million output of log2
49pub fn log2(p: u32, q: u32) -> u32 {
50	assert!(p >= q); // keep p/q bound to [1, inf)
51	assert!(p <= u32::MAX / 2);
52
53	// This restriction should not be mandatory. But function is only tested and used for this.
54	assert!(p <= 1_000_000);
55	assert!(q <= 1_000_000);
56
57	// log2(1) = 0
58	if p == q {
59		return 0
60	}
61
62	// find the power of 2 where q * 2^n <= p < q * 2^(n+1)
63	let mut n = 0u32;
64	while (p < pow2!(n) * q) || (p >= pow2!(n + 1) * q) {
65		n += 1;
66		assert!(n < 32); // cannot represent 2^32 in u32
67	}
68	assert!(p < pow2!(n + 1) * q);
69
70	let y_num: u32 = p - pow2!(n) * q;
71	let y_den: u32 = p + pow2!(n) * q;
72
73	// Loop through each Taylor series coefficient until it reaches 10^-6
74	let mut res = n * 1_000_000u32;
75	let mut k = 0;
76	loop {
77		let term = taylor_term(k, y_num.into(), y_den.into());
78		if term == 0 {
79			break
80		}
81
82		res += term;
83		k += 1;
84	}
85
86	res
87}
88
89#[test]
90fn test_log() {
91	let div = 1_000;
92	for p in 0..=div {
93		for q in 1..=p {
94			let p: u32 = (1_000_000 as u64 * p as u64 / div as u64).try_into().unwrap();
95			let q: u32 = (1_000_000 as u64 * q as u64 / div as u64).try_into().unwrap();
96
97			let res = -(log2(p, q) as i64);
98			let expected = ((q as f64 / p as f64).log(2.0) * 1_000_000 as f64).round() as i64;
99			assert!((res - expected).abs() <= 6);
100		}
101	}
102}
103
104#[test]
105#[should_panic]
106fn test_log_p_must_be_greater_than_q() {
107	let p: u32 = 1_000;
108	let q: u32 = 1_001;
109	let _ = log2(p, q);
110}
111
112#[test]
113#[should_panic]
114fn test_log_p_upper_bound() {
115	let p: u32 = 1_000_001;
116	let q: u32 = 1_000_000;
117	let _ = log2(p, q);
118}
119
120#[test]
121#[should_panic]
122fn test_log_q_limit() {
123	let p: u32 = 1_000_000;
124	let q: u32 = 0;
125	let _ = log2(p, q);
126}
127
128#[test]
129fn test_log_of_one_boundary() {
130	let p: u32 = 1_000_000;
131	let q: u32 = 1_000_000;
132	assert_eq!(log2(p, q), 0);
133}
134
135#[test]
136fn test_log_of_largest_input() {
137	let p: u32 = 1_000_000;
138	let q: u32 = 1;
139	let expected = 19_931_568;
140	let tolerance = 100;
141	assert!((log2(p, q) as i32 - expected as i32).abs() < tolerance);
142}
pallet_staking_reward_curve/log.rs

pallet_staking_reward_curve/
log.rs
