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

Paul Nathan pnathan.software at gmail.com
Wed Jul 30 13:41:25 PDT 2014


Gregor,

I think the simple answer is that if your function needs to be broadly
extensible in the future and to have specialization, it needs to be
designed in the trait fashion, per the remarks earlier.



On Thu, Jul 24, 2014 at 5:46 PM, Gregor Cramer <remarcg at gmx.net> wrote:

>  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
>
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140730/04a69c28/attachment.html>


More information about the Rust-dev mailing list