Challenge 3 results

DonMcCormack · Jul 6, 2020 06:23 PM

Thanks again to those who participated, and thanks for your patience with this late post. Everyone was able to complete the challenges. Both the largest numbers added (~2 million digits) and largest 1,000-digit list (~2,000 items) challenges for non-JMP staff were bested by @David_Burnham. For staff entries, the biggest two numbers added under 5 seconds was about 22 million (@brady_brady and @Craige_Hales) and the largest list was about 61,500 elements (Challenge 3 Example 3.JSL). These scripts have been posted below.

Here are point totals through three challenges:

Name	Points	Entries
@David_Burnham	37	3
@leelaim	36.5	3
@MathStatChem	28	2
@landon	24	2
@P_Anderson	22.5	2

Let's start with operations involving two numbers. Challenge 3 Example 1 – slow.JSL provides an implementation similar to most of the entries:

Determine if the numbers are the same (addition) or opposite (subtraction) signs.
Parse the number string.
Perform the addition/subtraction operations.
Concatenate the results to build the answer.

Whether addition and subtraction operations are performed in a single function or multiple functions is a matter of style and should only effect program clarity and readability, but not execution time. What will make a huge difference, however, is how input numbers are parsed and put back together. Parsing the input strings before looping over the individual digits (Challenge 3 Example 1 – faster.JSL) rather than inside the loop speeds the operation by about 5X (2.28 sec. vs. 0.464 sec for adding 2 16,000-digit numbers). Removing the individual string concatenations from inside the loops by collecting the results in a list then concatenating the items at the end speeds things up more than 10X (0.04054 sec) – see (Challenge 3 Example 1 – fastest.JSL).

Before we talk about how to make this even faster, we should talk about adding numbers in a list. Nearly everyone handled this problem by iterating through the list one item at a time, adding each to a running total. While this was not ultimately the fastest approach, it could be made exceptionally fast (Challenge 3 - Hales.JSL added 51,000 1000-digit numbers under 5 seconds). As with most operations, the key to speed improvements is to minimize the number of operations, all things equal. In the provided example, Challenge 3 Example 2.JSL, the solution was to reduce the carry/borrow operations from once set for each pair of numbers to three sets total. This was accomplished by:

Loading the input numbers into two matrices, one for positive numbers one for negative numbers.
Add each matrix separately using V Sum, perform one set of carry operations for the two result matrices.
Subtract the smaller number from the larger number. Perform a set of borrow operations once for the results. The final subtraction is performed using the two-number algorithm discussed above.

Both two-number and list operations can be made yet faster by considering more than one digit at a time during the carry/borrow operations. This was done in both Challenge 3 - Hales.JSL and Challenge 3 - Brady.JSL. While the natural inclination is to add/subtract/carry/borrow with one number, the procedure can, with a bit of ingenuity, be generalized to as many numbers as possible, provided overflow doesn't occur. In JMP, this would be 14 digits for the two-number case and 14 – Floor(Log10(listSize – 1)) digits, where listSize is the number of items in the input list, in the list case. To understand why this is so, recall that overflow occurs at about 9e16. Adding the two largest 15-digit numbers (fifteen 9s) causes an overflow error. Adding the two largest 14-digit numbers does not. Similarly, adding 9,999,999,999,999 to itself will cause an overflow when it is performed somewhere between 11 and 100 times (91 times, to be exact).

As an example of how this might work, consider adding three numbers where each number is arranged in registers of 14:

11 99999999999999

22 99999999999999

33 99999999999999

Summing the values from the first register (the 14 9s) gives you

2 99999999999997

Carrying the 2 and summing the second register gives you

68

The final number is

68 99999999999997

Application of this approach is given in Challenge 3 Example 3.JSL. Average processing time for adding two 2-million-digit numbers improves from 4.7 to 0.82 sec, a more than 5X speed improvement. Additional tweaks can improve the speed by another 2X, as evidenced by Challenge 3 - Hales.JSL and Challenge 3 - Brady.JSL The time required to add 10,000 1000-digit numbers is reduced from 4.5 to 0.88 seconds (5X). This results in the fastest list addition approach.

20 July 2020: One more bug fix, this time to Challenge 3 Example 3.JSL. Added warning messages when using a matrix argument for all three Example 1 files (not implemented until Example 2).

17 July 2020: I found another bug in the Challenge 3 Example 1 scripts and all three have been fixed and replaced.

16 July 2020: I replaced the scripts Challenge 3 Example 1 - slow.JSL and Challenge 3 Example 1 - faster.JSL because they contained a line at the end that causes a problem (they reference a table I was using to test the code). If you've downloaded these files and haven't fixed the problem yourself, please replace your older copies.