CODEWITHSUNDEEP
rust
Syntactic Fructose
Syntactic Fructose

Reputation: 20076

Convert vector of single integers into vector of single binary values

If I have a vector that represents some arbitrarily big numbers, big_v, I want to be able to convert this vector into a vector that holds the binary representation of big_v as well in order to implement a division algorithm. So say 

let big_v = vec![1,3,9];        // 139
let big_binary_v = func(big_v); // 10001011

big_binary_v's value would be the equivalent of [1,0,0,0,1,0,1,1].

This trick is that I could implement this easy if it weren't for the fact that the vector can represent an arbitrarily large integer , if not I could simply do binary(100) + binary(30) + binary(9). In the case that you have a number like 100000000000000001 however, you can't compute binary(100000000000000000) + binary(1). Is there any trick to convert this vector to binary without using size dependent operations?

Upvotes: 1

Views: 1009

Answers (1)

Veedrac
Veedrac

Reputation: 60137

The most obvious way is to generate some abstract operations.

fn add_binary_fixed(left: &mut Vec<u8>, right: u8);
fn multiply_binary_fixed(binary_value: &mut Vec<u8>, by: u8);

Then one can do

let mut binary_value = vec![0];
for decimal_digit in decimal_value {
    multiply(binary_value, 10);
    add(binary_value, decimal_digit);
}
binary_value

If one uses traits and proper types, this can generalize to any (bounded, natural numbered) base conversion:

fn convert(value: &LargeInteger, base: u8) -> LargeInteger {
    let mut output = LargeInteger::new(base);
    for digit in value {
        output.multiply(base);
        output.add(digit);
    }
    output
}

Upvotes: 2

Related Questions