Computes cumulative OR (from the highest index to the lowest) on the n (from n-1 to 0) first elements of the array. In this method it's assumed that there are no bits set in the array after the n-th element. The result of the function is an array looking like this: 11..1100..0. After i steps of the loop in j-th element there is `or` of all elements data[j:j+2^i]. To compute the step i+1 we need to
(data: Node, n: u64)
| 192 | // After i steps of the loop in j-th element there is `or` of all elements data[j:j+2^i]. |
| 193 | // To compute the step i+1 we need to shift the array by 2^i elements and `or` it to the current. |
| 194 | fn cumulative_or(data: Node, n: u64) -> Result<Node> { |
| 195 | let (shape, sc) = match data.get_type()? { |
| 196 | Type::Array(shape, sc) => (shape, sc), |
| 197 | _ => return Err(runtime_error!("Expected array type")), |
| 198 | }; |
| 199 | let g = data.get_graph(); |
| 200 | let pow2 = n.next_power_of_two(); |
| 201 | let k = pow2.trailing_zeros(); |
| 202 | let mut pad_shape = shape.clone(); |
| 203 | // pad_shape[0] = 2^k-(shape[0] - n) |
| 204 | if n > shape[0] { |
| 205 | pad_shape[0] = n - shape[0] + pow2; |
| 206 | } else { |
| 207 | let extra_bits = shape[0] - n; |
| 208 | if pow2 > extra_bits { |
| 209 | pad_shape[0] = pow2 - extra_bits; |
| 210 | } else { |
| 211 | pad_shape[0] = 0; |
| 212 | } |
| 213 | } |
| 214 | let data = if pad_shape[0] != 0 { |
| 215 | let pad = g.zeros(array_type(pad_shape, sc))?; |
| 216 | g.concatenate(vec![data, pad], 0)? |
| 217 | } else { |
| 218 | data |
| 219 | }; |
| 220 | let data = data.add(g.ones(scalar_type(BIT))?)?; |
| 221 | let mut suffix_or = data; |
| 222 | for i in 0..k { |
| 223 | let shift = 2_i64.pow(i); |
| 224 | suffix_or = g.multiply( |
| 225 | suffix_or.get_slice(vec![SliceElement::SubArray(None, Some(-shift), None)])?, |
| 226 | suffix_or.get_slice(vec![SliceElement::SubArray(Some(shift), None, None)])?, |
| 227 | )?; |
| 228 | } |
| 229 | suffix_or.add(g.ones(scalar_type(BIT))?) |
| 230 | } |
| 231 | |
| 232 | // Works only on positive integers from (0; 2^denominator_cap_2k). |
| 233 | // For the initial approximation of 1/n, we use would like to compute x that is different form 1/n no more than twice. |
no test coverage detected