Ron's Site
 Ramblings in mathematics and computer science

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

 By Ron ZenoFriday, 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 // for exit #include // 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; } ``` Copyright © 2002 Ron Zeno

Home