Dedekind.cpp - A program for computing some solutions to Dedekind's problem

By Ron Zeno
Friday, June 28, 2002
The following code compiles and runs correctly under MSVC++, though it should be easily modified for other compilers. Computing M(7) is treated as a special case, so that it can be resumed or even distributed with only a few changes.
// Dedekind.cpp
// Copyright © 2002 Ron Zeno
//
// Computes and counts representations of the distinct 
// monotone Boolean functions of n variables for 1<=n<=6, thus solving
// Dedekinds problem M(n) for the same n.  (These representations are
// used to test sorting networks that begin with simple, hypercubic
// comparator sets.)
//
// The monotone functions for M(n) are computed from those of M(n-1).
// For n=0, the functions are 0 and 1.
//
// The monotone functions are represented as M(n) bit strings 
// of length 2^n.  Since M(6) = 7,828,354, it requires almost 60 MB
// memory just to store the corresponding strings.  
//
// M(7) = 2,414,682,040,998 is computed from M(6), if the program is run 
// long enough, but no attempt is made to save the corresponding strings
//
// I've made no attempt to calculate M(8) which is a 76-bit number.
//
// For more information:
// Generating montone functions: http://www.mathpages.com/home/kmath094.htm
// Dedekind's problem: http://www.mathpages.com/home/kmath030.htm
//
// Using UINT64 for the strings because it allows the compiler to handle all 
// operations on the strings: & | == <<
//
// Using global variables rather than passing parameters in order to reduce
// memory requirements


/*
Outline of algorithm:

(Maintain that the strings are ordered numerically)
for each string i from the sets for M(n-1) taken in order
	for each string j from the sets for M(n-1) that is numerically greater or equal to i taken in order
		Add the string of j concatenated to the end of i to the strings for M(n) if
			L[i] & L[j] = L[i] and L[i] | L[j] = L[j] (this is equivalent to applying the sorting network
				comparison-swap operator L[i](k) : L[j](k) each bit k)
		(By taking i and j in order and appending j to i, the list of new strings will be 
		in numerical order.)


Two lists, one for M(n-1) and one for M(n) with their corresponding lengths
Initialize the list for M(0) to {0,1} with length 2
Initialize the other list to all zeroes with length 0

Compute the list for M(1) from M(0)
Output the list

Repeat after copying the new list over the old list (This method allows the lists to be of
different sizes.)

(Could instead repeat after swapping the references to the lists (use pointers to the lists, 
rather than copying contents of one into the other), but high potential for bugs if using
different sized lists.)
(Could also dynamically allocate memory for the lists.)
*/


/*
Bug fixes:
1) Was not resetting NewListLen after copying NewList into OldList
2) Was shifting TempI by CurrN rather than 2^CurrN (ShiftBy = 1 << CurrN)
3) Was not initializing NewList properly when starting with i = 1 rather than 0
4) Was assigning j instead of j0 as part of the resuming code

Performance fixes:
1) Removed the resetting of NewListLen, started with i = 1 rather than i = 0
*/

/*
Alternative algorithm (not implemented) with very low memory requirments but more computation
that computes M(n) directly without referring to M(n-1):

for each string x of 2^CurrN bits
	Sort the bits of x i,j where i and j differ by a single bit, 
		sorting all pairs i,j |i - j| = a together
	if x is unchanged, then it is a monotone boolean function (representation of)
*/

#include "stdafx.h"		// Standard MSVC++ header that includes stdio.h

#include <stdlib.h>		// for exit
#include <basetsd.h>	// for UINT64


// Constants for length of strings
int const MaxStringsNew = 7828354;		// 0:2, 1:3, 2:6, 3:20, 4:168, 5:7581, 6:7828354
int const MaxStringsOld = 7581;

UINT64 NewList[MaxStringsNew];
int NewListLen = 0;				// Current number of strings in NewList
UINT64 OldList[MaxStringsOld];
int OldListLen = 0;				// Current number of strings in OldList
int CurrN;						// Current n value for M(n) being computed


