Solved

# Stream of bytes to decimal numerals?

Posted on 2009-02-19
482 Views
Hi,

having (infinite) stream of bytes from LSB, how can I produce (infinite) stream of decimal numerals? The stream of bytes represents an extremely big integer number. The decimal numerals represent decimal representation of the number.

Thanks,
Petr

P.S. whatever language, pseudocode i OK. I am just somehow stupid after the lunch ;)
0
Question by:pepr

LVL 84

Expert Comment

here is one possible algorithm
http://en.wikipedia.org/wiki/Arithmetic_coding
0

LVL 53

Expert Comment

Unfortunately, there's no power of 2 that is also a power of 10. So, every bit of the stream can modify the low-order decimal digit. Or in other words, you have to wait until all bits on the stream have been received before you know the decimal representation of the number.
0

LVL 53

Expert Comment

You could of course use something like BCD.
0

LVL 53

Expert Comment

(there's also no power of 2 that is a multiple of 10, so you can't use that either)
0

LVL 84

Expert Comment

depending on what you mean by  a decimal "representation" of the number
Arithmetic coding can give you a representation, but the final decimal numerals when interpreted as a decimal number may not be the same number as the stream of bytes interpreted as a base 256 number.
You could also represent the bytes using only the decimal numerals from 0 to 7
0

LVL 28

Author Comment

Well, Infinity08 probably understands why I asked here :)

To ozo, I could say the same when having the stream of bits. I really want to get the numerals from 0 to 9 that, when concatenaded, would represent the number like a*10^0 + b*10^1 + c*10^2 + ...

In other words, I want to accept numerals in one encoding (here base 256) and produce the numerals in another encoding (here base 10). What is important, I want to do that on-the-fly. If the input stream ends, it is possible to accept extra zeros until I am sure that the internal state of the algorithm can produce also only zeros on output.
0

LVL 53

Accepted Solution

Unfortunately, there's no way this can work, since the next byte (bit) on the stream can modify any and all of the decimal digits.

The only way out, is to send the bytes in blocks representing values that are a power of 10. For example, each block of 4 bytes represents values between [0, 1000000000[ only. Any value outside of that range is an error. This limits the throughput of the stream, but it allows you to generate the decimal representation on-the-fly (per block of x bytes).
0

LVL 28

Author Closing Comment

Yes, exactly. It matches my own observation. Say converting binary stream to the base 10 is impossible, because 2^n alway affect the 10^x order constant.
0

LVL 84

Expert Comment

If we are allowed to combine this
> the next byte (bit) on the stream can modify any and all of the decimal digits.
with
> If the input stream ends, it is possible to accept extra zeros
and ones
> until I am sure that the internal state of the algorithm can produce also only zeros on output.
then we may be able to represent a decimal number that start with the output corresponding to a binary that starts with the input, (but not necessarily continuing with all 0's)
It's actually easier to do this if the numerals from 0 to 9 that, when concatenaded, would represent the number like a*10^-0 + b*10^-1 + c*10^-2 +
and the numerals from 0 to 1 that, when concatenaded, would represent the number like a*2^-0 + b*2^-1 + c*2^-2 + ...
(but you can also think of them as being scaled by an appropriate power of 2 or 10)
To avoid having to do all calculations in infinite precision, arithmetic coding effectively allows a bit of fudging in the 10^-n and 2^-m values. while maintaining the correspondence between input and output.
0

LVL 28

Author Comment

ozo: Do you say that it would be possible to do the conversion if the stream started with the most significant bit? It could be quite acceptable for my purpose. Basically, I need only one way transformation that could have also a form of signature (i.e. not neccesarily exact value). However. longer input should produce longer output and the same input should produce the same output.

Basically, I have a (large) buffer of bytes and I want to decide later how many decadic digits I want to get.

If you (both) have any idea how to do that, we can formulate the question and I will ask it (as a new one). I will ask it anyway. You can just suggest... You know ;)
0

LVL 53

Expert Comment

>> it would be possible to do the conversion if the stream started with the most significant bit?

That's possible, if you know the length of the stream. ie. you need to know the bit position of that MSB. If you know that, you can progressively determine the most significant decimal digit first, etc.
0

LVL 53

Expert Comment

>> we can formulate the question

For me, there's no need to open a new question. If you want, you can re-open this one :)
0

LVL 28

Author Comment

Well, I like when the discussions are rather separated if the topic changes :) This is one of the reasons why I have found EE so valuable.

See http:Q_24161121.html

P.S. When having "unlimited" account, I prefer to spend. I wish I could do that with money :D
0

LVL 53

Expert Comment

Fair enough :)
0

## Featured Post

Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
Need more eyes on your posted question? Go ahead and follow the quick steps in this video to learn how to Request Attention to your question. *Log into your Experts Exchange account *Find the question you want to Request Attention for *Go to the e…
This video discusses moving either the default database or any database to a new volume.