storing large integer

Question

Integer : 3322000011111010203100311011211322020110122010113111301101000200

String an integer in bits would required log2 of Integer that is 211.xxxx rounded 212 bits

Some programme on scriptlance says taking square root of this value will result in small, but he requires big deal of money that dont have. sqrt is 57636793900346419278364744407607.475108338

Now log2 (sqrt Integer) = 105.5 bits

But I am worried if we do not store sqrt perfectly we cannot recover back original value,

Question : Can we store this squareroot in 105.5 bits (round it like 13 bytes + 2 bits etc) and later read and square value to get original value back?

Please guide me.

Answer 1

Question : Can we store this squareroot in 105.5 bits (round it like 13 bytes + 2 bits etc) and later read and square value to get original value back?

No. You need to take log_2 of an integer (not a floating point) to see how many bits it needs. Ex: Log_2(256) = 8 bits. That number can be stored as 0x10000000. However, Log_2(256.123456789) ~= 8 bits as well. There is obviously more information in that second number, however.

To get around this, you could multiply your value by a power of 2 or 10 and store that as a integer (this is essentially fixed point: http://en.wikipedia.org/wiki/Fixed-point_arithmetic). So in your example, multiply 57636793900346419278364744407607.475108338 by 10^9 to get the integer: 57636793900346419278364744407607475108338, which is what you would store. Log_2 of that is 135.4, so you need at least 136 bits of information to store that number exactly.

Answer 2

But I am worried if we do not store sqrt perfectly we cannot recover back original value,

Question: Can we store this squareroot in 105.5 bits (round it like 13 bytes + 2 bits etc) and later read and square value to get original value back?

No.

Basically, you're asking whether you can take 212 bits of information, compress them into 106 bits by taking the square root, and then be able to recover the original data without loss. This cannot be done.

If it were possible, you could apply the same technique to the 106 bits to compress them down to 52 bits, then to 26, and so on, eventually compressing an arbitrary amount of data into less than one bit, while still being able to recover the original data.

Answer 3

You cant do that since, square root of a number is not an int always.And you Cant store the floating point numbers accurately. So, the problem is : 1. if you store the square root, then you will have to store the floating point number. which itself takes more space and as well is inaccurate. 2. As pointed by AIX, if its possible, then you can iterate the same procedure and then can restore arbitrary long numbers in only , possibly 2 bytes only. One byte for storing the value and another for storing how many times to square.