Science and Technology news... :: View topic

Generic Usenet Account · Guest

Could someone kindly answer the following two questions I have
regarding base64 encoding:
(1) What is the time-complexity of the base64 encoding/decoding
process?
(2) On an average, what is the size of the encoded data in relation to
the original (i.e. binary) data?

Thanks in advance,
KP Bhat

Stuart Caie · Guest

Generic Usenet Account wrote:
[quote](1) What is the time-complexity of the base64 encoding/decoding
process?
[/quote]
O(n)

[quote](2) On an average, what is the size of the encoded data in relation to
the original (i.e. binary) data?
[/quote]
Encoded data is a 35% increase over the original data.

Regards
Stuart

Mark Crispin · Guest

On Fri, 12 Sep 2003, Generic Usenet Account wrote:
[quote]Could someone kindly answer the following two questions I have
regarding base64 encoding:
(1) What is the time-complexity of the base64 encoding/decoding
process?
(2) On an average, what is the size of the encoded data in relation to
the original (i.e. binary) data?
[/quote]
Ah, September. The start of a new school year.

The answer to question (1) is that it depends upon the processor chip. A
64 bit chip will handle the data four times as fast; twice between the
entire data fits, and twice because of the efficiency of not having to
split the data.

The answer to question (2) is that the size of the encoded data is
inversely proportional to the original data due to the patented
compression mechanism used by BASE64.

If you don>t believe these answers, then read RFC 2045 where BASE64 is
specified and the answers to your question become obvious. Otherwise,
just submit the answers as-is on your homework, and you>ll get the grade
that you deserve.

-- Mark --

http://staff.washington.edu/mrc
Science does not emerge from voting, party politics, or public debate.
Si vis pacem, para bellum.

Dale King · Guest

"Mark Crispin" <mrc@CAC.Washington.EDU> wrote in message
news:Pine.LNX.4.60.0309121100070.26627@shiva0.cac.washington.edu...
[quote]On Fri, 12 Sep 2003, Generic Usenet Account wrote:
Could someone kindly answer the following two questions I have
regarding base64 encoding:
(1) What is the time-complexity of the base64 encoding/decoding
process?
(2) On an average, what is the size of the encoded data in relation to
the original (i.e. binary) data?

Ah, September. The start of a new school year.

The answer to question (1) is that it depends upon the processor chip. A
64 bit chip will handle the data four times as fast; twice between the
entire data fits, and twice because of the efficiency of not having to
split the data.
[/quote]
No, time complexity does not depend on processor chip. The answer is still
O(n). You can manipulate the constants with a different processor, but the
asymptotic time complexity is not affected. The relationship is linear.
--
Dale King

Lyndon Nerenberg · Guest

[quote]"Mark" == Mark Crispin <mrc@CAC.Washington.EDU> writes:
[/quote]
Mark> Ah, September. The start of a new school year.

Now now. You *know* it>s been September since 1992.

--lyndon

Guest

In comp.compression Dale King <KingD@tmicha.net> wrote:
[quote]"Mark Crispin" <mrc@CAC.Washington.EDU> wrote in message
news:Pine.LNX.4.60.0309121100070.26627@shiva0.cac.washington.edu...
On Fri, 12 Sep 2003, Generic Usenet Account wrote:
Could someone kindly answer the following two questions I have
regarding base64 encoding:
(1) What is the time-complexity of the base64 encoding/decoding
process?
(2) On an average, what is the size of the encoded data in relation to
the original (i.e. binary) data?

Ah, September. The start of a new school year.

The answer to question (1) is that it depends upon the processor chip. A
64 bit chip will handle the data four times as fast; twice between the
entire data fits, and twice because of the efficiency of not having to
split the data.

No, time complexity does not depend on processor chip. The answer is still
O(n). You can manipulate the constants with a different processor, but the
asymptotic time complexity is not affected. The relationship is linear.
[/quote]
Before you correct him, go back and read what he wrote again.
Carefully. The entire post. Then ask yourself "How was he answering
the question?" and see if the answer is appropriate.

--

That>s News To Me!
newstome@comcast.net

Generic Usenet Account · Guest

Stuart Caie <kyzer@4u.net> wrote in message news:<3f62082e$0$261$cc9e4d1f@news.dial.pipex.com>...
[quote]Generic Usenet Account wrote:
(1) What is the time-complexity of the base64 encoding/decoding
process?

