WEBVTT

1
00:00:00.180 --> 00:00:04.267
Must one query produce the whole truth table?

2
00:00:04.267 --> 00:00:10.536
A single query asks for one bit, a count asks how many assignments return one,

3
00:00:10.536 --> 00:00:15.064
and a full vector asks for every result in a declared order.

4
00:00:15.064 --> 00:00:21.391
Packed evaluation stores and processes truth bits together. We will learn to distinguish that

5
00:00:21.391 --> 00:00:28.125
representation from execution choices and the work required by the requested output.

6
00:00:28.305 --> 00:00:33.297
In false-first assignment order, the first four outputs are zero, one, one, one.

7
00:00:33.297 --> 00:00:39.880
The next two groups repeat that pattern because
A and B are not both true. The last four outputs are one,

8
00:00:39.880 --> 00:00:45.925
zero, zero, zero. The vector contains sixteen answers.

9
00:00:46.105 --> 00:00:50.610
The backend defines bit k as the answer for assignment row k.

10
00:00:50.610 --> 00:00:56.171
In our example the packed integer is seven thousand nine hundred eighteen.

11
00:00:56.171 --> 00:01:02.684
Its low bit stores row zero, the next bit row one, and so on.

12
00:01:02.684 --> 00:01:08.709
Ordinary printed binary notation puts the highest bit on the left, so label the direction.

13
00:01:08.889 --> 00:01:15.774
A packed evaluator constructs one bit column per input
variable. Bitwise AND combines the A and B columns,

14
00:01:15.774 --> 00:01:20.371
OR combines C and D, and XOR combines those two results.

15
00:01:20.371 --> 00:01:25.223
Each bit position performs the same Boolean calculation for its own assignment.

16
00:01:25.403 --> 00:01:30.871
The packed integer has ten set bits, so the satisfying-assignment count is ten.

17
00:01:30.871 --> 00:01:36.073
The runnable helper bitset to bool array takes the packed integer and number of variables,

18
00:01:36.073 --> 00:01:39.986
then returns the same sixteen-entry vector as the scalar oracle.

19
00:01:39.986 --> 00:01:45.035
The earlier word unpack was explanatory shorthand, not an API call.

20
00:01:45.215 --> 00:01:48.919
Packed versus unpacked describes representation.

21
00:01:48.919 --> 00:01:53.586
Eager versus lazy describes when work is performed.

22
00:01:53.586 --> 00:01:59.158
The repository’s named evaluation and materialization modes have specific behavior,

23
00:01:59.158 --> 00:02:04.000
so we do not treat lazy as a promise that a requested full matrix is free.

24
00:02:04.000 --> 00:02:07.726
A materialize call still asks for a concrete array.

25
00:02:07.906 --> 00:02:15.197
Compare two schedules for the same rule and layout. In the first,
build the full matrix immediately and retain it for later lookup.

26
00:02:15.197 --> 00:02:19.330
In the second, keep the compiled graph and request the matrix later.

27
00:02:19.330 --> 00:02:26.191
Both schedules eventually return the same array; the
distinction here is when the explicit output is produced.

28
00:02:26.371 --> 00:02:28.310
Names alone can mislead.

29
00:02:28.310 --> 00:02:35.972
The current function named compile expression to C M lazy builds
the shared graph and calls materialize C M before returning.

30
00:02:35.972 --> 00:02:41.848
Our example confirms that it returns the same dense array as the other wrapper.

31
00:02:41.848 --> 00:02:48.465
To defer final materialization explicitly, retain the compiled node and call materialize later.

32
00:02:48.645 --> 00:02:54.787
For k independent Boolean inputs, a complete truth vector has two to the k entries.

33
00:02:54.787 --> 00:03:01.288
Packing reduces storage overhead, but the mathematical output still contains that many bits.

34
00:03:01.288 --> 00:03:08.230
A graph may stay small while its explicit truth table
becomes large. State which artifact a size claim describes.

35
00:03:08.410 --> 00:03:12.880
A caller wants only to know whether one specified configuration is accepted.

36
00:03:12.880 --> 00:03:18.813
Another caller wants every accepted configuration listed. Are those the same benchmark task?

37
00:03:18.813 --> 00:03:30.794
Decide what must be returned before comparing their execution times.

38
00:03:30.974 --> 00:03:37.650
The first task returns one Boolean answer. The second
must produce a potentially large list of assignments.

39
00:03:37.650 --> 00:03:40.959
Timing them as if they were equivalent would be misleading.

40
00:03:40.959 --> 00:03:47.959
Next we will define a fair comparison that accounts for
preparation, repeated queries, and the exact output returned.