Skip to content

travisdesell/subset_sum_at_home

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

To compile:
    After cloning the git repository, be sure to do:
        git submodule init
        git submodule update
    To make sure that you grab all the files in the undvc_common submodule.

    Verbose version:
        g++ -Wall -DVERBOSE -O3 -o subset_sum subset_sum_main.cpp

    Quiet (fast) version:
        g++ -Wall -O3 -o subset_sum subset_sum_main.cpp

    For BOINC:
        g++ -DVERBOSE -DFALSE_ONLY -DENABLE_CHECKPOINTING -D_BOINC_ -O3 -msse3
            -funroll-loops -ftree-vectorize -Wall subset_sum_main.cpp
            -o subset_sum

Additional flags:
    -DTIMESTAMP             -- enable printing the starting, ending and
                               running time of the program
    -DFALSE_ONLY            -- only print out the failed sets
    -DENABLE_COLOR          -- enable ANSI colors. Sums that are required
                               and found (1s) will be printed green, and
                               sums that are required and not found (0s)
                               will be red.
    -DENABLE_CHECKPOINTING  -- Turns on checkpointing.
    -DSHOW_SUM_CALCULATION  -- Turns on printing out how the subset sums
                               are calculated. Useful for debugging and
                               this might be nice for analysis.
    -DHTML_OUTPUT           -- Output will be formatted for HTML, so it
                               can be put in a webpage.

To run:
    ./subset_sum <M> <N>
    Where <M> is the maximum set value, and <N> is the number of elements 
    in the set.  This will calculate it for all subsets.

    ./subset_sum <M> <N> <i> <count>
    This will start from the <i>th subset of the problem for <M> and <N>,
    and compute the next <count> subsets.


TODO:
    *   generate_ith_subset and the n_choose_k functions need to be
        updated so they don't fail when M >= 68 and N >= 34.

    *   Calculate the set sums (without a binary representation) and use
        it to verify the results from the fast binary implementation.
        *   Double check that the 'all_ones', 'or_single', 'or_equal' and 
            'shift_left' functions are working correctly.

    *   Update the code so that instead of checking all sums up to the 
        sum of all set elements, we only need to check up to the sum 
        of all set elements divided by 2 (as the sums are symmetric).

BUGS:
    *   No known bugs at the moment.

About

Source code for the SubsetSum@Home application.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Contributors 4

  •  
  •  
  •  
  •