# Based on Quine–McCluskey algorithm. Improve Nested loop for performance

I have a running program. That accepts 1 to 15 variables The goal of the program was a simplifier. Based on the Quine–McCluskey algorithm

Consider 3 variables

000
001
010
011
100
101
110
111


I group them by number of 1

000

001
010
100

011
101
110

111


Then I compare each string from the group to the next group

group 1
000

group 2
001
010
100

group 3
011
101
110

group1 -> group2
------------------
000 -> 001 = 00-
000 -> 010 = 0-0
000 -> 100 = -00
------------------
group2 ->group3
--------------------
001 -> 011 = 0-1
001 -> 101 = -01
001 -> 110 = no output

010 -> 011 = 01-
010 -> 101 = no output
010 -> 110 = -10

100 -> 011 = no output
100 -> 101 = 10-
100 -> 110 = 1-0

---------------------
etc.


then group the output again by number of 1 and compare them again until no strings can be compared.

I need to achieve a 15 variable but it take for ever for the program to finish.Any Idea how to speed it up. I was testing it on threading but just a little improvement.

Number of Strings: 2048 Length of variable: 11 Time: 10 minutes

Need to Achieved

Number of Strings: 32767 Length of variable: 15 Time: cannot be achieved

 List<List<string>> ImplicantsByOneFinal = new List<List<string>>();
List<List<string>> TermsByOne = new List<List<string>>();


is there a way or algorithm to improve this code. it becomes slower on 11 to 15 variables.

bool CombineAndGroup(List<List<string>> ImplicantsByOne)
{
TermsByOne = new List<List<string>>();
int combined = 0;
for (int i = 0; i < ImplicantsByOne.Count - 1; i++)
{
List<string> termsGrouped = new List<string>();
for (int j = 0; j < ImplicantsByOne[i].Count; j++)
{
int combination = 0;
int num1 = Convert.ToInt32((ImplicantsByOne[i][j]).Replace('-','0'), 2);
for (int k = 0; k < ImplicantsByOne[i + 1].Count; k++)
{
int num2 = Convert.ToInt32((ImplicantsByOne[i + 1][k]).Replace('-', '0'), 2);
int num3 = num2 - num1;
double num4 = Math.Log((double)num3, (double)2);
if (((num4 % 1) == 0) && (num3 > 0) && (Esum(ImplicantsByOne[i][j]) == Esum(ImplicantsByOne[i + 1][k])))
{
string combinedMinterm = CompareString(ImplicantsByOne[i][j], ImplicantsByOne[i + 1][k]);
if (!termsGrouped.Contains(combinedMinterm))
{
}

}
}
}
if (termsGrouped.Count > 0)
{
combined += termsGrouped.Count;
}
}

return (combined > 0) ? true : false;
}

private int Esum(String binCode)
{
binCode = binCode.Replace('1','0');
binCode = binCode.Replace('-', '1');
int esum = Convert.ToInt32(binCode, 2);
return esum;
}
//Purpose of CompareString is to compare two string and change the unique char to '-'
//like 000 and 001 = 00-
private string CompareString(string str1, string str2)
{
if (str1 == str2)
{
CountCompareStringLoops++;
return str1;
}
else
{
if (str1.Length == 1)
{
return "-";
}
int halflength = str1.Length / 2;
return CompareString(str1.Substring(0, halflength), str2.Substring(0, halflength)) + CompareString(str1.Substring(halflength), str2.Substring(halflength));
}
}


Main Program

 MintermsByOne = Loaded with string 000 001 and so on

CombineAndGroup(MintermsByOne);
ImplicantsByOneFinal = TermsByOne;
while (CombineAndGroup(TermsByOne))
{
ImplicantsByOneFinal = TermsByOne;
}


Output ImplicantsByOneFinal

• It's good to see you here. Commented May 10, 2013 at 12:39

I don't know how to write C#, but I want to help. So my code is given in Java.

1. I think == is an O(n) operation, your CompareString is O(nlgn) (n = str1.Length). Use a simpler and faster O(n) way and see if the time decreases:

private String CompareString(String str1, String str2) {
StringBuilder sb = new StringBuilder(str1.length());
for (int i = 0; i < str1.length(); i++) {
if (str1.charAt(i) == str2.charAt(i))
sb.append(str1.charAt(i));
else
sb.append('-');
}
return sb.toString();
}

2. Well, I found that there are a lot of ToInt32. Calculate the result of all strings in ImplicantsByOne at once and use it later. Do the same thing to Esum.

3. To check if num3 is a power of two:

private boolean isPowerOfTwo(int x) {
return (x > 0 && (x & (x - 1)) == 0);
}

• Thanks .I will try to get the time of CompareString if its faster.Also thanks for the Power of two method :). Commented May 11, 2013 at 3:21