Parallelised addition for `bigint`s #4

New issue

Open

opened 2025-12-13 17:25:50 -05:00 by Ghost · 0 comments

Ghost commented

2025-12-13 17:25:50 -05:00

(Migrated from codefloe.com)

Addition can be parallelised for bigints by:

Doing the addition between corresponding digits in parallel.
Storing the carried values in a separate buffer one digit over.
Repeating step 1 between the sum and the carries.

For example:

 [1,2,3,4,5,6,7,8,9]
+[0,0,0,0,5,2,3,5,1]
--------------------
 [1,2,3,4,0,8,0,3,0] // sum_1
+[0,0,0,1,0,1,1,1,0] // carry
--------------------
 [1,2,3,5,0,9,1,4,0] // answer

Obviously each element will be a full 64-bit integer rather than individual digits, but the algorithm still applies. In the worst case, this algorithm will take n steps, where n is the size of the larger array. This is the 99999999\dots9+1 case. However, in every other case, it will more efficient.

Addition can be parallelised for `bigint`s by: 1. Doing the addition between corresponding digits in parallel. 2. Storing the carried values in a separate buffer one digit over. 3. Repeating step 1 between the sum and the carries. For example: ``` [1,2,3,4,5,6,7,8,9] +[0,0,0,0,5,2,3,5,1] -------------------- [1,2,3,4,0,8,0,3,0] // sum_1 +[0,0,0,1,0,1,1,1,0] // carry -------------------- [1,2,3,5,0,9,1,4,0] // answer ``` Obviously each element will be a full 64-bit integer rather than individual digits, but the algorithm still applies. In the worst case, this algorithm will take $n$ steps, where $n$ is the size of the larger array. This is the $99999999\dots9+1$ case. However, in every other case, it will more efficient.