From 839e1096dde8e1e934a82d1cf0c4d3a43dc69f38 Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Wed, 26 Oct 2022 17:59:27 +0200 Subject: Use MulAssign in BaseConversion. Benchmarks show that MulAssign is quite a bit faster than Mul, especially since in this case it's mathematically proven that the multiplication cannot overflow. Also, removed skipping of leading zeros in long division. With the switch to multiplication after the first iteration, the chance that there actually are any leading zeros is on the order of 2^-26. I think at least. In any case, it's small. --- .../base_conversion/iterative_conversion.rs | 20 ++++++++++++++------ 1 file changed, 14 insertions(+), 6 deletions(-) (limited to 'src/passwordmaker/base_conversion/iterative_conversion.rs') diff --git a/src/passwordmaker/base_conversion/iterative_conversion.rs b/src/passwordmaker/base_conversion/iterative_conversion.rs index 7d52e9b..710903e 100644 --- a/src/passwordmaker/base_conversion/iterative_conversion.rs +++ b/src/passwordmaker/base_conversion/iterative_conversion.rs @@ -9,7 +9,7 @@ //! If you have any great idea how to improve it: Make a merge request! use std::convert::TryInto; -use std::ops::{Mul, DivAssign}; +use std::ops::{Mul, DivAssign, MulAssign}; use std::iter::successors; pub(crate) struct IterativeBaseConversion{ @@ -59,10 +59,10 @@ impl IterativeBaseConversion } impl std::iter::Iterator for IterativeBaseConversion - where V : for<'a> DivAssign<&'a B> + //used between steps to go to next-lower current_base_power + where V : for<'a> DivAssign<&'a B> + //used in the first iteration to ensure that MulAssign cannot overflow. RemAssignWithQuotient+ //used to get the result of each step. - TryInto, //used to convert the result of each step. We _know_ this cannot fail, but requiring Into would be wrong. - for<'a> &'a V : Mul<&'a B, Output = Option> + TryInto+ //used to convert the result of each step. We _know_ this cannot fail, but requiring Into would be wrong. + for<'a> MulAssign<&'a B> //used instead of DivAssign after one iteration. it's faster to mul the dividend than div the divisor. { type Item = B; @@ -73,7 +73,9 @@ impl std::iter::Iterator for IterativeBaseConversion let result = self.current_value.rem_assign_with_quotient(&self.current_base_power); if self.switch_to_multiplication { - self.current_value = (&self.current_value * &self.base).expect("Cannot overflow."); + //mul_assign is in principle dangerous. + //Since we do two rem_assign_with_quotient calls first, we can be sure that the result is always smaller than base^max_power though. + self.current_value *= &self.base } else { self.current_base_power /= &self.base; self.switch_to_multiplication = true; @@ -128,7 +130,13 @@ mod iterative_conversion_tests{ type Output = Option; fn mul(self, rhs: &MyU128) -> Self::Output { self.0.checked_mul(rhs.0).map(|s| MyU128(s)) - } + } + } + + impl MulAssign<&u64> for MyU128 { + fn mul_assign(&mut self, rhs: &u64) { + self.0.mul_assign(*rhs as u128); + } } impl RemAssignWithQuotient for MyU128{ -- cgit v1.2.3