Date: Thu, 5 Dec 2019 16:09:26 -0800 From: Devin Teske <dteske@freebsd.org> To: freebsd-announce@freebsd.org Subject: [FreeBSD-Announce] BSD-Licensed Combinatorics library/utility Message-ID: <51AD9B50-9488-45CE-878F-EE97F6914E49@freebsd.org>
next in thread | raw e-mail | index | archive | help
Hello. I=E2=80=99d like to announce a new utility/library for FreeBSD base = available for review. https://reviews.freebsd.org/D16132 <https://reviews.freebsd.org/D16132>; Preview HTML-formatted manuals: https://fraubsd.org/doc/cmb.1.html <https://fraubsd.org/doc/cmb.1.html>; https://fraubsd.org/doc/cmb.3.html <https://fraubsd.org/doc/cmb.3.html>; *** Combinatorics is the study of combinations. For example, calculating how many possible combinations given a set of = items and some parameters such as how many or a range of how many items = to select. Iterating over every possible combination to perform some action for = each =E2=80=94 with support for position indicators so that if you = prematurely terminate you can pick up at the last combination where you = left-off. Find combinations of numerical items that produce a particular sum, = quotient, product, or difference. *** While these problem have been solved (or partially solved) in languages = such as: Perl (Algorithm::Combinatorics) Python (itertools, numpy) R (comb) Haskell Others =E2=80=A6 my implementation is faster than all of them. =E2=80=A6 and BSD-licensed. =E2=80=A6 and written in C with bindings for Perl and Python (R and = others forthcoming). =E2=80=A6 and works on Mac OS X, Linux, Solaris, BSD, etc. with minimal = dependencies. NB: The Perl/Python bindings are not in the review for import to base. *** Q. Why add this to FreeBSD base? A. Lofty goals With a combinatorics library, we can start thinking about taking on = monumental tasks such as: * Making the =E2=80=9Cbuild option survey=E2=80=9D test all combinations = of build options Today, the build-option survey only iterates over a handful of = hand-selected build options. It does combinatorially iterate over all = possible combinations as that might prove exorbitantly expensive in = either time or resources. I will be attempting to solve the incompleteness aspect using cmb, while = dedicating several hundred cores in a private cluster to solving the = time/resource requirements. * Offer packages compiled from ports with non-standard options I don=E2=80=99t know if any other Operating System is tackling this = problem, but I think we can, if not for the entire ports tree, a subset = thereof. One of the things I imagine is adding to the ports tree, the ability to = say =E2=80=9Cmake allpkg=E2=80=9D or something which would compile every = possible combination of optional directives in the given port directory = where you say it, generating uniquely named packages with appropriately = codified MANIFEST files that enumerate which options were enabled for = each. This project too, I am not sure how many resources or time will need to = be dedicated to staying current (especially if we try and tackle the = entire ports tree), but I do happen to have quite a lot of hardware at = my disposal and HPC scheduling software providing an MPI environment to = get the job done. *** Through both of these endeavors, the missing element has been a = permissively-licensed high-performance combinatorics library. I first started working in the highly specialized area of mathematics = dealing with combinations back in 1989, wrote my first Proof-of-Concept = (using Bourne Shell of all things) back in 2001 and in the past 3 years = have made a concerted effort to provide the missing aspect to more = complex work like the above endeavors. 30 years in the making, I am excited to bring to FreeBSD base my = BSD-licensed solution. Let it be like =E2=80=9Cseq=E2=80=9D, =E2=80=9Cjot=E2=80=9D, and other = well-known utilities in base for solving a hard problem in the =E2=80=9CUN= IX Way=E2=84=A2=E2=80=9D (write a tool to do one job and do it well). =E2=80=94=20 Cheers, Devin=
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?51AD9B50-9488-45CE-878F-EE97F6914E49>