# Simple Lookup Equation

This topic is 2497 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

The problem is pretty simple I think, for some reason I'm just not sure how to approach it.
I've written a container similar to a deque which resizes similar to std::vector (newSize = oldSize*2 + 1).
I want to make my lookup time O(N).

I need to be able to determine my chunk and chunk sub-index.
For instance, if I look up Container1[4] I would find chunk 2 sub-index 0, and Container2[4]
would find chunk 0 sub-index 4.

 [Container] [CHUNK] [ELEMENTS] Container1 0 1 2 3 4 5 6 7 1 3 7 15 31 63 127 255 Container2 0 1 2 3 4 5 6 7 5 11 23 47 95 191 383 767 

It is also important to note that the initial number of elements in a chunk is arbitrary.

I'm a little embarrassed to ask such a simple math question, but I have been stuck on this one.
Thanks in advance for any help!

##### Share on other sites
The number of elements in chunk 'n' is k*2^(n+1)-1, for given k (k=1 in Container1, k=6 in Container2)

The number of elements in all chunks preceeding chunk 'n' is k*2^(n+1) - 2*k - n

So.

Given your index 'i', the chunk to be looked up is however unfortunately... not solvable

The reason it's not solvable (with elementary functions at least) is that your chunk sizes aren't actually doubling in size, if they were it'd be trivial to find which chunk an index belongs to, and once that is known the sub-index is trivial

##### Share on other sites
I'm not averse the changing the sizing algorithm to be more cooperative.
The amount that it sizes is relatively unimportant, as long as it scales significantly on each resize.

I'm going to mull over your math and see if I can glean inspiration from it. It'd be very helpful to know
the function to find the chunk assuming chunk assuming it was doubling in size.
Both of these functions are very helpful. Thank you!

-edit
I'm starting to think of this as a linear equation, based on your math:
y = k*2[sup]x[/sup]

...So all I need to do is solve for x.

where...
x = chunk index
y = number of elements at x chunks
k = initial number of elements per chunk

### [color=#000000][color=#000000] · log[sub]b[/sub](m), therefore...[/font] x * log[sub]2[/sub](2) = log[sub]2[/sub]( y / k ) x = log[sub]2[/sub]( y / k ) The truncated value of x should be the chunk index. I'm not sure if further simplification can be done, or my math makes any sense, but it seems to work. -edit2 x = log[sub]2[/sub]( y / k + 1 ) ...to compensate for zero-based indexing.

##### Share on other sites
Hi,

I may be a little late to the party, but I think the solution to the problem is f(n) = (k + 1) * 2^n - 1, where n is the chunk index (starting at zero) and k is the number of elements in the first chunk. So, using logarithms like you did above, you get

n = log2((f(n) + 1) / (k + 1))

-Josh

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633736
• Total Posts
3013598
×