From e76138016dd063e510771bc097e7064f381eace2 Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Sun, 7 Jul 2019 00:19:12 -0700 Subject: [PATCH] switch algorithm in UnsignedDivRem to match FixedUDivRemSqrtRSqrt --- src/ieee754/div_rem_sqrt_rsqrt/algorithm.py | 25 +++++++++++++------ .../div_rem_sqrt_rsqrt/test_algorithm.py | 16 +++++++++--- 2 files changed, 29 insertions(+), 12 deletions(-) diff --git a/src/ieee754/div_rem_sqrt_rsqrt/algorithm.py b/src/ieee754/div_rem_sqrt_rsqrt/algorithm.py index 6ba28311..84ea1d4c 100644 --- a/src/ieee754/div_rem_sqrt_rsqrt/algorithm.py +++ b/src/ieee754/div_rem_sqrt_rsqrt/algorithm.py @@ -38,12 +38,14 @@ class UnsignedDivRem: NOT the same as the // or % operators - :attribute remainder: the remainder and/or dividend + :attribute dividend: the dividend + :attribute remainder: the remainder :attribute divisor: the divisor :attribute bit_width: the bit width of the inputs/outputs :attribute log2_radix: the base-2 log of the division radix. The number of bits of quotient that are calculated per pipeline stage. :attribute quotient: the quotient + :attribute quotient_times_divisor: ``quotient * divisor`` :attribute current_shift: the current bit index """ @@ -56,11 +58,12 @@ class UnsignedDivRem: :param log2_radix: the base-2 log of the division radix. The number of bits of quotient that are calculated per pipeline stage. """ - self.remainder = Const.normalize(dividend, (bit_width, False)) + self.dividend = Const.normalize(dividend, (bit_width, False)) self.divisor = Const.normalize(divisor, (bit_width, False)) self.bit_width = bit_width self.log2_radix = log2_radix self.quotient = 0 + self.quotient_times_divisor = self.quotient * self.divisor self.current_shift = bit_width def calculate_stage(self): @@ -74,17 +77,23 @@ class UnsignedDivRem: assert log2_radix > 0 self.current_shift -= log2_radix radix = 1 << log2_radix - remainders = [] + trial_values = [] for i in range(radix): - v = (self.divisor * i) << self.current_shift - remainders.append(self.remainder - v) + v = self.quotient_times_divisor + v += (self.divisor * i) << self.current_shift + trial_values.append(v) quotient_bits = 0 + next_product = self.quotient_times_divisor for i in range(radix): - if remainders[i] >= 0: + if self.dividend >= trial_values[i]: quotient_bits = i - self.remainder = remainders[quotient_bits] + next_product = trial_values[i] + self.quotient_times_divisor = next_product self.quotient |= quotient_bits << self.current_shift - return self.current_shift == 0 + if self.current_shift == 0: + self.remainder = self.dividend - self.quotient_times_divisor + return True + return False def calculate(self): """ Calculate the results of the division. diff --git a/src/ieee754/div_rem_sqrt_rsqrt/test_algorithm.py b/src/ieee754/div_rem_sqrt_rsqrt/test_algorithm.py index c5c3e7b3..7d6b2013 100644 --- a/src/ieee754/div_rem_sqrt_rsqrt/test_algorithm.py +++ b/src/ieee754/div_rem_sqrt_rsqrt/test_algorithm.py @@ -296,14 +296,22 @@ class TestUnsignedDivRem(unittest.TestCase): with self.subTest(n=n, d=d, q=q, r=r): udr = UnsignedDivRem(n, d, bit_width, log2_radix) for _ in range(250 * bit_width): - self.assertEqual(n, udr.quotient * udr.divisor - + udr.remainder) + self.assertEqual(udr.dividend, n) + self.assertEqual(udr.divisor, d) + self.assertEqual(udr.quotient_times_divisor, + udr.quotient * udr.divisor) + self.assertGreaterEqual(udr.dividend, + udr.quotient_times_divisor) if udr.calculate_stage(): break else: self.fail("infinite loop") - self.assertEqual(n, udr.quotient * udr.divisor - + udr.remainder) + self.assertEqual(udr.dividend, n) + self.assertEqual(udr.divisor, d) + self.assertEqual(udr.quotient_times_divisor, + udr.quotient * udr.divisor) + self.assertGreaterEqual(udr.dividend, + udr.quotient_times_divisor) self.assertEqual(udr.quotient, q) self.assertEqual(udr.remainder, r) -- 2.30.2