HugeMotherFuckingInt

I'm trying to write a HugeMotherFuckingInt processing library in C.

My first try, I stored the numbers as a char[] and computed them using basic arithmetic.

My second try, I stored the numbers as unsigned long char[]. This proved to be a faster, easier and clearer approach.

Still though, it seems to be a bit too slow.

What other data structures might result in faster execution of basic arithmetic +/*-?

Also, are there any algorithms to speed up the arithmetic operations themselves?

You should use an unsigned int representation for efficiency as this is the machine word size. C ensures unsigned addition wraps around so you can implement most algorithms quite easily. Some tricks are needed for multiplication which aren't worth discussing. Endianness doesn't really matter.

typedef struct _biginteger {
    int length;
    int capacity;
    unsigned int* data;
} bigint;

If you are actually planning to use the library rather than write a toy implementation you should just use an existing implementation, eg GMP.

GMP makes available an extremely useful algorithms reference at http://gmplib.org/manual/Algorithms.html#Algorithms which you may find useful.

Unless you have ~500 limb integers long multiplication will probably be the fastest method available- so any performance improvements need to come from micro optimizations. Or rather, hand coding assembly, which is why you don't really want to write your own.