WEBVTT 1 00:00:00.000 --> 00:00:02.233 This overview explains how a packed 2 00:00:02.233 --> 00:00:09.867 algebraic-normal-form representation stores exact coefficients and supports further representation comparisons. 3 00:00:09.867 --> 00:00:17.567 Compact coefficient storage is not the same object as a packed truth vector and does not guarantee a universal runtime win. 4 00:00:17.867 --> 00:00:24.833 In this algebraic normal form, multiplication means and and addition means exclusive-or. 5 00:00:24.833 --> 00:00:29.100 The formula is A exclusive-or A B. 6 00:00:29.100 --> 00:00:32.067 A term appearing twice would cancel. 7 00:00:32.067 --> 00:00:35.733 These operations differ from ordinary real-number addition and 8 00:00:35.733 --> 00:00:39.667 multiplication when values are combined. 9 00:00:39.667 --> 00:00:45.767 At zero zero and zero one, A is zero, so both terms are zero. 10 00:00:45.767 --> 00:00:51.433 At one zero, the A term is one and the product is zero, giving one. 11 00:00:51.433 --> 00:00:56.000 At one one, both terms are one and cancel to zero. 12 00:00:56.000 --> 00:01:00.800 The truth outputs are zero zero one zero. 13 00:01:00.800 --> 00:01:06.367 In the declared monomial order, the constant coefficient is zero, A is present, B alone is 14 00:01:06.367 --> 00:01:08.900 absent, and A B is present. 15 00:01:08.900 --> 00:01:12.600 The coefficient sequence is zero one zero one. 16 00:01:12.600 --> 00:01:16.667 It is not the truth-output sequence. 17 00:01:16.667 --> 00:01:16.682 Algebraic normal form writes a Boolean function as exclusive-or of products. 18 00:01:16.682 --> 00:01:22.400 Algebraic normal form writes a Boolean function as exclusive-or of products. 19 00:01:22.400 --> 00:01:29.067 A packed exact source-ANF representation stores coefficients while preserving the function. 20 00:01:29.067 --> 00:01:37.200 C6 advanced this exact core; C7 and C8 tested identities and representations on another family and machine. 21 00:01:37.200 --> 00:01:41.667 F is the exclusive-or of A and the product A AND B. 22 00:01:41.667 --> 00:01:46.500 Its ANF has coefficient one on the terms A and AB. 23 00:01:46.500 --> 00:01:51.833 On ascending A-B assignments its outputs are 0, 0, 1, 0. 24 00:01:51.833 --> 00:01:57.600 The declared monomial order assigns the two nonzero coefficients to positions one and three. 25 00:01:57.600 --> 00:02:02.267 Evaluating that stored ANF reconstructs the truth outputs. 26 00:02:02.267 --> 00:02:09.433 This is coefficient packing, not packing the truth-output column; the two bit layouts represent different objects. 27 00:02:09.433 --> 00:02:15.533 The retained C6 core advance did not automatically promote its gate or production path. 28 00:02:15.533 --> 00:02:20.133 C7 and C8 retained exact identities while relative cost of set, 29 00:02:20.133 --> 00:02:25.000 packed and bitset representations remained workload and machine dependent. 30 00:02:25.000 --> 00:02:29.898 Preserve that distinction when the coefficient animation looks compact. 31 00:02:29.898 --> 00:02:29.900 Preserve that distinction when the coefficient animation looks compact. 32 00:02:30.200 --> 00:02:34.333 Work a second complete case with A 1, B 1. 33 00:02:34.333 --> 00:02:37.767 Keep this assignment fixed throughout the calculation. 34 00:02:37.767 --> 00:02:42.000 Each symbol retains the meaning already introduced; a new value does not 35 00:02:42.000 --> 00:02:45.267 create a new logical rule. 36 00:02:45.267 --> 00:02:47.867 The linear term contributes one. 37 00:02:47.867 --> 00:02:53.067 The product term also contributes one because both of its inputs are one. 38 00:02:53.067 --> 00:02:58.533 Over the two-element field, exclusive-or of these contributions is zero. 39 00:02:58.533 --> 00:03:02.000 Adding them as ordinary integers would give two, which is not 40 00:03:02.000 --> 00:03:06.133 this Boolean polynomial evaluation. 41 00:03:06.133 --> 00:03:09.800 This case establishes a specific contrast. 42 00:03:09.800 --> 00:03:13.400 GF(2) sum is XOR. 43 00:03:13.400 --> 00:03:17.267 Coefficient storage and evaluation are distinct. 44 00:03:17.267 --> 00:03:21.800 Keep the input, intermediate values, and conclusion together when comparing 45 00:03:21.800 --> 00:03:24.067 it with the previous case. 46 00:03:24.067 --> 00:03:30.360 The calculated answer belongs to this complete assignment under the stated rule. 47 00:03:30.360 --> 00:03:30.367 The calculated answer belongs to this complete assignment under the stated rule. 48 00:03:30.667 --> 00:03:34.800 Pack the coefficients with entry j in bit j. 49 00:03:34.800 --> 00:03:40.167 Their weighted sum is ten, printed as binary one zero one zero. 50 00:03:40.167 --> 00:03:45.867 Reading that numeral as a truth vector would attach the wrong meaning to its bits. 51 00:03:45.867 --> 00:03:51.000 Pack the truth outputs by the same bit-position convention and obtain four, printed as 52 00:03:51.000 --> 00:03:53.233 zero one zero zero. 53 00:03:53.233 --> 00:03:57.267 The two words differ because one stores polynomial coefficients and 54 00:03:57.267 --> 00:04:00.833 the other stores evaluated outputs. 55 00:04:00.833 --> 00:04:05.767 A sparse coefficient form can be compact, but converting it or obtaining a requested full 56 00:04:05.767 --> 00:04:08.000 vector still costs work. 57 00:04:08.000 --> 00:04:12.033 A representation identity is not a benchmark result. 58 00:04:12.033 --> 00:04:19.096 Compare complete matched tasks before deciding which storage or execution form is useful. 59 00:04:19.096 --> 00:04:19.100 Compare complete matched tasks before deciding which storage or execution form is useful. 60 00:04:19.100 --> 00:04:23.633 Declare whether bits index ANF terms or assignments. 61 00:04:23.633 --> 00:04:30.322 Reconstruct exact outputs and keep representation costs tied to their workload and machine.