Prior rounding scheme for efficient finite decimal multiplication

Question

This concerns fixed precision finite decimal multiplication. It is about prior rounding which may be computationally beneficial as the result is only needed to be accurate at a specific Order of Magnitude (OM) given a particular rounding mode (RM).

Let, a and b be finite decimals, and an OM and RM be specified. How much prior rounding of a and b can be done to get a result equal to that obtained by multiplying a and b (a * b) exactly and then rounding using the specified OM and RM?

Is there a formula that works for all cases?

Example 1.

• a=12.34567; b=67.89123; OM=-1; RM=Half_UP (HU)
• With no prior rounding: a*b = 838.1627214741 ~ 838.2

(i) RM=HU for all rounding:

• Prior round a(OM=-1), b(OM=-1): 12.3 * 67.9 = 835.17 ~ 835.2
• Prior round a(OM=-2), b(OM=-2): 12.35 * 67.89 = 838.4415 ~ 838.4
• Prior round a(OM=-2), b(OM=-3): 12.35 * 67.891 = 838.45385 ~ 838.4
• Prior round a(OM=-3), b(OM=-2): 12.346 * 67.89 = 838.16994 ~ 838.2
• Prior round a(OM=-3), b(OM=-3): 12.346 * 67.891 = 838.182286 ~ 838.2

(ii) RM=Half_Down (HD) to prior round a XOR b and RM = HU for the final round.

• This is the same as (i) in this example (as neither a or b has 5 as the last digit at a significant place).

(iii) RM=Down (D) to prior round a XOR b and RM=Up (U) to prior round the other, and RM=HU for the final round.

a(RM=D), b(RM=U)

• Prior round a(OM=-2), b(OM=-2): 12.34 * 67.90 = 837.886 ~ 837.9
• Prior round a(OM=-2), b(OM=-3): 12.34 * 67.892 = 837.78728 ~ 837.8
• Prior round a(OM=-3), b(OM=-2): 12.345 * 67.90 = 838.2255 ~ 838.2
• Prior round a(OM=-3), b(OM=-3): 12.345 * 67.892 = 838.12674 ~ 838.1
• Prior round a(OM=-4), b(OM=-3): 12.3456 * 67.892 = 838.1674752 ~ 838.2
• Prior round a(OM=-3), b(OM=-4): 12.345 * 67.8913 = 838.1180985 ~ 838.1
• Prior round a(OM=-4), b(OM=-4): 12.3456 * 67.8913 = 838.15883328 ~ 838.2
• Prior round a(OM=-5), b(OM=-4): 12.34567 * 67.8913 = 838.163585671 ~ 838.2
• Prior round a(OM=-4), b(OM=-5): 12.3456 * 67.89123 = 838.157969088 ~ 838.2

a(RM=U), b(RM=D)

• Prior round a(OM=-2), b(OM=-2): 12.35 * 67.89 = 838.4415 ~ 838.4
• Prior round a(OM=-2), b(OM=-3): 12.35 * 67.891 = 838.45385 ~ 838.5
• Prior round a(OM=-3), b(OM=-2): 12.346 * 67.89 = 838.16994 ~ 838.2
• Prior round a(OM=-3), b(OM=-3): 12.346 * 67.891 = 838.182286 ~ 838.2
• Prior round a(OM=-4), b(OM=-3): 12.3457 * 67.891 = 838.1619187 ~ 838.2
• Prior round a(OM=-3), b(OM=-4): 12.346 * 67.8912 = 838.1847552 ~ 838.2
• Prior round a(OM=-4), b(OM=-4): 12.3457 * 67.8912 = 838.16438784 ~ 838.2
• Prior round a(OM=-5), b(OM=-4): 12.34567 * 67.8912 = 838.162351104 ~ 838.2
• Prior round a(OM=-4), b(OM=-5): 12.3457 * 67.89123 = 838.164758211 ~ 838.2

Example 2.

• a=99.00044=b; OM=-1; RM=HU.
• With no prior rounding: a * b = 9801.0871201936 ~ 9801.1

(i) RM=HU for all rounding:

• Prior round a(OM=-3), b(OM=-3): 99 * 99 = 9801 ~ 9801.0
• Prior round a(OM=-4), b(OM=-3): 99.0004 * 99 = 9801.0396 ~ 9801.0
• Prior round a(OM=-3), b(OM=-4): 99 * 99.0004 = 9801.0396 ~ 9801.0
• Prior round a(OM=-4), b(OM=-4): 99.0004 * 99.0004 = 9801.07920016 ~ 9801.1 ...

Example 3.

• a=999999.0000999999; b=999.000999; OM=-1; RM=HU.
• With no prior rounding: a * b = 999000000.0989009999999001 ~ 999000000.1

