Factorisation.hpp File Reference

Plans for the module on factorisation of natural numbers. More...

Go to the source code of this file.

Detailed Description

Plans for the module on factorisation of natural numbers.

Tools for finding factorisations n = a * b.

Literature review
  • Literature on factorisation via SAT and CSP.
  • Literature on factorisation in general.
  • Literature on efficient multiplication.
Interesting good constraint representations
  • Boolean CNF:
    1. Of course, a generator for the standard school method needs to be implemented.
    2. And then generators exploiting more complicated methods should be investigated.
  • Constraints in general:
    1. The next thing is to use a representation as an alliance of (strong) active clause-sets, using the school method, but for an arbitrary basis b, which gives the domain size for the variables. In this way we can optimise on b.

      (Strong) Active clause-sets for addition and multiplication of digits seem most natural. A further parameter could be the number k of digits considered as one block (or should this be handled by using a larger b? seems so!).

      The implementation of strong active clause-sets likely utilises (large) tables, and possibly finite automata. From constraints a+b=c we might get equations, so we need them as literals; from constraints a*b=c we could also get for example a=c/b, and the question is whether we should handle also such functional dependencies.

    2. Likely the more complicated multiplications algorithms allow a nicer representation using constraints --- of course the challenge is to find good constraints!
    3. We can also investigate different representations of numbers (not using the decimal expansion).
    4. And from methods for factorisation perhaps we could infer additional constraints (at least).

Definition in file Factorisation.hpp.