How bad would be this algorithm that converts a string to a multiple precision number?

Question

I've been developing a C++ library for multiple precision computations (integers/fixed point), assume positive numbers.

The class is something like:

class Integer {
 public:
   //constructor
   //destructor
   //set
   //overload operators
 private;
  uint32_t *mem;
  int n_bits_stored;
};

Specifically the //overload operatos has binary operators like

Integer Integer::operator+(const Integer& rhs);
Integer Integer::operator-(const Integer& rhs);
Integer Integer::operator*(const Integer& rhs);
Integer Integer::operator/(const Integer& rhs);
Integer Integer::operator%(const Integer& rhs);

but also

Integer Integer::operator<<(const int& l);
Integer Integer::operator>>(const int& l);
Integer& Integer::operator<<=(const int& l);
Integer& Integer::operator>>=(const int& l);

with the obvious meaning.

The idea is to extend the basic C++ integer types, other than you can change the bitwidth at real time.

Anyway... I'd like to overload the operator = , that would convert a string object to a Integer object, something like

Integer x = "0xFE3425452783DFEABC34532FCAA"

(you can assume hex numbers are passed as string, so I can omit the prefix 0x)

Here it is the approach I thought I could use

• Input : a string str storing the hex digits

• Output : an Integer object x

  1. Create a map Map m object where the key belong to the set {'0','1',...,'E','F'} and the values are in the set {0,1,...,E,F} (the former are characters, the latter are integers).
  2. For each element in the map store the equivalent integer
  3. Init x = 0 (assume also is already properly sized, eventually if the size is not enough then I can just chop the equivalent string).

  4. For i = 0 ... str_digits.len-1 (the scanning should be from most significant digit to less significant digit).

     4.1. x = x << 4; //Left shifiting

     4.2. x |= m[str[i]]; //Implicit casting performed

  5. return x

I know I'm missing some details but, you can assume that casting from integer types are implemented, as constructors, overload of every type of operators are implemented as well excepted for the the specific one I want to implement. Here there are my questions:

1. Is my algorithm correct?
2. Assuming it is correct is specifically the digit storing part implemented using Map data structure efficient? What concerns me a bit is the computational cost of fetching a digit, because in case where the base is high this approach could possibly be not efficient, right? What would you recommend otherwise?

Answer 1

Is my algorithm correct

If I ignore some minor glitches like writing {0,1,...,14,15} instead of {0,1,...,E,F}, it looks correct at a first glance. But honestly, implement it and use a debugger, the code will probably be not much longer that your text above.

is specifically the digit storing part [..] efficient?

If you mean by "Fetching a digit" the operation m[str[i]], using a hashmap makes this an O(1) operation, so that is not the bottleneck. But the operation 4.1 will probably have a running time proportional to the length of x which is proportional to str_digits.len, and putting this into a loop with str_digits.len iterations results in an O(N²) operation.

Is this efficient? Not as efficient as it could be, of course. But you should better ask yourself "is it efficient enough for my purpose", and that is something you can only find out by profiling.

Answer 2

The map is not particularly efficient, compared to the simple arithmetic to convert a character representing a hex digit to its numerical equivalent. Check out the ASCII code and you'll see that.

Further (though I would use arithmetic instead of a map) the map is constant, so could be constructed ahead of time and shared instead of being constructed as part of the conversion algorithm.

If the shift itself involves a loop, then as others are pointing out, that ends up being a doubly nested loop. However, the number of digits and bits is not likely to be large enough to make a difference, unless you're getting into thousands to millions of digits.

Also, the number of iterations of the inner loop, assuming you use 64-bit integers internally, would be the size of the current value of the conversion in progress log 64, so not that bad IMHO.

Still, to address the inner loop, you could convert groups of 16 digits at a time to 64-bit integers and then accumulate those into the big integer (so you'd only need to do a big integer shift every 16 digits)...

Answer 3

Execution time is quadratic in the number of digits without any need. Considering that even multiplication and division can be done much faster than that, it's quite bad.