How Can I Implement Arbitrary-Length Integers in C ?

Implementing Arbitrary-Length Integers in C

When faced with the task of handling numbers exceeding the capacity of a typical long int, many programmers resort to existing open source implementations. However, the challenge of creating your own custom BigInt class offers valuable insights into the intricacies of numerical operations.

Approach

The fundamental approach for BigInt implementation involves representing the number as a string, breaking it down into smaller digits (e.g., single digits), and storing them in an array. This enables straightforward implementation of comparison operators. The challenge lies in implementing more complex operations like addition and multiplication.

Addition

To perform addition, we mimic the binary operations used by CPUs. Each element of the BigInt's value array is added, with any overflow being carried to the next element. As an example, consider the = operator implementation:

BigInt& operator+=(const BigInt& operand) {
  BT count, carry = 0;
  for (count = 0; count < std::max(value_.size(), operand.value_.size()); count++) {
    BT op0 = count < value_.size() ? value_.at(count) : 0,
       op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
    BT digits_result = op0 + op1 + carry;
    if (digits_result - carry < std::max(op0, op1)) {
      BT carry_old = carry;
      carry = digits_result;
      digits_result =
          (op0 + op1 + carry) >> sizeof(BT) * 8; // NOTE [1]
    } else
      carry = 0;
  }

  return *this;
}

Multiplication

Multiplication can be performed using repeated additions. Alternatively, efficient algorithms like the Karatsuba method can be employed.

Additional Considerations

The BigInt class should provide standard operators such as operator<< for shifting and comparison operators like operator<. Befriending std::ostream operator<< enables convenient output. Optimizations can be made to improve efficiency, such as checking the number of digits with size() before performing comparisons.

The above is the detailed content of How Can I Implement Arbitrary-Length Integers in C ?. For more information, please follow other related articles on the PHP Chinese website!