void InitLists()
{
	int i;

	for(i = 0; i < MaxStringsNew; i++)
	{
		NewList[i] = 0;
	}
	NewListLen = 0;

	for(i = 0; i < MaxStringsOld; i++)
	{
		OldList[i] = 0;
	}

	// n = 0 condition: {0,1}
	OldList[1] = 1;
	OldListLen = 2;

	CurrN = 0;	// Indicates M(0) is in OldList

	// Placing a copy into NewList as well
	NewList[1] = 1;
	NewListLen = 2;
}  // InitLists


void CopyList()
{
	int i;

	// Check for overflow and return 0 on error
	if (NewListLen > MaxStringsOld)
	{
		printf("List overflow during copy\n");
		exit(0);
	}

	for(i = 0; i < NewListLen; i++)
	{
		OldList[i] = NewList[i];
	}
	OldListLen = NewListLen;
}  // CopyList


void PrintNewList()
{
	int i;

	for(i = 0; i < NewListLen; i++)
	{
		printf("%I64Lu ", NewList[i]);
	}
	printf("\n");
	printf("Length = %d\n", NewListLen);
}  // PrintNewList


void WriteList()
{
	int i;
	FILE *fstream;

	if ((fstream = fopen("myfile.txt", "w")) == NULL)
	{
		printf("Can't open file\n");
		exit (1);
	}


	for(i = 0; i < NewListLen; i++)
	{
		fprintf(fstream, "%I64Lu\n", NewList[i]);
	}
	fclose(fstream);
}  // WriteList


void ReadList5()	// n=5 case for testing
{
	int i;
	UINT64 Temp;
	FILE *fstream;

	if ((fstream = fopen("results32.txt", "r")) == NULL)
	{
		printf("Can't open file\n");
		exit (1);
	}

	for(i = 0; i < 7581; i++)
	{
		fscanf(fstream, "%I64Lu\n", &Temp);
		OldList[i] = Temp;
	}

	fclose(fstream);

	OldListLen = 7581;
	CurrN = 5;
}  // ReadList5


void ReadList3()	// n=3 case for testing
{
	OldList[ 0] = 0;
	OldList[ 1] = 1;
	OldList[ 2] = 3;
	// Can stop here for n = 1
	//OldListLen = 3;
	//CurrN = 1;

	OldList[ 3] = 5;
	OldList[ 4] = 7;
	OldList[ 5] = 15;
	// Can stop here for n = 2
	//OldListLen = 6;
	//CurrN = 2;

	OldList[ 6] = 17;
	OldList[ 7] = 19;
	OldList[ 8] = 21;
	OldList[ 9] = 23;
	OldList[10] = 31;
	OldList[11] = 51;
	OldList[12] = 55;
	OldList[13] = 63;
	OldList[14] = 85;
	OldList[15] = 87;
	OldList[16] = 95;
	OldList[17] = 119;
	OldList[18] = 127;
	OldList[19] = 255;

	OldListLen = 20;
	CurrN = 3;
}  // ReadList3


void ReadList1()	// n=1 case for testing
{
	OldList[ 0] = 0;
	OldList[ 1] = 1;
	OldList[ 2] = 3;

	OldListLen = 3;
	CurrN = 1;
}  // ReadList1


