[Redwoood]

Ctn,

do I understand this correctly?

You have one specific string and want to encode it as efficiently
as possible?
Well, this is different from general compression, where you don't know in advance what you have to compress.
( and in which case you can't do better than log_2(n) if you require a fixed size encoding)

In the constant case (ie constant string -> efficient encodig ) it is absolutely possible to store it in a smaller space. (depending upon the inherent redundancy of this specific string)

What string do you have to encode?

However, keep in mind that in order to find a clever algorithm to
calculate the original string from your 'seed' you introduce a lot of code into your program.
So, let's say you have a 20 byte string, and somehow you bring it down to a 2 byte 'seed', you have to do the 'decoding' in less than 18 + (length of machine code for function call for straight-forward implementation)

so let's say the length ( load registers etc., CALL routine ) is 16 bytes (should be doable)

hence your decoder must be smaller than 34 bytes total machine code length. Otherwise it would be more efficient to save the string itself and use the straight-forward approach.

Bye

Redwoood

 

[Ctn]

Quote:

Originally posted by Redwoood Ctn, do I understand this correctly? You have one specific string and want to encode it as efficiently as possible? Well, this is different from general compression, where you don't know in advance what you have to compress. ( and in which case you can't do better than log_2(n) if you require a fixed size encoding) In the constant case (ie constant string -> efficient encodig ) it is absolutely possible to store it in a smaller space. (depending upon the inherent redundancy of this specific string) What string do you have to encode? However, keep in mind that in order to find a clever algorithm to calculate the original string from your 'seed' you introduce a lot of code into your program. So, let's say you have a 20 byte string, and somehow you bring it down to a 2 byte 'seed', you have to do the 'decoding' in less than 18 + (length of machine code for function call for straight-forward implementation) so let's say the length ( load registers etc., CALL routine ) is 16 bytes (should be doable) hence your decoder must be smaller than 34 bytes total machine code length. Otherwise it would be more efficient to save the string itself and use the straight-forward approach. Bye Redwoood

i did log_e(64)

opps

yap one specific string

among others

Wow sounds impressive

but Im abit confused.
I'll be coding it in straight forward c++ and prob wont be touching registers. The code length isnt that important as long as it doesnt take much more than 15ms to encode/decode.

One thing I dont understand is that how do you bring a 20byte interger string down to a 2byte 'seed'? That's 10x compression !!!! kick arse

could you give me a simple example of this? I just need a rough idea

thanks

 

[TerriblySorry]

Consider that most pseudo-random number generators are in fact sequence generators which perform 1 or more mathematical and/or logical operations on a seed. Here's a simple example:

extern u16 seed;

u16 prng( void )
{
return( seed++ );
}

If - and it's a big if - you have the sequence "1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,2 0" then all you need to do is "seed=0" then call prng 20 times, storing each return value in a string or array or something.

For more complex sequences, you need a prng that's capable of generating a much more varied sequence. A good example would be a pi generator, where each call to the function would return the next digit in the math comp 22/7.

Course, the longer the string you want to "compress" in this way the less likely you'll be able to find a seed that works. But for low compression rates this can do the trick.

 

[Ctn]

ahh i c what you mean now

but i not every msg to be sent is going to be the same

so you would need to send the seed + the algorithm along?
eeek sounds like its gonna exceed 5 bytes easy...

 

[TerriblySorry]

You'd just need to send the seed. The prng should already be a constant in both systems.

For different messages, you'd need to send a different seed.

 

[Ctn]

ahhh i get ya

 

[Redwoood]

It would be a lot easier, if you could give an example for the kinds
of messages you want to exchange


also, how many different messages are there?

 

[Ctn]

Ill get right back to u

Could we correspond via email?

so far only a few but will have more.

 

[Redwoood]

sure no prob.

you can send me an email through head-fi

(don't like to post it publicly, spam-crawlers everywhere )

BTW:
If you have a limited number of predefined messages you want to send, you can count them and instead of sendig the message, you send their number.

Gives you 2^30 possible different messages (which is a lot more than you would ever want to)


Bye


Redwoood

 

[Ctn]

k

that was my fall back plan actually =)
actually it isnt enuff hehe..just enuff to do abit

but ill formulate my Q better and mail u tomororw

 

[Audio-Me]

Math nerds! I hate Calculus...

I do some amateur html coding, that's about it.

 

[Ctn]

ack call me nething but a math nerd

i hate math !!!!!