Page MenuHomePhorge
Files F386358

bruteforce.py
No OneTemporary
Actions

Size
4 KB
Referenced Files
None
Subscribers
None

bruteforce.py
View Options

from itertools import product
from functools import lru_cache # For memoization
# Define the area size for each gate type
@lru_cache(None)
def evaluate_circuit(circuit, inputs):
intermediate_outputs = list(inputs[:])
for gate, in1, in2 in circuit:
intermediate_out1 = intermediate_outputs[in1]
intermediate_out2 = intermediate_outputs[in2]
if gate == 'AND':
output = intermediate_out1 & intermediate_out2
elif gate == 'OR':
output = intermediate_out1 | intermediate_out2
elif gate == 'XOR':
output = intermediate_out1 ^ intermediate_out2
elif gate == 'XNOR':
output = ~(intermediate_out1 ^ intermediate_out2) & 1
elif gate == 'NAND':
output = ~(intermediate_out1 & intermediate_out2) & 1
elif gate == 'NOR':
output = ~(intermediate_out1 | intermediate_out2) & 1
elif gate == 'INV':
output = ~intermediate_out1 & 1
elif gate == 'ANDNOT':
output = intermediate_out1 & (~intermediate_out2 & 1)
elif gate == 'ORNOT':
output = intermediate_out1 | (~intermediate_out2 & 1) # & 1 to ensure output is 0 or 1 else it will be -1
else:
output = 0
intermediate_outputs.append(output)
return intermediate_outputs[-1]
def brute_force_boolean(target_function, num_inputs, max_gates, max_area):
truth_table = list(product([0, 1], repeat=num_inputs))
target_outputs = [target_function(input_comb) for input_comb in truth_table]
print("Truth Table and Target Outputs:")
print("Inputs\t\tOutput")
for inputs, output in zip(truth_table, target_outputs):
print(f"{inputs}\t{output}")
gate_types = {
'INV': 1160,
'AND': 3472,
'NAND': 2832,
'OR': 3472,
'NOR': 2832,
'XOR': 4632,
'XNOR': 4632,
'ANDNOT': 3472,
'ORNOT': 3472
}
best_circuit = None
best_area = max_area
i = 0
for num_gates in range(1, max_gates + 1):
print("num_gates: ", num_gates, " building circuits")
for circuit in generate_all_circuits(num_inputs, num_gates, gate_types, best_area):
total_area = sum(gate_types[gate] for gate, _, _ in circuit)
if(i % 100000 == 0):
print(f"Circuit: {i:,} at num_gates: {num_gates} with area: {total_area}")
i += 1
if total_area > best_area:
continue
if all(evaluate_circuit(tuple(circuit), inputs) == target_output
for inputs, target_output in zip(truth_table, target_outputs)):
if not best_circuit or total_area < best_area:
best_circuit = circuit
best_area = total_area
print("New best circuit found with area", best_area, ":", best_circuit)
else:
print("Circuit with area", total_area, ":")
for gate, in1, in2 in circuit:
print(f" Gate: {gate}, Input1: {in1}, Input2: {in2}")
return best_circuit, best_area
def generate_all_circuits(num_inputs, num_gates, gate_types, best_area):
"""
circuit: [(gate, in1, in2), ...] where gate is one of the gate types and in1, in2 are indices of the inputs or intermediate outputs
"""
base_indices = list(range(num_inputs))
def recursive_build(current_circuit, available_indices, current_area, depth):
if depth == num_gates:
outputs_used = set()
for _, in1, in2 in current_circuit:
outputs_used.add(in1)
outputs_used.add(in2)
all_outputs_used = True
for i in range(len(current_circuit)-1):
if i + num_inputs not in outputs_used:
all_outputs_used = False
break
if all_outputs_used or num_gates == 1:
yield current_circuit
return
for gate, area in gate_types.items():
if current_area + area > best_area:
continue
for in1 in available_indices:
for in2 in available_indices:
if (in1 == in2 and gate != 'INV') or (in1 != in2 and gate == 'INV'): # Skip redundant gates
continue
new_circuit = current_circuit + [(gate, in1, in2)]
new_indices = available_indices + [len(available_indices)]
yield from recursive_build(new_circuit, new_indices, current_area + area, depth + 1)
return recursive_build([], base_indices, 0, 0)
# Example: Target function for 2-input XOR
target_function = lambda x: x[0] ^ x[1]
best_circuit, best_area = brute_force_boolean(target_function, num_inputs=2, max_gates=5, max_area=1000000)
print("Best circuit:", best_circuit, "with area: ", best_area)

File Metadata

Mime Type
text/x-script.python
Expires
Thu, Jul 3, 7:10 AM (1 d, 16 h)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
157201
Default Alt Text
bruteforce.py (4 KB)

Event Timeline