[rust-dev] std::num::pow() is inadequate / language concepts

Gregor Cramer remarcg at gmx.net
Thu Jul 24 15:46:26 PDT 2014


Hello Rust folk!

I am new to Rust, and I have doubts concerning current language concepts.

One example: in module ::std::num function pow() is defined:

pub fn pow<T: One + Mul<T, T>>(mut base: T, mut exp: uint) -> T {
    if exp == 1 { base }
    else {
        let mut acc = one::<T>();
        while exp > 0 {
            if (exp & 1) == 1 {
                acc = acc * base;
            }
            base = base * base;
            exp = exp >> 1;
        }
        acc
    }
}

In general this implementation is ok, but not really usable with BigInt. Of
course, the call ':.std::num::pow(a, 1000)', 'a' is a BigInt, works. But this
implementation is not adequate for big integers. Firstly, too many memory
allocations during the computation (a specialized version can avoid these
memory allocations), secondly, for big integers a specialized function for
squaring (base * base) has to be used, because squaring can be done quite
more efficient than multiplication (with big integers). So this function is much
too slow and has to be overloaded, but:

1. Overloading is not supported (even the archaic C++ is providing this).

2. The footprint 'base: T' is not 100% suitable, for big integers the function
definition
     fn pow(base: &BigInt, mut exp: uint) -> BigInt
would be more appropriate, because the argument 'base' needs not to be
modified (or reassigned), and a call by reference (avoiding a superfluous
memory allocation) is more efficient in this case.

Of cource, a specialized version of pow() could be implemented in trait
BigInt, but this is only a workaround. And if a user only knows
::std::num::pow(), he will use an inappropriate implementation without
being aware of this.

Probably in this case it might be a solution  to move pow() into a trait, but
I'm speaking about a general problem. Rust 1.0 will be released, and someone
is developing a new module for version 1.1. But some of the functions in 1.0
are inadequate for the new module, how to solve this without changing the API
in 1.1? I think that function overloading may  help in some cases, but the
problem with inappropriate footprints remains. In my opinion this
thing with the footprints (reference or not if the real type is unknown -
that's why the concept with 'const' in C++ exists) is a conceptual design
issue, but probably I do not yet fully understand Rust.

BTW: the functions next_power_of_two(), and checked_next_power_of_two()
are only defined for primitives (trait Primitive), but should also be 
applicable for big integers, I think .

C heers,
Gregor
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140725/43e6317c/attachment.html>


More information about the Rust-dev mailing list