1use std::os::unix::thread;
 2
 3use rand::{thread_rng, Rng};
 4
 5fn decomposer(mut value: u64, q: u64, d: usize, logb: u64) -> Vec<u64> {
 6    let b = 1u64 << logb;
 7    let full_mask = b - 1u64;
 8    let bby2 = b >> 1;
 9
10    if value >= (q >> 1) {
11        value = !(q - value) + 1;
12    }
13
14    // let mut carry = 0;
15    // let mut out = Vec::with_capacity(d);
16    // for _ in 0..d {
17    //     let k_i = carry + (value & full_mask);
18    //     value = (value) >> logb;
19    //     let go = thread_rng().gen_bool(1.0 / 2.0);
20    //     if k_i > bby2 || (k_i == bby2 && ((value & 1) == 1)) {
21    //         // if (k_i == bby2 && ((value & 1) == 1)) {
22    //         //     println!("AA");
23    //         // }
24    //         out.push(q - (b - k_i));
25    //         carry = 1;
26    //     } else {
27    //         // if (k_i == bby2) {
28    //         //     println!("BB");
29    //         // }
30    //         out.push(k_i);
31    //         carry = 0;
32    //     }
33    // }
34    // println!("Last carry {carry}");
35    // return out;
36
37    let mut out = Vec::with_capacity(d);
38    for _ in 0..d {
39        let k_i = value & full_mask;
40        value = (value - k_i) >> logb;
41
42        if k_i > bby2 || (k_i == bby2 && ((value & 1) == 1)) {
43            // if (k_i == bby2 && ((value & 1) == 1)) {
44            //     println!("AA");
45            // }
46            out.push(q - (b - k_i));
47            value += 1;
48        } else {
49            // if (k_i == bby2) {
50            //     println!("BB");
51            // }
52            out.push(k_i);
53        }
54    }
55
56    return out;
57}
58
59fn recompose(limbs: &[u64], q: u64, logb: u64) -> u64 {
60    let mut out = 0;
61    limbs.iter().enumerate().for_each(|(i, l)| {
62        let a = 1u128 << (logb * (i as u64));
63        let a = ((a * (*l as u128)) % (q as u128)) as u64;
64        out = (out + a) % q;
65    });
66    out % q
67}
68
69fn main() {
70    // let mut v = Vec::with_capacity(10);
71    // v[0] = 1;
72    // println!("Hello, world!");
73
74    let mut rng = thread_rng();
75
76    let q = 36028797018820609u64;
77    let logb = 11;
78    let d = 5;
79
80    for _ in 0..100000 {
81        let value = rng.gen_range(0..q);
82        let limbs = decomposer(value, q, d, logb);
83        // println!("{:?}", &limbs);
84        let value_back = recompose(&limbs, q, logb);
85        assert_eq!(value, value_back)
86    }
87}