int main(int argc, char* argv[])
{
	int i, j, ShiftBy;
	UINT64 TempI, TempJ, TempIShifted, TempNew;

	
	printf("Compute solutions to Dedekind's Problem\n\n");

	InitLists();

	// ReadList1();

	do
	{
		ShiftBy = 1 << CurrN;
		CurrN++;	// Now working on next n

		// Can skip the i = 0 case by setting NewListLen properly
		for (i = 1; i < OldListLen; i++)
		{
			TempI = OldList[i];
			TempIShifted = TempI << ShiftBy;
			for (j = i; j < OldListLen; j++)
			{
				TempJ = OldList[j];
				// Could use ^
				if (((TempI & TempJ) == TempI) && ((TempI | TempJ) == TempJ))
				{
					TempNew = TempIShifted | TempJ;
					// printf("%I64Lu ", TempNew);

					if (NewListLen >= MaxStringsNew)
					{
						printf("List overflow\n");
						printf("n = %d, i = %d, j = %d, Ti = %I64Lu, Tj = %I64Lu, TiS = %I64Lu, TN = %I64Lu\n",
							CurrN, i, j, TempI, TempJ, TempIShifted, TempNew);
						exit(0);
					}
					NewList[NewListLen] = TempNew;
					if (NewListLen >= 1)
						if (NewList[NewListLen] <= NewList[NewListLen - 1])
						{
							printf("Order incorrect\n");
							printf("n = %d, i = %d, j = %d, Ti = %I64Lu, Tj = %I64Lu, TiS = %I64Lu, TN = %I64Lu\n",
								CurrN, i, j, TempI, TempJ, TempIShifted, TempNew);
							exit(0);
						}

					NewListLen++;
				}
			}
		}

		//PrintNewList();
		printf("N = %d, Length = %d\n", CurrN, NewListLen);

		if (CurrN < 6)
		{
			CopyList();
			// Resetting NewListLen to 0 is required when starting with i = 0, for i = 1 keep it as is
			// NewListLen = 0;	// Setting the length back to 0 - not bothering to reinitialize list
		}
	} while (CurrN < 6);


	UINT64 ProgCheck = 4;//16777216;	// To check progress of lengthy computations with minimal disruption
									// Make sure it is >= Count or C1, whichever it is compared against
	UINT64 C1 = 2;
	UINT64 Count;
	int i0, j0;


	// n=7 - Requires some serious processing speed to compute.  Supercomputer anyone?
	// Written so it can be resumed or spread across multiple processors

	Count = NewListLen;		// To resume, set to last value computed instead
	i0 = 1;		// To resume, set to last value of i corresponding to Count
	j0 = i0;	// To resume, set to last value of j plus one


	// Count =    22011325208, i =     8120, j =   944900
	// Resuming, so set variables
	Count = 19863841562;
	i0 = 7708;
	j0 = 6357865 + 1;	// bug - was assigning j instead of j0

	// If resuming...
	TempI = NewList[i0];
	if (j0 != i0)
	{
		printf("Resuming...\n");
		for (j = j0; j < NewListLen; j++)
		{
			TempJ = NewList[j];
			if (((TempI & TempJ) == TempI) && ((TempI | TempJ) == TempJ))
			{
				Count++;

				C1++;

				//if ((Count ^ ProgCheck) == 0)
				if ((C1 ^ ProgCheck) == 0)
				{
					ProgCheck <<= 1;
					printf("Count = %14I64Lu, i0 = %8d, j = %8d\n", Count, i0, j);
					//printf("C1 = %14I64Lu\n", C1);
					//printf("TempI = %14I64Lu, TempJ = %14I64Lu\n", TempI, TempJ);
				}
			}
			/*
			C1++;

			//if ((Count ^ ProgCheck) == 0)
			if ((C1 ^ ProgCheck) == 0)
			{
				ProgCheck <<= 1;
				printf("Count = %14I64Lu, i0 = %8d, j = %8d\n", Count, i0, j);
				//printf("C1 = %14I64Lu\n", C1);
				//printf("TempI = %14I64Lu, TempJ = %14I64Lu\n", TempI, TempJ);
			}
			*/
		}
		i0++;	// Ready for next i
	}

	printf("Count = %14I64Lu, i0 = %8d, Len = %d\n", Count, i0, NewListLen);
	printf("(This will take a long while...)\n");
	for (i = i0; i < NewListLen; i++)
	{
		TempI = NewList[i];
		for (j = i; j < NewListLen; j++)
		{
			TempJ = NewList[j];
			if (((TempI & TempJ) == TempI) && ((TempI | TempJ) == TempJ))
			{
				Count++;

				C1++;

				// Debug - stop at a point to resume
				/*
				if (Count >= 10000)
				{
					printf("Count = %14I64Lu, i = %8d, j = %8d\n", Count, i, j);
					printf("Stopped\n");
					exit(0);
				}
				*/

				//if ((Count ^ ProgCheck) == 0)
				if ((C1 ^ ProgCheck) == 0)
				{
					ProgCheck <<= 1;
					printf("Count = %14I64Lu, i = %8d, j = %8d\n", Count, i, j);
					//printf("C1 = %14I64Lu\n", C1);
					//printf("TempI = %14I64Lu, TempJ = %14I64Lu\n", TempI, TempJ);
				}
			}
		}
	}

	//PrintNewList();
	printf("N = %d, Length = %d\n", CurrN+1, Count);

	printf("\n");

	return 0;
}
Home