1 package net.mograsim.logic.model.examples;
3 import java.math.BigInteger;
4 import java.util.ArrayList;
5 import java.util.HashMap;
8 import java.util.Map.Entry;
11 public class NANDOptimizer
13 public static void main(String[] args)
15 System.out.println(optimize(3, Set.of(0b001, 0b010, 0b011, 0b100), Set.of(0b000)));
18 private static String optimize(int bitCount, Set<Integer> combinationsRequiredZero, Set<Integer> combinationsRequiredOne)
20 BigInteger maskZeroes = combinationsRequiredZero.stream().map(BigInteger.ONE::shiftLeft).reduce(BigInteger.ZERO, BigInteger::or);
21 BigInteger maskOnes = combinationsRequiredOne.stream().map(BigInteger.ONE::shiftLeft).reduce(BigInteger.ZERO, BigInteger::or);
22 if (maskZeroes.and(maskOnes).compareTo(BigInteger.ZERO) != 0)
23 throw new IllegalArgumentException("A combination is required to be both 1 and 0");
24 BigInteger mask = maskZeroes.or(maskOnes);
25 BigInteger target = maskOnes;
27 return optimize(bitCount, mask, target);
30 public static String optimize(int bitCount, BigInteger mask, BigInteger target)
32 long start = System.currentTimeMillis();
33 Map<BigInteger, String> atomicCombinations = generateAtomicCombinations(bitCount);
35 for (Entry<BigInteger, String> e : atomicCombinations.entrySet())
36 if (check(e.getKey(), target, mask))
39 List<Map<BigInteger, String>> mapPool = new ArrayList<>();
40 mapPool.add(new HashMap<>());
42 for (int gateCount = 1;; gateCount++)
44 mapPool.add(new HashMap<>());
45 System.out.println("Checking gateCount " + gateCount + "...");
46 String optimized = optimize(atomicCombinations, mask, target, gateCount, mapPool.toArray(Map[]::new));
47 if (optimized != null)
49 long stop = System.currentTimeMillis();
50 System.out.println("Took " + (stop - start));
56 @SuppressWarnings("null")
57 private static String optimize(Map<BigInteger, String> availableCombinations, BigInteger mask, BigInteger target, int remainingGates,
58 Map<BigInteger, String>[] mapPool)
60 final boolean deeperLevelExists = remainingGates != 1;
61 Map<BigInteger, String> availableCombinationsCopy;
62 if (deeperLevelExists)
64 availableCombinationsCopy = mapPool[remainingGates];
65 availableCombinationsCopy.putAll(availableCombinations);
67 availableCombinationsCopy = null;
68 for (Entry<BigInteger, String> source1 : availableCombinations.entrySet())
69 for (Entry<BigInteger, String> source2 : availableCombinations.entrySet())
71 BigInteger nand = nand(source1.getKey(), source2.getKey());
72 if (availableCombinations.containsKey(nand))
74 String name = '(' + source1.getValue() + ' ' + source2.getValue() + ')';
75 if (deeperLevelExists)
77 availableCombinationsCopy.put(nand, name);
78 String result = optimize(availableCombinationsCopy, mask, target, remainingGates - 1, mapPool);
81 availableCombinationsCopy.remove(nand);
82 } else if (check(nand, target, mask))
86 if (deeperLevelExists)
87 availableCombinationsCopy.clear();
91 private static boolean check(BigInteger combination, BigInteger target, BigInteger mask)
93 return combination.xor(target).and(mask).compareTo(BigInteger.ZERO) == 0;
96 private static Map<BigInteger, String> generateAtomicCombinations(int bitCount)
98 Map<BigInteger, String> atomicCombinations = new HashMap<>();
99 for (int bit = 0; bit < bitCount; bit++)
101 BigInteger atomicCombination = BigInteger.ZERO;
102 for (int i = 1 << bit; i < 1 << bitCount; i += 2 << bit)
103 for (int j = 0; j < 1 << bit; j++)
104 atomicCombination = atomicCombination.or(BigInteger.ONE.shiftLeft(i + j));
105 atomicCombinations.put(atomicCombination, Integer.toString(bit));
107 return atomicCombinations;
110 private static BigInteger nand(BigInteger a, BigInteger b)
112 return b.and(a).not();