Page MenuHomePhorge
Files F360844

No OneTemporary
Actions

Size
5 KB
Referenced Files
None
Subscribers
None

View Options

diff --git a/bruteforce.py b/bruteforce.py
new file mode 100644
index 0000000..f18eb59
--- /dev/null
+++ b/bruteforce.py
@@ -0,0 +1,122 @@
+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-diff
Expires
Sat, May 17, 4:20 PM (1 d, 4 h)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
141559
Default Alt Text
(5 KB)

Event Timeline