-1

Let's say you have a very long binary-word (>64bit), which represents an unsigned integral value, and you would like to print the actual number. We're talking C++, so let's assume you start off with a bool[ ] or std::vector<bool> or a std::bitset, and end up with a std::string or some kind of std::ostream - whatever your solution prefers. But please only use the core-language and STL.

Now, i suspected, you must evaluate it chunkwise, to have some intermediate results, that are small enough to store away - preferably base 10, as in x·10k. I could figure out to assemble the number from that point. But since there is no chunk-width that corresponds to the base of 10, I don't know how to do it. Of course, you can start with any other chunk-width, let's say 3, to get intermediates in the form of x·(23)k, and then convert it to base 10, but this will lead to x·103·k·lg2 which obviously has a floating-point exponent, that isn't of any help.

Anyway, I'm exhausted of this math-crap and I would appreciate a thoughtful suggestion.

Yours sincerely,
Armin

ndrey
  • 35
  • 5
  • 1
    Search Stack Overflow for "binary to decimal conversion" or similar. But note that in general, every decimal digit is dependent on every binary digit. – Oliver Charlesworth Jan 04 '13 at 20:18
  • 1
    This problem is _so much harder than you'd think_. I'd say use a bignum library for the task, or give up. Otherwise, you have to implement and do lots and lots of bidnum division and modulo to get the answer. Is rounding allowed? If rounding is allowed, then it's easy to convert it to a `double`. – Mooing Duck Jan 04 '13 at 20:24
  • @MooingDuck it can't be that hard, can it? Have you tried it before? – Seth Carnegie Jan 04 '13 at 20:25
  • @SethCarnegie: Yes, I tried to write `std::ostream& operator<<(std::ostream&, const bignum&)` once, and it turned out to be a nightmare. – Mooing Duck Jan 04 '13 at 20:26
  • 1
    Another option is to forget base 10, and simply print as hex, or base64, both of which are trivial. – Mooing Duck Jan 04 '13 at 20:27
  • Shouldn't be too hard, if you you can afford to buffer the output so that it can be built from least-significant decimal digit to most significant decimal-digit – Bwmat Jan 04 '13 at 20:28
  • This actually seems a lot harder than it looks. I cannot come up with a good solution off the top of my head...anyone care to provide some hints here in the comments? – im so confused Jan 04 '13 at 20:29
  • @MooingDuck did you ever finish it or did you give up and use a library? – Seth Carnegie Jan 04 '13 at 20:29
  • @SethCarnegie: I actually did get it working eventually, but bignum division took a _lot_ of work to get working correctly, and the whole procedure was _very_ slow. – Mooing Duck Jan 04 '13 at 20:31
  • 2
    @AK4749, MooingDuck: Conceptually, this isn't very hard (see e.g. my answer [here](http://stackoverflow.com/a/10180768/129570)). Once you've defined a `bignum` class and defined some arithmetic overloads for it, the code almost writes itself. Doing it efficiently, however, is more challenging... – Oliver Charlesworth Jan 04 '13 at 20:31
  • ah yeah, seems like no other way other than bignums from these comments and your answer. I was wondering if there was some trick you could use to fit pieces inside 64 bits. guess not :/ – im so confused Jan 04 '13 at 20:34
  • 2
    @AK4749: See also http://en.wikipedia.org/wiki/Double_dabble. – Oliver Charlesworth Jan 04 '13 at 20:35
  • 1
    Hey, why do you guys downvote my question? Just because it's not easy to answer doesn't mean it's a bad question, am I right? It's my first post on SO, for god's sake. – ndrey Jan 04 '13 at 20:39
  • 1
    @armintamzarian: Your question seems reasonable (although there are probably duplicates); so I don't understand the downvotes either. – Oliver Charlesworth Jan 04 '13 at 20:40
  • @MooingDuck: 3rd party libraries are not an option. I have nothing against rounding if you can provide an example. – ndrey Jan 04 '13 at 20:44
  • 1
    @armintamzarian: it's probably downvoted because many many people have asked how to print bignums on stackoverflow before. This is definitely a duplicate question, which shows that you did not show enough research effort. – Mooing Duck Jan 04 '13 at 20:58
  • 1
    Represent your numbers as `std::string`. To convert from binary, you only need two operations, multiply-by-two and add-one (which you can combine into one operation, but lets get the basics working first). Both are trivial to implement if you know how to multiply a long number by two on a piece of paper. – n. m. could be an AI Jan 04 '13 at 21:02
  • @Oli I totally understand the downvotes. They’re not for the question, they’re for the attitude (I also abhor the decimal chauvinist attitude but that’s an effect of our education system and can’t be blamed on OP). – Konrad Rudolph Jan 04 '13 at 21:12
  • @Konrad: You mean I am an asshole because I would like to read a proper decimal number? Please tell me you're joking. – ndrey Jan 04 '13 at 21:34
  • @armintamzarian No, I didn’t say you were an asshole to begin with. But the “math-crap” ruins an otherwise quite nice question and your attitude in the comments just now isn’t helping the cause. – Konrad Rudolph Jan 04 '13 at 22:04
  • @Konrad: Yeah, but you talked about "decimal chauvinism" and the education system, and this didn't seem to refer to the term "math-crap". By the way, I like math, why else would I reason about these kind of problems? – ndrey Jan 04 '13 at 22:15
  • @armin The decimal chauvinism was just an aside, unrelated to the downvotes or the attitude in the question. I’m just annoyed by the choice of word in “print the actual number”. If you want to print the actual number, just print the binary representation. Every representation is the actual number. Decimal is no more legit than binary or any other base. This is a common mistake when dealing with different bases: decimal is given a somewhat elevated position, as if it were the “true” representation. This shows a deep-rooted misunderstanding of the difference between meaning and representation. – Konrad Rudolph Jan 04 '13 at 22:21
  • @Konrad: I understood the point, you gave a hint about, very well in the first place - just wanted you to explain. Now, if you favor the idea over it's representation, and you are annoyed of people not recognizing it, you shouldn't get to serious about terms like "math-crap", which by itself and read in context, is a representation - an expression of "I tried a lot, couldn't figure out the result". And besides that, I think I disagree. A decimal number isn't just there to serve a chauvinism, it's there for compatibility with everyday life. demanding to ignore it would be chauvinism, right? – ndrey Jan 04 '13 at 23:08
  • I don’t say anywhere that decimal numbers should be ignored. I simply state that it’s wrong to equate “actual number” with “decimal representation” as the question does. – Konrad Rudolph Jan 05 '13 at 00:49

