Which is the better NAND

SelDraken · July 13, 2023, 3:39am

I am wanting to make a function that acts like a NAND.
It takes in two inputs, A, B and outputs a C

Which is more efficient in lua

not A or not B
not (A and B)

thanks for the replies.

Mystxry12 · July 13, 2023, 3:41am

Second approach is the best.

ThanksRoBama · July 13, 2023, 8:57am

You should benchmark it chars chars

waves5217 · July 13, 2023, 9:44am

Both expressions give equivalent output and they’re both SO fast I don’t think you should be bothering with performance of either option. The difference depends on what A and B are, but you can still run multiple hundred million of these if-statements in under a second before reaching stack overflow. There are many other factors and circumstances magnitudes more crucial than this, affecting execution time.

Anyways, let’s break down how lua (to my knowledge) interprets the expressions.

IMPORTANT: Lua’s short-circuit evaluation will not evaluate the second operand if the first one is sufficient.

not false or true/false

Won’t even look at the second option because the first operand is true and the condition is true regardless of the second operand.

(not true) and true/false

Same applies, but with the opposite values. First operand false, whole condition is false.

The execution speed will theoretically be faster for the expression that doesn’t evaluate the unnecessary part.

If A is true, not A or not B will execute faster because it will conclude before B is even evaluated.

→ not (A and B) will proceed to check the value of B.

If A is false, not (A and B) will execute faster because B won’t be evaluated.

→ not A or not B will proceed to check the value of B.

So I’d say, choose the one you prefer in terms of readability.

ThanksRoBama · July 13, 2023, 10:20am

Less theorizing, more experimenting! >:3

Setup

Two sets of 10k bools, randomly chosen with an even distribution, NAND’ed together. First with one method, then with the other.

Benchmarking code


local nbs = 1e5
local a, b = {}, {}
for i = 1, nbs do
	a[i] = math.random(0, 1) == 1
	b[i] = math.random(0, 1) == 1
end

local ca, cb = 0, 0
for i = 1, nbs do
	if a[i] then ca += 1 end
	if b[i] then cb += 1 end
end
print(ca/nbs, cb/nbs) --Just checking that the distribution seems reasonable

local repeats = 1e3
for _ = 1, 1 do
	local nts = 1e5
	local ts = {}
	for i = 1, nts do
		local t0 = tick()
		local aNandB
		for _ = 1, repeats do --Do the calculation lots of times because it's too damn fast
			aNandB = not a[i] or not b[i] --1.2e-8, 26% slower
			--aNandB = not (a[i] and b[i]) --9.5e-9
		end
		local t1 = tick()
		ts[i] = t1 - t0
	end

	local avg = 0
	for i = 1, nts do
		avg += ts[i]/nts
	end
	print(avg/repeats)
end

Change which version is commented out to switch between testing one or the other.

Results

Code	Average time	Times slower than fastest	Times faster than slowest
`not a[i] or not b[i]`	1.20E-08	1.26	1
`not (a[i] and b[i])`	9.51E-09	1	0.79

Conclusion

not (a[i] and b[i]) is on average 26% faster than not a[i] or not b[i] for this type of input, and experiments are coo!!!

waves5217 · July 13, 2023, 12:44pm

Hey, cool test!

I’ve done my experiment a bit differently, so my results differ. I’ll also consider why that is so.

Conclusion

Both expressions are almost EQUALLY EFFICIENT.

The difference is usually no higher than 0.8 %!

Experiment description

In attempts to measure the performance as perfectly as possible, I compared the same condition in a number of repetitions (100 million, to be exact). I ran the repetitions 10 times separately but during the same run-time for both expressions, not A or not B and not (A and B). The experiment was repeated four times, that is for all four combinations of A and B booleans. (true, true, false, false, true, false and false, true).

Hypothesis

Described in my post above: Which is the better NAND - #4 by MeerkatSpirit. I expected the performance to be about equal. Both expressions had their advantages depending on the two conditions.

