1

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?
  • 1
    When talking about integers, you do not mean "multiple precision", you mean "arbitrary size", don't you? – Doc Brown Feb 6 '17 at 13:32
  • @DocBrown, yes. That's what I mean. – user8469759 Feb 6 '17 at 16:09
4

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.

  • What's N in your notation? – user8469759 Feb 6 '17 at 15:16
  • @user8469759: the number of digits. Note it does not matter if you pick binary digits or base 16 digits or base XYZ digits. – Doc Brown Feb 6 '17 at 15:27
  • About 4.1 : this can be likely breaking down by knowing which digit will move. The first time you won't move any, the second time you will only move the 4 weak bits, then 8 etc. However OP will have to use a dedicated function instead of using the overload of an operator – Walfrat Feb 6 '17 at 16:11
  • I'm still not sure of what approach you're proposing. I'm probably missing something. I got that I could use arithmetic (ascii code) to avoid the use of a map, which is ok. I'm not sure about the rest. – user8469759 Feb 7 '17 at 11:32
  • @user8469759: you map access is not the bottleneck (at least not in terms of big-O), so I suggest you don't optimize this. For learning purposes, you could optimize step 4.1, if you think you really think you need something to optimize, that is what causes the quadratic running time. But my actual proposal is to implement the whole thing in code and measure the running time before investing any effort in optimizations you probably don't need. – Doc Brown Feb 7 '17 at 11:39
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)...

1

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.

  • Could you suggest an alternative? – user8469759 Feb 6 '17 at 11:28
  • Also why the execution time is quadratic? Assuming you have to convert a number with m digits taken from a set of n digits, and assuming m >> n isn't the cost m ln n? – user8469759 Feb 6 '17 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.