(i) RM=HU for all rounding:

• Prior round a(OM=-4), b(OM=-4): 999999.0001 * 999.0010 = 999000001.0989001 ~ 999000001.1
• Prior round a(OM=-4): 999999.0001 * 999.000999 = 999000000.0989010999 ~ 999000000.1 ...

Considerations:

• A good strategy might be to prior round one number up and the other down.
• The aim of prior rounding a and b is to reduce the amount of computation. This may be futile for decimals with small numbers of digits or for when there is only a small amount of rounding, but there could be significant computational gains for decimals with very large numbers of digits and substantial amounts of rounding.
• I have now considered prior rounding for the case of multiplication of integers and developed some Java code to start to answer this question. I realised that prior rounding only the largest integer is a good approach and I think that the most prior rounding that can be done of the larger number is to round to the magnitude that is the integer part of the square root of the magnitude of the larger number. So, if: the two numbers being multiplied are a=(100 consecutive 9s) and b=(50 consecutive 9s); OM=64. Then the most prior rounding of x that can be done is to effectively divide x by 100000000, multiply the result of this by y and then multiply by 100000000. This has made me realise that any computational benefits of prior rounding for multiplying integers of this magnitude are likely to be negligible, the numbers involved must be far larger to gain any benefit from the overhead of the prior rounding. Translating this to decimal numbers, the benefit of prior rounding is going to be dependent on the magnitude of the integer component of the larger number, the number of decimal places it has, and the order of magnitude at which a precise albeit rounded result is wanted.
• Special cases with rounding typically involve the digits 4, 5 and 9.

Feedback:

• Thanks in advance for any feedback (on how to improve the question, or what examples might help).
• I do not plan to detail the examples further as I don't want to edit the question too much and I think now that prior rounding just one of the numbers is probably the best strategy.
• I intend to post an answer and provide a link to the Java implementation in due course. I am hoping to post an answer or an update in February.

Answer 1

The problem can be divided into cases:

• Case 1: a and b are integers
• Case 2: a is an integer AND b is a fraction
• Case 3: a AND b are both fractions
• Case 4: a is a fraction AND b is a decimal
• Case 5: a AND b are both decimals

Where:

• a fraction is a number x such that -1 < x < 1 and is expressed as a decimal.
• a decimal has both an integer and fractional part
• Case 5 is the general case. It can be split into a two part problem: Separate a into the integer and fractional parts. Multiply the integer part by b (an example of Case 2). Multiply the fractional part by the b (an example of Case 4). Add the two parts together and do a final round. (When calculating the two components a bit more precision is needed - calculate the parts to 3 extra digits of precision).

I developed some Java code and a test suite. The method names start "multiplyPriorRound" and can be found in the following classes:

• https://github.com/agdturner/agdt-java-math/blob/master/src/main/java/uk/ac/leeds/ccg/math/Math_BigDecimal.java
• https://github.com/agdturner/agdt-java-math/blob/master/src/main/java/uk/ac/leeds/ccg/math/Math_BigInteger.java

A suite of test cases are in the associated JUnit test classes with method names beginning suites "testMultiplyPriorRound":

• https://github.com/agdturner/agdt-java-math/blob/master/src/test/java/uk/ac/leeds/ccg/math/Math_BigDecimalTest.java
• https://github.com/agdturner/agdt-java-math/blob/master/src/test/java/uk/ac/leeds/ccg/math/Math_BigIntegerTest.java

I drew some pictures to help me figure out what to do. The key idea is to make the strings of digits smaller mostly by disregarding the smallest parts of any fractions. For each number it was important to figure out the OM of the digit furthest to the left and furthest to the right. The number of digits to the left of the OM wanted for the result precision is important for identifying if and where to round the other number.

OM = * 9 8 7 6 5 4 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 *

Case 1: a = * * * * * * * * * *. b = * * * * * * *.

Case 2: a = * * * * * * * * * *. b = . * * * * * * * * * *

Case 3: a = . * * * * * * * * * * b = . * * * * * * * * * *

Case 4: a = . * * * * * * * * * * b = * * * * * * *. * * * * * * * *

Case 5: a = * * * * * * * * * *. * * * * * * * * b = * * * * * * *. * * * * * * * * * *

Sorry this is not a complete self contained answer. I am not sure if anyone is interested in this, so I am going to leave this here for now and see what happens. I may detail things further in due course. I hope to get around to doing some timing experiments to compare the prior rounding multiplication with arbitrary precision multiplication. I may post about that in another forum appropriate for that. (The numbers may have to have a lot of digits before there is a significant advantage.) There are similar challenges for efficient prior rounding in division and in raising a decimal to the power of another decimal...