Asked  7 Months ago    Answers:  5   Viewed   62 times

I'd like to implement a big int class in C++ as a programming exercise—a class that can handle numbers bigger than a long int. I know that there are several open source implementations out there already, but I'd like to write my own. I'm trying to get a feel for what the right approach is.

I understand that the general strategy is get the number as a string, and then break it up into smaller numbers (single digits for example), and place them in an array. At this point it should be relatively simple to implement the various comparison operators. My main concern is how I would implement things like addition and multiplication.

I'm looking for a general approach and advice as opposed to actual working code.

 Answers

37

Things to consider for a big int class:

  1. Mathematical operators: +, -, /, *, % Don't forget that your class may be on either side of the operator, that the operators can be chained, that one of the operands could be an int, float, double, etc.

  2. I/O operators: >>, << This is where you figure out how to properly create your class from user input, and how to format it for output as well.

  3. Conversions/Casts: Figure out what types/classes your big int class should be convertible to, and how to properly handle the conversion. A quick list would include double and float, and may include int (with proper bounds checking) and complex (assuming it can handle the range).

Tuesday, June 1, 2021
 
aaronhuisinga
answered 7 Months ago
11

The GNU Multiple Precision Arithmetic Library does what you want http://gmplib.org/

Gnu MP is a C library but it has a C++ class Interface and if you are interested only in big integers, you may just deal with mpz_class. Look at the sample below which I took from the page C++ Interface General

 int main (void)
 {
   mpz_class a, b, c;

   a = 1234;
   b = "-5678";
   c = a+b;
   cout << "sum is " << c << "n";
   cout << "absolute value is " << abs(c) << "n";

   return 0;
 }
Saturday, June 5, 2021
 
employeegts
answered 7 Months ago
81
unsigned concatenate(unsigned x, unsigned y) {
    unsigned pow = 10;
    while(y >= pow)
        pow *= 10;
    return x * pow + y;        
}

Proof of compilation/correctness/speed

I avoid the log10 and pow functions, because I'm pretty sure they use floating point and are slowish, so this might be faster on your machine. Maybe. Profile.

Monday, June 14, 2021
 
Pradip
answered 6 Months ago
44

AFAIK the EntityManager Java interface cannot be implemented directly in Scala. The Java varargs are converted to Seq[Class[_]] in the first method and Seq[String] in the second method. Because of erasure, both methods then appear as having the same signature createStoredProcedureQuery(String, Seq[_]).

I can only propose a workaround for this issue. You should write a Java abstract class that extends the EntityManager interface and implement the 2 offending methods by delegating to 2 other abstract methods with different names in order to disambiguate:

public abstract class EntityManagerWorkaround implements EntityManager {
@Override
public StoredProcedureQuery createStoredProcedureQuery(String procedureName, Class... resultClasses) {
    return createStoredProcedureQueryForResultClasses(procedureName, resultClasses);
}

@Override
public StoredProcedureQuery createStoredProcedureQuery(String procedureName, String... resultSetMappings) {
    return createStoredProcedureQueryForResultSetMappings(procedureName, resultSetMappings);
}

public abstract StoredProcedureQuery createStoredProcedureQueryForResultClasses(String procedureName, Class... resultClasses);

public abstract StoredProcedureQuery createStoredProcedureQueryForResultSetMappings(String procedureName, String... resultSetMappings);

}

Now you can extend the abstract class from Scala and implement the disambiguated methods:

class EntityManagerImpl extends EntityManagerWorkaround {
  override def createStoredProcedureQueryForResultClasses(procedureName: String, resultClasses: Class[_]*) = ???

  override def createStoredProcedureQueryForResultSetMappings(procedureName: String, resultSetMappings: String*) = ???
}
Monday, August 23, 2021
 
Jacob
answered 4 Months ago
39

First of all, you can't do I/O in a sensible way without the basic operations(e.g. division and modulus). To provide efficient implementation of converting the bigint to base-10 string, I am researching two possible optimizations:

First, you can divide by some power of ten instead of ten exactly. What that means, you will get four base-10 digits every time you divide the number by 10000 for example.

Second, how would you choose which power of ten to divide by? 10, 100, 1000, 10000, etc...
There seems to be a good choice which is the maximum power of ten that can fit in your word(32-bit). Fortunately, you can implement division/modulus by one word much more efficiently than when it comes to two "bigint"s.

I haven't given an implementation because I am still researching the problem in my spare time because I have implemented the basic operations in my library and I/O is the next step hopefully ;)

Sunday, October 3, 2021
 
Yrtymd
answered 2 Months ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :
 
Share