Requires
http://www.hiveworkshop.com/forums/j...-codes-188790/
This tutorial will discuss the smallest way to represent a collection of numbers as one number.
In the previous tutorial, numbers were merged with placeholders. It discussed that merging numbers in a smaller base merits a smaller overall number.
Given a constant set of maximums 126, 14, and 444, storing the 1,7,11 using those maximums would give 107011. In binary, it would give 19979.
107011 (b10 placeholders)
19979 (b2 placeholders)
Why on earth is the binary number so much smaller than the radix number?
Let's look back on the highest possible number that can be stored using the maximums.
12614444 (just the numbers merged together). Could this same digit also store 99999999 in the same amount of space? It certainly could. In binary, 19979 is 100111000001011. Could this not also be 111111111111111 in the same amount of bits?
This means, placeholders actually waste space. 107011 wastes 999999-107011, or 892988.
In binary, 100111000001011 has a max storage of PA7, but only has a max value of FEZ, thus wasting space. This wasted space is not nearly as noticeable in binary as placeholders are much smaller than those in radix, but it is there.
Looking back at the set of constants {126, 14, 444}, can this set not represent the max numbers of 3 different bases? Remember that a base is the max number + 1 (because of 0), so {126, 14, 444} could be stored in bases {127, 15, 445}. Rather than allocate a set of placeholders, allocate a base.
Remember that base conversion is all about multiplication, so convert your number into the target base.
Storing 1,7,11
(0*127)+1 (stored) -> 1
1*15 + 7 -> 22
22 * 445 + 11 -> 9801
Not a single bit of wasted information, the number is as compact as possible.
19979 from binary placeholders, 9801 with layered base conversion.
To go back
Code:
9801%445 = 11
(9801-11)/445 = 22
22%15 = 7
(22-7)/15 = 1
Set = {1,7,11}
9801->7K9 (space saved from 199779: 10178)
19979->FEZ (space saved from 107011: 87032)
107011->2AKJ
The larger the set of numbers, the more space that is saved.
This same principal can be applied to multidimensional arrays.
An array a[3,6] could also be represented as a[27] (3*7+6). To go back to the specific indexes, 27%7=6, (27-6)/7=3, a[3,6].
