How to store store the value 10^20 in C?

Question

I want to multiply two numbers of sizes 10^10, resulting size is 10^20 which is 2^66.

I want to store that number in a standard datatype in C. I would rather not use "GNU MP Bignum library".

Why does the following C program not hold the number correctly?

#include<stdio.h>
typedef long long int ull;
int main(){

    ull n1 = 10000000000LL;
    ull n2 = 10000000000LL;

    printf("%llu",n1*n2);
    return 0;
}

What would be the best way to hold this number and work with it?

Answer 1

Store it as two long long values. Here's a sketch of a solution:

#include <stdio.h>

typedef unsigned long long ull;

void multiply( ull a, ull b, ull * lo, ull * hi )
{
  ull ah = a >> 32;
  ull bh = b >> 32;
  ull al = a & 0xFFFFFFFF;
  ull bl = b & 0xFFFFFFFF;

  ull mid = ah * bl + al * bh;
  ull albl = al * bl;

  ull imm = mid + ( albl >> 32 );

  *lo = ( mid << 32 ) + albl;
  *hi = ah * bh + ( imm >> 32 );
}

int main()
{
  ull n1 = 10000000000LL;
  ull n2 = 10000000000LL;

  ull lo, hi;

  multiply( n1, n2, &lo, &hi );

  printf( "result in hex is %llx%016llx\n", hi, lo );
  return 0;
}

Outputs:

result in hex is 56bc75e2d63100000

Answer 2

On a 64 bit architecture a long long holds at most 2^63-1. On 32 bit at most: 2^32 -1. If you need bigger numbers than that, then you should re-evaluate what you are doing if there is a better way to solve the problem.

If you need bigger numbers, you'll have to either create your own library or use someone else's library:

Here are two libraries to handle Arbitrary Precision numbers. The limits of how big a number you can use depend on the amount of disk space, memory, and processing power you have to hold and compute them.

GMP and MAPM

If you must roll your own, You could store it in an array of integers. A 64-bit integer is just two 32-bit integers. A 1024 bit integer could also be seen as thirty two 32-bit integers. Create a class which holds arrays of integers, stitching them together into any size you need. The hard part is then to write functions which can add subtract multiply and divide the arrays of integers.

Answer 3

You could implement an arbitrarily large numerical value using a variety of strategies.

I am personally a fan of using a linked list. The idea would be to store every digit in a node. You would need to implement an addition, subtraction, multiplication and division function respectively.