---
Video Title: Lengthening LOOKUP
Description: Theory of Computation
https://uvatoc.github.io/week3

7.4: Lengthening LOOKUP
- Defining a "data structure"
- Recursive circuit implementation of LOOKUP

Nathan Brunelle and David Evans
University of Virginia
---

So the next thing we're going to do,
the next piece of syntactic sugar we're

going to add, is we're
actually going to add

something that looks
kind of like a data structure.

We're going to give a way that we can
actually index into lists next.

We're going to define this function that
we're going to call lookup.

So the idea of lookup is
I hand this function a bit

string, and I hand it a bit
string representing an index.

And it will tell me, in the bit string that
was given, what is the bit at the index.

So given a bit string and an index,
give me the bit at that index.

When we define this function, we're
actually going to define our function in

terms of some value k, where k is
basically telling us how big our index is.

So when I'm describing this function,
I'm not describing just one function,

I'm describing an infinite number of
functions.

One where k is equal to
1, another where k is equal

to 2, another where k is
equal to 3, and so forth.

So the way that this function
is going to work is we're

going to say that I give
you a big long bit string here.

So I'm going to give you this big long bit
string.

How long is it?

Well, we have two components to this bit
string.

We have the string that we're going to be
indexing into.

It's going to be of length 2 to the k for
whatever k was over here.

And we also have the
index we're going to be using

to find the bit, to
look into that bit string.

That index is k bits long.

The subscript k for which
version of lookup we're

talking about matches the
length of the index in bits.

And then our output is
going to be that one bit

at the location that we
indexed in the bit string.

So the idea is that if I give you this bit
string x that's 2 to the k bits long,

and I give you this bit string I that's k
bits long, if I think of I as a natural

number between 0 and 2 to the k minus 1,
if I think of I as a natural number,

I want to return the bit x sub i.

The ith bit of x.

So as an example here, if I have k is
equal to 3, that means I have 8 bits.

So this is bit 0, this is bit 1,
this is bit 2, this is bit 3, 4, 5, 7.

So these are my bits at the various
indices.

I is telling me which bit in this string
to return.

So in this case, I is 2.

So I want to return the thing at index 2,
which means I'm returning the 0 here.

This is the goal of lookup.

We're going to be able to index into a
string.

So the first 2 to the k
bits of our input, that's

considered to be that bit
string we're indexing into.

The last k bits are the index that we're
going to use to pick the bit.

So what we're going to do is I'm going to
show that no matter what k is,

I can always find a NAND cricket, a
NAND circuit, that computes lookup sub k.

And then I'm also going
to show some bound for the

number of gates we're
going to need to do that.

So let's talk about this.

Let's talk about how it is that we can show
that we can find a NAND gate to do lookup.

And we're essentially going to do this by
induction.

So we're going to have
an inductive argument for

why it is that we're
going to be able to do this.

So the idea is that
we're going to define

lookup sub k in terms
of lookup sub k minus 1.

So here we're trying to do our lookup
where k is equal to 3.

And in order to do that,
we're going to define lookup

where k is equal to 3 in
terms of lookup k minus 1.

So we're looking at an index of size 2.

The way that we're going to do this is
we're going to say, well, let's consider

that we're trying to look at index I in
our bit string.

If the first bit of I is 0,
then whatever bit we're

looking for is in the
first half of the string.

So in this case, if I have 0, 1,
2, 3, 4, 5, 6, 7, if the first bit of my

index is 0, then the largest number I
could be talking about is 3.

So I must be talking about something in
the first half of the string.

On the other hand, if the
first bit of my index was

1, the smallest number I
could be talking about was 4.

So whatever bit I'm looking for must be in
the second half of the string.

So once I've established that I must be
looking in the first half of the string,

I can just use the
rest of the index to look

into the half of the
string that I identified.

So now I can use the
last two bits of I and just

do a lookup into the
four bits of the first half.

Whatever bit in the half string we're
indexing with the one shorter index is the

same as whatever we were looking up in the
larger original problem.

So in this case, we're looking at index 2.

So 0, 1, 2, 3.

And we can see that index 2 here was the
index we were looking at there as well.

How is it that we're going to find the
index down here for k is equal to 2?

Well, we can convert that into a lookup
for k is equal to 1.

So let's look at k is equal to 1.

So in this case, we said that our lookup
must be in the second half.

So it must be one of these two.

And our index was 0 in this case.

So what does this look like?

We have two bits in our string,
and we have a one-bit index.

This is 0, 1.

So we're going to be returning this one.

So whenever the input was 0, we return the
first one.

Whenever the index was 1, we return the
second one.

So if this is like I, and this is x sub 0,
and this is x sub 1, then if we do lookup

