1

I am looking to implement a big integer library in C, and I am still stuck on as to how I should represent an input string as an array of long integers. The input string would be given in base-10, and then I would need to be able to find out how to store this in base 2^64 (the size of a long integer).

unsigned long long *string_to_long_arr(char *string);

I know I can use floored division and the modulo operation to convert between bases, but this won't work for large numbers as I won't have access to those operations. I was thinking about trying to use the ASCII values of the input string, but I'm not sure how well that'd work and what its exact implementation would be like. Also, I know other programming languages have big integers (Python, for example). I haven't found how its implementation works. Links to how the conversion process between strings and long arrays in other programming languages would be much appreciated. Thank you!

William Ryman
  • 231
  • 2
  • 9
  • 2
    first step is to convert arbitrarily long decimal to binary (as the title hints). The long long bit is irrelevant . Interesting question. – pm100 Mar 13 '22 at 16:36
  • 3
    Related, for ideas [GMP](https://gmplib.org/), [OpenSSL](https://www.openssl.org/docs/man1.0.2/man3/bn.html), etc. If you're really interested the source for most such implementations is readily available for perusal. I'm more familiar with the latter, and it seems the actions of BN_asc2bn and BN_bn2asc would be what you'd be interested in. – WhozCraig Mar 13 '22 at 16:39
  • 1
    *but this won't work for large numbers as I won't have access to those operations.* These are the very operations that will be present in your big integer library. – President James K. Polk Mar 13 '22 at 16:44
  • 2
    You should not store it as 64-bit array unless you have access to 128-bit operations. Work with a 32-bit array, so you can use 64-bit for partial products, sums, carries etc that propagate along the array. The "easy" way to convert to and from decimal text is the usual one: for dec->bigint multiply the bigint by 10 and add the next digit. For bigint->dec, divide the bigint by 10 and buffer the remainder. Repeat until done in both cases. They are fairly simple because they are basic operations on the bigint with a small constant. It's much harder when both operands are bigint. – Weather Vane Mar 13 '22 at 17:34
  • 1
    see [How to convert a gi-normous integer (in string format) to hex format?](https://stackoverflow.com/a/18231860/2521214) ... once you have hex string its easy and fast to convert to binary you just use LUT for the 16 digit possibilities – Spektre Mar 14 '22 at 06:58

0 Answers0