Is there a way to make this function faster? (C)
If you don't want to change the format of the data, you can try SIMD.
typedef uint8_t u8x16 __attribute__((vector_size(16)));
void add_digits(uint8_t *const lhs, uint8_t *const rhs, uint8_t *out, size_t n) {
uint8_t carry = 0;
for (size_t i = 0; i + 15 < n; i += 16) {
u8x16 digits = *(u8x16 *)&lhs[i] + *(u8x16 *)&rhs[i] + (u8x16){carry};
// Get carries and almost-carries
u8x16 carries = digits >= 10; // true is -1
u8x16 full = digits == 9;
// Shift carries
carry = carries[15] & 1;
__uint128_t carries_i = ((__uint128_t)carries) << 8;
carry |= __builtin_add_overflow((__uint128_t)full, carries_i, &carries_i);
// Add to carry chains and wrap
digits += (((u8x16)carries_i) ^ full) & 1;
// faster: digits = (u8x16)_mm_min_epu8((__m128i)digits, (__m128i)(digits - 10));
digits -= (digits >= 10) & 10;
*(u8x16 *)&out[i] = digits;
}
}
This is ~2 instructions per digit. You'll need to add code to handle the tail-end.
Here's a run-through of the algorithm.
First, we add our digits with our carry from the last iteration:
lhs 7 3 5 9 9 2
rhs 2 4 4 9 9 7
carry 1
+ -------------------------
digits 9 7 9 18 18 10
We calculate which digits will produce carries (≥10), and which would propagate them (=9). For whatever reason, true is -1 with SIMD.
carries 0 0 0 -1 -1 -1
full -1 0 -1 0 0 0
We convert carries to an integer and shift it over, and also convert full to an integer.
_ _ _ _ _ _
carries_i 000000001111111111110000
full 111100001111000000000000
Now we can add these together to propagate carries. Note that only the lowest bit is correct.
_ _ _ _ _ _
carries_i 111100011110111111110000
(relevant) ___1___1___0___1___1___0
There are two indicators to look out for:
carries_ihas its lowest bit set, anddigit ≠ 9. There has been a carry into this square.carries_ihas its lowest bit unset, anddigit = 9. There has been a carry over this square, resetting the bit.
We calculate this with (((u8x16)carries_i) ^ full) & 1, and add to digits.
(c^f) & 1 0 1 1 1 1 0
digits 9 7 9 18 18 10
+ -------------------------
digits 9 8 10 19 19 10
Then we remove the 10s, which have all been carried already.
digits 9 8 10 19 19 10
(d≥10)&10 0 0 10 10 10 10
- -------------------------
digits 9 8 0 9 9 0
We also keep track of carries out, which can happen in two places.
Candidates for speed improvement:
Optimizations
Be sure you have enabled you compiler with its speed optimizations settings.
restrict
Compiler does not know that changing Vout[] does not affect Vin1[], Vin2[] and is thus limited in certain optimizations.
Use restrict to indicate Vin1[], Vin2[] are not affected by writing to Vout[].
// void LongNumAddition1(unsigned char *Vin1, unsigned char *Vin2, unsigned char *Vout, unsigned N)
void LongNumAddition1(unsigned char * restrict Vin1, unsigned char * restrict Vin2,
unsigned char * restrict Vout, unsigned N)
Note: this restricts the caller from calling the function with a Vout that overlaps Vin1, Vin2.
const
Also use const to aid optimizations. const also allows const arrays to be passed as Vin1, Vin2.
// void LongNumAddition1(unsigned char * restrict Vin1, unsigned char * restrict Vin2,
unsigned char * restrict Vout, unsigned N)
void LongNumAddition1(const unsigned char * restrict Vin1,
const unsigned char * restrict Vin2,
unsigned char * restrict Vout,
unsigned N)
unsigned
unsigned/int are the the "goto" types to use for integer math. Rather than unsigned char CARRY or char CARRY, use unsigned or uint_fast8_t from <inttypes.h>.
% alternative
sum = a+b+carry; if (sum >= 10) { sum -= 10; carry = 1; } else carry = 0; @pmg or the like.
Note: I would expect LongNumAddition1() to return the final carry.
To improve the speed of your bignum addition, you should pack more decimal digits into array elements. For example: you can use uint32_t instead of unsigned char and store 9 digits at a time.
Another trick to improve performance is you want to avoid branches.
Here is a modified version of your code without tests:
void LongNumAddition1(const char *Vin1, const char *Vin2, char *Vout, unsigned N) {
char carry = 0;
for (int i = 0; i < N; i++) {
char r = Vin1[i] + Vin2[i] + CARRY;
carry = (r >= 10);
Vout[i] = r - carry * 10;
}
}
Here is a modified version dealing with 9 digits at a time:
#include <stdint.h>
void LongNumAddition1(const uint32_t *Vin1, const uint32_t *Vin2, uint32_t *Vout, unsigned N) {
uint32_t carry = 0;
for (int i = 0; i < N; i++) {
uint32_t r = Vin1[i] + Vin2[i] + CARRY;
carry = (r >= 1000000000);
Vout[i] = r - carry * 1000000000;
}
}
You can look at the code generated by gcc and clang on GodBolt's Compiler Explorer.
Here is a small test program:
#include <inttypes.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
int LongNumConvert(const char *s, uint32_t *Vout, unsigned N) {
unsigned i, len = strlen(s);
uint32_t num = 0;
if (len > N * 9)
return -1;
while (N * 9 > len + 8)
Vout[--N] = 0;
for (i = 0; i < len; i++) {
num = num * 10 + (s[i] - '0');
if ((len - i) % 9 == 1) {
Vout[--N] = num;
num = 0;
}
}
return 0;
}
int LongNumPrint(FILE *fp, const uint32_t *Vout, unsigned N, const char *suff) {
int len;
while (N > 1 && Vout[N - 1] == 0)
N--;
len = fprintf(fp, "%"PRIu32"", Vout[--N]);
while (N > 0)
len += fprintf(fp, "%09"PRIu32"", Vout[--N]);
if (suff)
len += fprintf(fp, "%s", suff);
return len;
}
void LongNumAddition(const uint32_t *Vin1, const uint32_t *Vin2,
uint32_t *Vout, unsigned N) {
uint32_t carry = 0;
for (unsigned i = 0; i < N; i++) {
uint32_t r = Vin1[i] + Vin2[i] + carry;
carry = (r >= 1000000000);
Vout[i] = r - carry * 1000000000;
}
}
int main(int argc, char *argv[]) {
const char *sa = argc > 1 ? argv[1] : "123456890123456890123456890";
const char *sb = argc > 2 ? argv[2] : "2035864230956204598237409822324";
#define NUMSIZE 111 // handle up to 999 digits
uint32_t a[NUMSIZE], b[NUMSIZE], c[NUMSIZE];
LongNumConvert(sa, a, NUMSIZE);
LongNumConvert(sb, b, NUMSIZE);
LongNumAddition(a, b, c, NUMSIZE);
LongNumPrint(stdout, a, NUMSIZE, " + ");
LongNumPrint(stdout, b, NUMSIZE, " = ");
LongNumPrint(stdout, c, NUMSIZE, "\n");
return 0;
}