1 Answers1

1

I'm going to assume you already have some sort of bignum division/modulo function to work with, because implementing such a thing is a complete nightmare.

class bignum {
public:
   bignum(unsigned value=0);
   bignum(const bignum& rhs);
   bignum(bignum&& rhs);
   void divide(const bignum& denominator, bignum& out_modulo);
   explicit operator bool();
   explicit operator unsigned();
};

std::ostream& operator<<(std::ostream& out, bignum value) {
   std::string backwards;
   bignum remainder;
   do {
       value.divide(10, remainder);
       backwards.push_back(unsigned(remainder)+'0');
   }while(value);
   std::copy(backwards.rbegin(), backwards.rend(), std::ostream_iterator(out));
   return out; 
}

If rounding is an option, it should be fairly trivial to convert most bignums to double as well, which would be a LOT faster. Namely, copy the 64 most significant bits to an unsigned long, convert that to a double, and then multiply by 2.0 to the power of the number of significant bits minus 64. (I say significant bits, because you have to skip any leading zeros)
So if you have 150 significant bits, copy the top 64 into an unsigned long, convert that to a double, and multiply that by std::pow(2.0, 150-64) ~ 7.73e+25 to get the result. If you only have 40 significant bits, pad with zeros on the right it still works. copy the 40 bits to the MSB of an unsigned long, convert that to a double, and multiply that by std::pow(2.0, 40-64) ~ 5.96e-8 to get the result!

Edit

Oli Charlesworth posted a link to the wikipedia page on Double Dabble which blows the first algorithm I showed out of the water. Don't I feel silly.

Community
  • 1
  • 1
Mooing Duck
  • 64,318
  • 19
  • 100
  • 158
  • @SethCarnegie: Though I speak from experience, that does not mean wisdon. Oli Charlesworth posted a link on how to do it in linear time rather than my crazy slow method. – Mooing Duck Jan 04 '13 at 21:02
  • @MooingDuck: I basically have a bignum class and I implemented most of the arithmetic operations - except for division and modulo. If I understand your rounding-approach correctly, it's an approximation of the result, not an approximation of the intermediates that magically end up in the precise integral result, as I thought. So it's a solution to keep in mind if anything other fails. To try out your remainder-example, I will have to wait until I implemented modulo and division. But thanks for your contribution. – ndrey Jan 04 '13 at 21:10
  • @armintamzarian: Seriously, ignore everything I wrote here about division and look up [Double Dabble](http://en.wikipedia.org/wiki/Double_dabble). – Mooing Duck Jan 04 '13 at 21:11
  • @MooingDuck: Also, it should be possible to do the bignum version with add+multiply only. – Oliver Charlesworth Jan 04 '13 at 21:14
  • @Mooing Duck: Yes, got it. Now, I will have to work through this carefully, but it seems to be the solution I was looking for. – ndrey Jan 04 '13 at 21:17
  • @Oli Charlesworth: It doesn't need to be linear time, since it will only matter if you print stuff out. But if you have a solution, that is faster than double dabble, I wouldn't stop you from showing ;) – ndrey Jan 04 '13 at 21:25