sub 1 of x0, x1, I, this is going to be
equal to...

Or if I was true in this case,
if I was 1, we went to return x1.

If I was false, we went to return x0.

So lookup sub 1 is just a rewriting of if.

And then once we have lookup sub 1,
we can do lookup sub 2.

Because lookup sub 2, we can just figure
out by looking at one bit of I,

which half to look in.

With two ifs, we're going to be able to do
lookup of 2.

And with lookup of 2, we're going to be
able to do lookup of 3.

And with 3, we can do 4 and so forth.

Yes.

Yeah, so, when I look at the index,
in our example where k is equal to 3,

when I look at my index,
if the first bit of my index

is 0, the largest number
I could be indexing is 3.

The largest value the index could be is 3,
since I knew the first bit was 0.

And all of the indices from 0 to 3 are in
the first half of the bit stream.

If the index was 1, the
number I was representing must

have been at least 4 in
the second half of the string.

And once I've identified
which half I'm in, then

I've got a smaller index
problem to deal with.

This is how we can define lookup.

What does lookup look like when I have a
k-bit index?

So here, my last k bits are the index.

My first 2 to the k bits are my string.

How can I find lookup sub k?

What I'm going to do is I'm going to say,
if the first bit of I was a 0,

then I want to do whatever
the one smaller lookup

problem was on the
first half of the string.

So I start with bit 1 in my index,
rather than bit 0.

And I'm doing a lookup of that index into
the first half of my original string.

Because I must have been looking at a
small index, that first bit being a 0.

My index must have
been small, so I must have

been looking in the
first half of my string.

So I just do a lookup in the first half of
my string.

If, on the other hand, the
first bit was a 1, then I'm

going to be returning
whatever this value is from my if.

So I'm going to be
doing an index, ignoring

the first bit in the
second half of the string.

When we do lookup k, the way that we
figure out the value of lookup sub k is

we're going to do a lookup
sub k minus 1, two lookups

of size k minus 1, and
then which one do we keep?

Well, whichever one
we get from an if with the

first bit, depending on
what the first bit was.

How can I do k minus 1?

Well, we can define that in terms of k
minus 2.

So, we have kind of an
inductive construction of

how this looking up
into our bit strings works.

So we can say, well, how do we look up
into a bit string of size 2, that is,

our indexes of size 1, if we just reorder
our inputs, then it's just an if.

So whenever I was a 0, we wanted x sub 0.

Whenever I was a 1, we wanted x sub 1.

So this is the same thing as the if.

That now when we're saying whenever the if
was 0, we're going to get x sub 0.

Whenever the if was a 1, we're going to
get x sub 1.

Whatever bit we looked
up in lookup 1 was

the same as the bit
that we returned with if.

So now we know we can do lookup 1.

Since we can do if with only nans,
we can do lookup 1 with only nans.

Now let's look at lookup 2.

So lookup2, we have four bits as our input
and two bits as our index.

In the case that our first bit
happened to be a zero, we can

use the second bit to select
the right index of our first half.

And in the case where what we're looking
up should be in the second half,

we can use that second bit in order to
figure out which index it should have been.

Ignoring the first bit, where would we be
if we knew that we were in the second half?

Where would we be looking if we knew that
we were looking in the first half?

And then we're going to use an if to keep
one.

So look something up in the first half,
look something up in the second half,

and then using this if figure out
if we should have been looking

in the first half all along,
or the second half all along.

And we can continue this.

So we can start looking up three and four.

So what is lookup3?

We'll lookup3, we have 8 bits as our input
bit string, we have 3 bits as our index.

So we can use lookup2
to find the value in the

case we should be
looking in the first half.

We can use lookup2 to find the value in
the case we should have been looking in

the second half, and then figure out which
one was the right answer with an if.

And then how can we do lookup4?

We're going to use lookup3 to find
something in the first half, we can use

lookup3 to find something in the second
half, And then use an if to find out which

half we should have been looking in all
along.

And then we can use the same pattern for
lookup 5.

So if I wanted to do lookup 5,
this is going to be messy.

But I would have twice
as many input bits here, so

I need to copy and paste
all of this garbage again.

So there we go, we have
twice as many input bits,

and we are going to have
one more bit of our index.

And then we are going to be looking at
lookup 4.

So in order to do lookup
5, we are going to look at

lookup 4 to look in the
first half or the second half.

And then we use an if
with the first bit to figure

out which half we should
have been in, and so forth.

For any k that you give me, we can find a
lookup k defined in this recursive way.

So because I can do if, I can do lookup 1.

Because I can do lookup 1 and if,
I can do lookup 2.

Because I can do lookup 2 and if,
I can do lookup 3.

So all of these, now I could, with effort,
convert into exclusively NAND gates.