[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 486
  • Last Modified:

Stream of bytes to decimal numerals?

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
pepr
Asked:
pepr
  • 7
  • 4
  • 3
1 Solution
 
ozoCommented:
here is one possible algorithm
http://en.wikipedia.org/wiki/Arithmetic_coding
0
 
Infinity08Commented:
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
 
Infinity08Commented:
You could of course use something like BCD.
0
Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

 
Infinity08Commented:
(there's also no power of 2 that is a multiple of 10, so you can't use that either)
0
 
ozoCommented:
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
 
peprAuthor Commented:
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
 
Infinity08Commented:
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
 
peprAuthor Commented:
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
 
ozoCommented:
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
 
peprAuthor Commented:
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
 
Infinity08Commented:
>> 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
 
Infinity08Commented:
>> 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
 
peprAuthor Commented:
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
 
Infinity08Commented:
Fair enough :)
0

Featured Post

Vote for the Most Valuable Expert

It’s time to recognize experts that go above and beyond with helpful solutions and engagement on site. Choose from the top experts in the Hall of Fame or on the right rail of your favorite topic page. Look for the blue “Nominate” button on their profile to vote.

  • 7
  • 4
  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now