FatStack.js - A stack implementation using Bignums.

Forewarning: The tests conducted in this article are not proof of anything.

We all have lots of thinking (or sleeping) time while traveling. I find these times to be the best for really thinking an idea through. While I was on a charter bus, I just randomly thought about something: we store data in 8 bit chunks - why can't we store data in 256 number "chunks"? Would this be performant over other ways we use data in traditional list structures (I doubted it)? This evening, I decided to give it a try.

Before I move forward I want to say that I HIGHLY doubt I'm the first to think of this, but a quick search brought up nothing, so I figured hey, why not write a good piece on something interesting.

The idea is simple: use the "space" provided by "number space" to store data. I take our initial number, which is zero, and multiply it by our element's "space", multiplied by the current index.

r = 0
r = r * (1000 * 0)
r = 0

Alright, simple for the first index. Then we add our first piece of data.

r = r + 214
r = 214

Great. Lets do this a few more times.

r = r * (1000 * 1) + 4
r = 214004

OK, so we see a nice visual indication that our numbers are "in" the data store. We see our 214, and 004. Hold on a minute though, how do we access our element? With modulus:

b = r % 1000
b = 4

We've defined peek and push. What about pop?

r = r / 1000
r = 214.004

And now we're back at 214.004. To get 214 itself, we just use peek!

Awesome, so now we have a stack to play with! Using this with a zipper (I haven't thought or looked to far in this, so bear with me) we can implement an array with random insertion. For the sake of brevity though (and laziness), I won't.

Instead lets think about some big waste going on. We can store values from 0 to 999 in each "element" of this "list" (well, it's really a stack). With 8-bit data though, we only store 0-255. How can we fix this? Well, after some checking, turns out changing the size of our "allowed values" set still allows this to all work, while being optimal.

Excuse if my notation is off here. Below I present push, pop, peek, and extract (gets the value at any index) as equations:



S is the set of all possible values that will be stored.
l is the length of the set S.
b is a number between 0 and 255.
r (i - 1) is pop. It removes the top of the stack.
r (i + 1) is push. It adds to the top of the stack.
r (i) is peek. It looks at the top of the stack.
r (n) is extract. It looks at any element in the stack.

You could probably make a few more variants but again, I don't want to waste too much time here. What I want is to see how it performs against a proper stack implementation. In order for this to be possible though, the programming language must have big number support or a library that offers it. I have an idea of how big number implementations work, and in theory, I think the big number stack will excel with smaller data sets, and fall behind larger, since calculation has to trickle up to the most significant digits. Lets see how it does.

PP stands for "push, pop"

Apparently, pretty terrible in all cases. It's almost, what, 500% slower (bignum vs native push-pop)?

Comments

Popular Posts