Important considerations

Studio takes some time to fully launch and load, which means that not yielding the script for a short while before beginning the experiment may have an impact on the results, especially of the first tested expression in order.

→ Solved this with task.wait(10) before starting.

os.clock() is the most accurate function for benchmarking. tick() can potentially cause slight inconsistencies.
Floating point error. Because of the certain limitation in storing numbers, calculating average is not always perfect.
Because both expressions are so damn fast, there are other factors involved in the execution time. These tests arguably cannot be perfect.

Sometimes your results will differ! Studio events, resource like CPU use, background tasks on your computer, CPU and GPU temperature, all this can affect the outcome. Sometimes the first expression is faster than the second, although it theoretically shouldn’t be, and vice versa.

Code

local repetitions = 1e8

local times1, times2 = {}, {}
local clock = os.clock
local tstart: number
local tfinish: number

local A = false
local B = true

local avg1: number
local avg2: number

task.wait(10)
print("Began")

for i=1, 10 do
	tstart = clock()
	
	local aNandB
	
	for i=1, repetitions do
		aNandB = not A or not B
	end
	
	tfinish = clock() - tstart
	times1[#times1+1] = tfinish
	
	task.wait()
end

for i=1, 10 do
	tstart = clock()

	local aNandB

	for i=1, repetitions do
		aNandB = not (A and B)
	end

	tfinish = clock() - tstart
	times2[#times2+1] = tfinish
	
	task.wait()
end

local function FindAverage(array)
	local count = 0
	for _,v in array do
		count += v
	end
	
	return count/#array
end

avg1 = FindAverage(times1)
avg2 = FindAverage(times2)

print("Average time | not A or not B: "..avg1)
print("Average time | not (A and B): "..avg2)

if avg1 > avg2 then
	print("not (A and B) was faster")
	print(
		"Relative difference (%): "..string.format("%.3f", tostring(((avg1-avg2)/avg1)*100))
	)
else
	print("not A or not B was faster")
	print(
		"Relative difference (%): "..string.format("%.3f", tostring(((avg2-avg1)/avg2)*100))
	)
end

Results

A = true, B = true

→ not (A and B) was negligibly faster.

not (A and B)	0.6796392300006119 s	not A or not B	0.6804587700011325 s

Relative difference (%): 0.120.

A = false, B = false

→ not A or not B was negligibly faster.

→ Interestingly, sometimes the difference was a lot bigger (2.5% or more). I’m not sure what causes that.

not (A and B)	0.6842400899971836 s	not A or not B	0.6828325800059247 s

Relative difference (%): 0.206.

A = true, B = false

→ not (A and B) was negligibly faster.

not (A and B)	0.6969810900001903 s	not A or not B	0.7017967100007809 s

Relative difference (%): 0.686.

A = false, B = true

→ not A or not B was negligibly faster.

not (A and B)	0.7116225999998278 s	not A or not B	0.7100575700038462 s

Relative difference (%): 0.220.

Why did the results differ from the test by @ThanksRoBama ?

ThanksRoBama, nice username

I quite like their test, it’s interesting as a practical example. Fun approach. However, even though the distribution is approximately equal, the combinations of values A and B are not, which causes variations.

After switching to os.clock(), adding task.wait(10) at the top, and performing multiple tests, both expressions appeared to be similarly efficient.

SelDraken · July 13, 2023, 10:23pm

I was asking for my son, he does a lot of hardware type circuitry using different gates, and he was wondering the difference depending on the underlying hardware. Such as on the computers boards, and circuitry, which is using the least amount of ‘hardware’ energy.

waves5217 · July 13, 2023, 11:24pm

not (A and B) is formed as a NAND gate.

NAND gate diagram:

A ---|      |
     | NAND |---C
B ---|      |

(NAND gate - Wikipedia)

Mathematically that’s .

The computer evaluates both A and B before negating to produce the output.

But it gets slightly more complicated than this because Lua won’t even touch B if A is false. It will conclude the whole condition is false before negating. So it doesn’t seem to truly fit NAND. Well, actually, it’s underlying C code doing this.

On the other hand, similar applies to not (A or B) and not A or not B (which are different expressions producing different outcomes). I guess that would mean it would be inaccurate to associate them with a single particular gate.

Considering the tests above, we could say the required hardware resources depend on the values of A and B.

In theory

not (A and B)

A

true

B

true

→ not (true and true) → not true → false

A

true

B

false

→ not (true and false) → not false–> true

A

false

B

false or true

→ (directly to) not false → true

Doesn’t matter what B is. It won’t be considered.

=========================================

Looks like inverter gate (NOT gate) at this point.

What supports this is the almost identical execution time for not false and not (false and true).

EmilyBendsSpace · July 13, 2023, 11:44pm

Short-circuit evaluation is just a performance optimization though, it doesn’t change the logic, so it’s still always going to match the NAND truth table. In fact, in the actual transistor implementation of a PMOS NAND gate, the MOSFETs are in parallel, so either one can literally short-circuit the other, making the state of the other transistor irrelevant.

waves5217 · July 14, 2023, 12:23am

Hey, thanks for the reply, Emily, you really bend space (seen your many contributions before).

I am by no means on a very familiar ground with these hardware details. So if I understand correctly, you mean that not (A and B) is always going to match the NAND truth table regardless of the lua implementation.

Just like not (A or B) evaluation matches the NOR truth table, even though lua allows the evaluation to halt early when the result can be determined without fully evaluating both operands.

After consulting the Wiki, “PMOS or pMOS logic […] is a family of digital circuits based on p-channel, enhancement mode metal–oxide–semiconductor field-effect transistors (MOSFETs)” (PMOS logic - Wikipedia). And PMOS NAND is responsible for not-and operations.

So the transistors are arranged in parallel in a way that allows short-circuit output because one transistor renders other transistors irrelevant regardless of their state.

Awkward and completely simplified picture:

@SelDraken this is amazing info. It’s the hardware configuration itself allowing Lua and C to do this.

SelDraken · July 14, 2023, 12:31am

Thanks for the posts.
This is all a bit beyond me.

My son has been building circuits, and I am trying to introduce him to some programming.
So he has had questions that I never thought to even ask about how things are working behind the scenes with the language and the logic.

He said the post marked as solution is what most answered his questions about this.
He is in high school and already knows more than I have learned in the last 30 years of coding o.o

I appreciate all the answers, this has been very educational for me too, and given us a lot of things to research.

Thanks again everyone, I would mark you all as solved if I could.

waves5217 · July 14, 2023, 12:48am

I’m glad we could help and that you guys found some use of my posts too.

Emily probably knows much more than me about hardware. Lua/C can fully evaluate the expression in some cases with only the first variable. NAND can be viewed as a small box, but the “parallel transistors” in those mentioned cases make NAND resemble the functionality of a NOT gate(?). So the operation is still is performed by PMOS NANDs, and what I said at the end of the reply marked as a solution is not entirely true. Sorry. Of course, the execution speed is still the same, but it doesn’t involve different gates.

I learned a lot today too. Good luck with new discovery!

EmilyBendsSpace · July 14, 2023, 8:22pm

It’s expected that you won’t be able to measure a real difference here. Just overhead of the for loop, which includes an integer comparison, is going to dominate over a few boolean operations. Both expressions also short-circuit when the first ‘A’ operand is False. In a totally naive, unoptimized implementation, not (A and B) will have fewer operations in the case where A is true (one AND, one invert), whereas (not A) or (not B) would have two inversions and one OR.

Personally, if you’re going to implement NAND, there’s no reason not to just use not(A and B) since it’s immediately readable as NAND right from the operands, and it’s going to be at least as fast as the alternative.

system · July 28, 2023, 8:22pm

This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.