checked_powd takes exponentially long time to complete about rust-decimal HOT 6 CLOSED

The use case is actually exposing a function for users to call. If users put in a huge exponent, they may not expect the program to be running for 100 seconds and will think the program has hung. An error would be a much better solution in my case.

Thus, I'll limit the max exponent for users. That would make it more foolproof.

On your side I'd suggest a note on the API saying that it may take a long time to run if the exponent is large, as it may not be completely expected.

Thanks!

from rust-decimal.

The problematic code in this case is in checked_powu where it does this:

                // Square self once and make an infinite sized iterator of the square.
                let iter = core::iter::repeat(squared);

                // We then take half of the exponent to create a finite iterator and then multiply those together.
                let mut product = Decimal::ONE;
                for x in iter.take((exp >> 1) as usize) {
                    match product.checked_mul(x) {
                        Some(r) => product = r,
                        None => return None,
                    };
                }

This is effectively looping 73864470 times - which in this case results in sub-optimal performance.

As a more simplistic example, if we did 3 ^ 5 this algorithm effectively:

• Squares 3 - so 9.
• Creates an iterator of 9's and takes 2 of those elements
• Then multiplies by that amount - e.g. 1 * 9 * 9 = 81
• Because the exponent is odd, it does one more 81 * 3 = 243

The squaring first is supposed to save cycles however it doesn't save enough in this case! An optimization could be for larger numbers is to square twice (or three times), for example, which would cut down the number of iterations substantially.

I don't think it is actually a huge lift to do some of these optimizations. We'd effectively just have a couple of other matches in there - e.g. _ if exp < 100 => etc.

At some stage however I think the exponent will be too large with minimal changes (i.e. a very small number). In this case there is also the opportunity to exit early rather than hit zero and continue iterating.

If you don't mind - I may actually open this issue again. While it does sound like you found a workaround I would like to make sure that unexpected "loops" that cause programs to hang are kept minimal.

from rust-decimal.

It's certainly slow, but I wouldn't say it takes forever. As an example:

    let base = dec!(0.99999999999999);
    let exp = dec!(147728940);
    println!("Starting");
    let result = base.powd(exp);
    println!("{result}");
    let second_result = base.checked_powd(exp).unwrap();
    println!("{second_result}");

The powd's result is printed about 10 seconds after the previous message, and checked_powd takes the same amount of time. Increasing the exponent by a factor of ten again makes it take 100 seconds instead, so (with admittedly few data points) this seems linear with the exponent value rather than exponential.

I don't suppose you could explain a little more about your use case? What are you attempting to do where you want to attempt to calculate an exponential, giving up if it takes too long? Maybe there's another solution that would work better.

from rust-decimal.

Yes I believe the unexpectedness is the issue here... If the pathological behaviour is documented and known then we can always trap it out way before it gets pathological.

from rust-decimal.

Nevertheless, I believe there is no particular reason to stop at squaring... We can just keep squaring until it reaches a power of two that is large enough.

Essentially, take the binary representation of the exponent. Anywhere there is a 1, square to that power (building up from previous powers). Then multiply up all the different powers where the binary of the exponent is 1.

This way, you are guaranteed a bounded total number of multiplications. For example, a 32-bit exponent takes at most 31 squarings to reach the highest power. Then at most 31 multiplications to arrive at the result .

Intermediate memory is limited to the accumulated result, the current power and the next square. Thus three decimal values worth.

There is no pathological case under this scheme.

I'll try to find time to make a PR.

from rust-decimal.

#638

from rust-decimal.