How do you take a number representing a list of items, and divide it into chunks, where the number of chunks is a power-of-two, AND where each chunk also has a power-of-two number of items (where size goes up to a max power of two, so 1, 2, 4, 8, 16, 32, 32 being the max)? Is this even possible?
So for example, 8 items could be divided into 1 bucket (power of two bucket) with 8 items (power of two items):
[8]
9 items could be:
[8, 1]
That works because both numbers are powers of two, and the size of the array is 2 (also a power of two).
Let's try 11:
[8, 2, 1]
Nope that doesn't work. Because the size of the array is 3 which is not a power of two, even though it adds to 11. How about this?
[4, 4, 2, 1]
That works! It's 4 elements which is a power of two.
[2, 2, 2, 1, 1, 1, 1, 1]
That also works, since there are 8 buckets (8 is a power of two), with 1 or 2 items each (each a power of two). But [4, 4, 2, 1] is better because it's shorter.
I guess an even better one (after getting comments) would be this, though I didn't see it the first time around:
[8, 1, 1, 1]
That one is short, and also starts with the largest number.
So following this pattern, here are some other numbers:
13:
[8, 1, 1, 1, 1, 1] // no, 6 not power of 2
[8, 2, 1, 1, 1] // no, 5 not power of 2
[8, 2, 2, 1] // yes, 4 is power of 2
[8, 4, 1] // no, 3 not power of 2
14:
[8, 2, 2, 2]
15:
[8, 4, 2, 1]
16:
[16]
18:
[16, 2]
200:
[32, 32, 32, 32, 32, 32, 4, 4]
When the size of the first layer of buckets in the bucket tree grows to longer than 32, then it nests. So take the number 1234 for example. This can be represented by 38 32's followed by 16 followed by 4.
[32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 16, 4]
But now the bucket size is 40 items long, which isn't a power of two AND it's greater than 32. So it should be nested! I can't quite visualize this in my head, so sorry if this isn't a perfect example, I think you can get the gist of what I mean though.
// the parent "x" is 2 in length
x = [a, b]
// child "a" is 32 in length
a = [32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32]
// child "b" is 8 in length
b = [32, 32, 32, 32, 32, 32, 16, 4]
Taken another layer up, say we have a very large number (I don't know what the minimum large number is) that requires another layer of nesting. What we can say about this layer is that, x will be 32 in length, but we will also have a y that is at least 1.
_x_ = [a, b, c, d, e, f, g, h,
i, j, k, l, m, n, o, p,
q, r, s, t, u, v, w, x,
y, z, a2, b2, c2, d2, e2, f2]
_y_ = [a3]
a = [32, 32, 32, ..., ?]
...
f2 = [32, ..., ?]
Then once we have _x_, _y_, _z_, ... 32 total of these, we build another layer on top.
What is an algorithm/equation that will take a number and divide it into this tree of buckets / item sizes that are all powers of two, up to a max (in this case, 32)?
A subgoal is to minimize the number of levels. There isn't a specific limit, but I am imagining no more than 1 million or very max 1 billion nodes in the entire runtime, so it seems like you'll only have 3 or 4 levels probably, I don't know exactly how to calculate it.
This is going to be used for array lookup. Essentially I am breaking apart a single, large, arbitrarily sized "contiguous" array into small contiguous chunks with size power-of-2 up to 32 in length. This balances lookup performance (i.e. fits within cpu cache), with memory fragmentation.
Update:
I think trying to incorporate this somehow to build up that nested tree I'm trying to describe will help. The last thing now missing is getting the nested arrays to be properly sized to power-of-two values...
The best I have been able to do so far is this:
console.log(spread(74))
console.log(spread(85))
console.log(spread(87))
console.log(spread(127))
console.log(spread(1279))
console.log(spread(12790))
console.log(spread(127901))
function spread(n) {
if (n == 0) {
return [0, 0, 0, 0, 0, 0]
}
let array = []
let r = split(n)
while (r[0] > 31) {
array.push([32, 0, 0, 0, 0, 0])
r[0] -= 32
}
array.push(r)
let s = sum(r)
if (!isPowerOf2(s)) {
let x = pow2ceil(s)
let i = 1
while (i < 5) {
if (r[i] > 1) {
i++
break
}
i++
}
if (i == 5) {
i = 0
}
main:
while (true) {
while (r[i]) {
r[i + 1] += 2
r[i]--
s += 1
if (s == x) {
break main
}
}
i++
}
}
if (array.length == 1) {
return array[0]
} else if (array.length < 33) {
return array
} else {
return divide(array, 32)
}
}
function sum(arr) {
let i = 0
arr.forEach(x => {
i += x
})
return i
}
function split(n) {
const r = [0, 0, 0, 0, 0, 0]
let u = 32
let i = 0
while (u > 0) {
while (n >= u) {
r[i]++
n -= u
}
i += 1
u >>= 1
}
return r
}
function isPowerOf2(v) {
return v && !(v & (v - 1))
}
function pow2floor(v) {
var p = 1;
while (v >>= 1) {
p <<= 1;
}
return p;
}
function pow2ceil(v) {
var p = 2
while (v >>= 1) {
p <<= 1
}
return p
}
function divide(data, size) {
const result = []
const upSize = data.length / size;
for (let i = 0; i < data.length; i += size) {
const chunk = data.slice(i, i + size);
result.push(chunk)
}
if (result.length > size) {
return divide(result, size)
}
return result;
}
