num_base_digits special case pow2

[Phaiax]

    #[test]
    fn num_base_digits_pow2() {
        use ::ll::base::num_base_digits;
        let cases = [
            ("10", 2, 4), // 0b 1010
            ("15", 2, 4), // 0b 1111
            ("16", 2, 5), // 0b10000
            ("1023", 2, 10), // 0b 1111111111
            ("1024", 2, 11), // 0b10000000000
            ("341", 4, 5), // 4»11111
            ("5461", 4, 7), // 4»1111111
            ("16383", 4, 7), // 4» 3333333
            ("16384", 4, 8), // 4»10000000
            ("65535", 4, 8), // 4»33333333
            ("299593", 8, 7), // 8»1111111 // 8**0 + 8**1 + 8**2 + 8**3 + 8**4 + 8**5 + 8**6
            ("299594", 8, 7), // 8»1111112
            ("2097151", 8, 7), // 8» 7777777
            ("2097152", 8, 8), // 8»10000000
            ("268435455", 16, 7), // 0x fffffff
            ("268435456", 16, 8), // 0x10000000
            ("13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084095", 2, 512), // 512 bits with value 1 -> 1 Limb
            ("13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096", 2, 513), // 513 bits -> 2 Limbs
        ];
        for &(s, base, digits) in cases.iter() {
            let i : Int = s.parse().unwrap();
            unsafe {
                println!("{:?} in base {} should need {} digits", s, base, digits);
                assert_eq!(digits,
                           num_base_digits(i.limbs(), i.abs_size(), base));
            }
        }
    }

fails with

"15" in base 2 should need 4 digits
"16" in base 2 should need 5 digits
"1023" in base 2 should need 10 digits
"1024" in base 2 should need 11 digits
"341" in base 4 should need 5 digits
"5461" in base 4 should need 7 digits
"16383" in base 4 should need 7 digits
"16384" in base 4 should need 8 digits
"65535" in base 4 should need 8 digits
"299593" in base 8 should need 7 digits
thread 'int::test::num_base_digits_pow2' panicked at 'assertion failed: `(left == right)` (left: `7`, right: `21`)', src/int.rs:3680

[Phaiax]

        let bits_per_digit = BASES.get_unchecked(base as usize).big_base.0 as usize;
         // doing an actual division here is much slower than this
        (total_bits + bits_per_digit - 1) >> bits_per_digit.trailing_zeros()

I do not get how the optimization should have worked. The .trailing_zeros() is doubled since it is done already in build.rs

    // Powers of two use a different path, so re-use the big_base field to store
    // the number of bits required to store a digit in the base.
    if base.is_power_of_two() {
        big_base = base.trailing_zeros() as usize;
    }

The other thing. For base = 8, the correct math would be int(total_bits/3). I don't know if it is possible to reduce different divisions (/3, /4, /5, /6, /7 that are not just the power of two divisions /2 /4 /8 ..). into one single shift statement.

[Phaiax]

I guess the error was to think that if the base is a power of two, the divisor is also power of two.