O(n)

(2) On an average, what is the size of the encoded data in relation to
the original (i.e. binary) data?

Encoded data is a 35% increase over the original data.

Regards
Stuart
[/quote]
Thanks to everyone who responded.

I wonder what the "increase factor" is for other binary to text
encoding schemes like UUEncode, XXEncode, Binhex, Quoted-Printable etc
(list gleaned from http://www.xceedsoft.com/products/binEncod/index.htm).
Also, is there any other prominent binary to text encoding scheme
that I left out?

Regards,
KP Bhat

Florian Rehnisch · Guest

o Generic Usenet Account <usenet@sta.samsung.com>:

[quote]I wonder what the "increase factor" is for other binary to text
encoding schemes like UUEncode, XXEncode, Binhex, Quoted-Printable etc
(list gleaned from http://www.xceedsoft.com/products/binEncod/index.htm).
[/quote]
I wonder why people don>t use google for looking up the web. In
less than 4mins I found
http://www.fpx.de/fp/Software/UUDeview/Introduction.html
in the uudeview homepage. You will find there a brief
description for these formats. uuencode, xxencode, BinHex are
``three in four'' encodings like base64. So increase factor is
about the same.

QP is completely different. Each non-ascii character will (ascii
chars may) be encoded to their hex-representation (i.e. `=FC'
for the german u-umlaut, `ü'). Depending on input data, there
is an increase of encoded data beetween 0% and 200%.

A rule when to use base64 or quoted-printable has been discussed
here before.

For details on base64 or QP read rfc2045, like Mark told you.

[quote]Also, is there any other prominent binary to text encoding scheme
that I left out?
[/quote]
yEnc. Different story.

flori

Stuart Caie · Guest

Generic Usenet Account wrote:
[quote]Also, is there any other prominent binary to text encoding scheme
that I left out?
[/quote]
- btoa and btoa5
- BinHex 1.0 (DL), BinHex 2.0 (HEX), BinHex 3.0 (HCX)
- FSCode
- ish
- bcode
- BOO
- abe
- ship

Regards
Stuart

Dale King · Guest

<newstome@comcast.net> wrote in message
news:yHq8b.424393$YN5.285929@sccrnsc01...
[quote]In comp.compression Dale King <KingD@tmicha.net> wrote:
"Mark Crispin" <mrc@CAC.Washington.EDU> wrote in message
news:Pine.LNX.4.60.0309121100070.26627@shiva0.cac.washington.edu...
On Fri, 12 Sep 2003, Generic Usenet Account wrote:
Could someone kindly answer the following two questions I have
regarding base64 encoding:
(1) What is the time-complexity of the base64 encoding/decoding
process?
(2) On an average, what is the size of the encoded data in relation
to
the original (i.e. binary) data?

Ah, September. The start of a new school year.

The answer to question (1) is that it depends upon the processor chip.
A
64 bit chip will handle the data four times as fast; twice between the
entire data fits, and twice because of the efficiency of not having to
split the data.

No, time complexity does not depend on processor chip. The answer is
still
O(n). You can manipulate the constants with a different processor, but
the
asymptotic time complexity is not affected. The relationship is linear.

Before you correct him, go back and read what he wrote again.
Carefully. The entire post. Then ask yourself "How was he answering
the question?" and see if the answer is appropriate.
[/quote]
I read it again and my answer is still unchanged. Time complexity does not
depend on the processor chip. The execution time may be sped up with a
different processor, but the asymptotic time complexity does not change.
Time complexity does not measure absolute execution time, but the
relationship of execution time to input size.

--
Dale King

Kjetil Torgrim Homme · Guest

[Dale King]:
[quote]
newstome@comcast.net> wrote:
Before you correct him, go back and read what he wrote again.
Carefully. The entire post. Then ask yourself "How was he
answering the question?" and see if the answer is appropriate.

I read it again and my answer is still unchanged.
[/quote]
then you are as dense as Mark Crispin secretly hoped the student would
be.

--
Kjetil T. | read and make up your own mind
| http://www.cactus48.com/truth.html

Guest

In comp.compression Dale King <dale[dot]king@thomson.net> wrote:
[quote]newstome@comcast.net> wrote in message
news:yHq8b.424393$YN5.285929@sccrnsc01...
In comp.compression Dale King <KingD@tmicha.net> wrote:
"Mark Crispin" <mrc@CAC.Washington.EDU> wrote in message
news:Pine.LNX.4.60.0309121100070.26627@shiva0.cac.washington.edu...
On Fri, 12 Sep 2003, Generic Usenet Account wrote:
Could someone kindly answer the following two questions I have
regarding base64 encoding:
(1) What is the time-complexity of the base64 encoding/decoding
process?
(2) On an average, what is the size of the encoded data in relation
to
the original (i.e. binary) data?

Ah, September. The start of a new school year.

The answer to question (1) is that it depends upon the processor chip.
A
64 bit chip will handle the data four times as fast; twice between the
entire data fits, and twice because of the efficiency of not having to
split the data.

No, time complexity does not depend on processor chip. The answer is
still
O(n). You can manipulate the constants with a different processor, but
the
asymptotic time complexity is not affected. The relationship is linear.

Before you correct him, go back and read what he wrote again.
Carefully. The entire post. Then ask yourself "How was he answering
the question?" and see if the answer is appropriate.

I read it again and my answer is still unchanged. Time complexity does not
depend on the processor chip. The execution time may be sped up with a
different processor, but the asymptotic time complexity does not change.
Time complexity does not measure absolute execution time, but the
relationship of execution time to input size.
[/quote]
Sigh. I really thought you>d get it, but I guess not. Re-read the
response AGAIN, keeping in mind that Crispin might not have been
seriously trying to answer the question.

Usually Brits are characterized as having an understated delivery of
comedy that many Americans just miss. I wonder if Mark is British,
because it certainly went right over your head!

--

That>s News To Me!
newstome@comcast.net

Mark Crispin · Guest

On Tue, 16 Sep 2003, Kjetil Torgrim Homme wrote:
[quote][Dale King]:
I read it again and my answer is still unchanged.
then you are as dense as Mark Crispin secretly hoped the student would
be.
[/quote]
I>m more amazed that he didn>t object to the second part of the answer
(the one about the data size being inversely proportional to the original
data due to the patented compression mechanism used by BASE64...).

Then again, I have to remind myself that RFC 748 (which I wrote in my
younger and wilder days) was the only RFC specifically marked in the RFC
index with "note date of issue." :-)

-- Mark --

http://staff.washington.edu/mrc
Science does not emerge from voting, party politics, or public debate.
Si vis pacem, para bellum.

Mark Crispin · Guest

On Tue, 16 Sep 2003 newstome@comcast.net wrote:
[quote]Usually Brits are characterized as having an understated delivery of
comedy that many Americans just miss. I wonder if Mark is British,
because it certainly went right over your head!
[/quote]
No, I>m about as American as they come.

This Yankee Doodle has been to London just once, but not on a pony (and I
don>t wear a cap, so I couldn>t stick a feather in it and call it
macaroni)...

Speaking of which, I completely bewildered a poor British gal behind the
counter at a London Starbucks by ordering a "skinny quad grande latte."
Apparently Starbucks doesn>t teach its foreign employees how to speak
Seattle...

-- Mark (who someday hopes to afford a bespoke Purdey...)

http://staff.washington.edu/mrc
Science does not emerge from voting, party politics, or public debate.
Si vis pacem, para bellum.

Kjetil Torgrim Homme · Guest

[Mark Crispin]:
[quote]
Then again, I have to remind myself that RFC 748 (which I wrote in
my younger and wilder days) was the only RFC specifically marked
in the RFC index with "note date of issue." :-)
[/quote]
cool, didn>t know you started that. it did take 12 years before
anyone took up the tradition (RFC 1097). ahead of your time, eh?

--
Kjetil T. | read and make up your own mind
| http://www.cactus48.com/truth.html


www.GetXFactor.com Leading Technology, Science, Agriculture News and information	Part of the Identityscape.com network... getxfactor.com jmoodmusic.com smartbusinesschoices.com mintdepot.com lowfaresalways.com evangelicalview.com shoppingpodder.com soproudlywehail.com webnews.ws currenthumor.com

Science and Technology news... Forum Index -> Compression Forum	Goto page 1, 2 Next
Page 1 of 2