utils Module - maccergit/Euler GitHub Wiki

This is a Python module that provides utility functions imported by the other projects.

To Use

  1. Make sure the "utils" project is also checked out, in addition to the project being worked on. For example, if working on prob011, both "prob011" and "utils" will need to be checked out into the workspace - here is what they looked like when fully expanded in Eclipse (use the "twisties" on the left of the entries to expand the tree) - the name on the right of the project entries will be the name of your GitHub repo holding the project :
  1. The project that will import the utilities needs to "reference" the "utils" project. Thus, the "prob011" project will need to reference the "utils" project. Do this right-clicking on the "prob011" project, select "Properties" to bring up the project properties, and then select "Project References" to show the projects that can be referenced. Check "utils", and then "Apply and Close" :
  1. The project needing to use functionality from the "utils" module can now import the "utils" module call code from the module :
import utils.timing
utils.timing.table_timing([1, 4], count, scale)
utils.timing.plot_timing([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], count, scale, "prob0011.01")

utils.factor.gen_factors(limit)

This generator will return the prime factors one at a time for a provided value. Once the last factor is returned, the generator exits. To get all of the factors in a single unit, use a Python comprehension to repeatedly call the generator :

>>> import utils.factor
>>> [x for x in utils.factor.gen_factors(120)]
[2, 2, 2, 3, 5]

alternatively, use the unpack operator :

>>> [*utils.factor.gen_factors(120)]
[2, 2, 2, 3, 5]

However, the SymPy and pyprimesieve libraries have much faster factoring calls, and should be used instead.

utils.factor.factPow(limit)

Returns a dictionary of prime factors for a provided value. The keys are the prime factor values, and the associated values are the power of the primer factor. Example :

>>> import utils.factor
>>> utils.factor.factPow(2)
{2: 1}
>>> utils.factor.factPow(3)
{3: 1}
>>> utils.factor.factPow(4)
{2: 2}
>>> utils.factor.factPow(12)
{2: 2, 3: 1}
>>> utils.factor.factPow(180)
{2: 2, 3: 2, 5: 1}

utils.factor.gen_divisors(limit)

Generates all the divisors for a given value (not the prime factors), including 1 and the number itself. The order is not specified, which allows for the use of a faster algorithm - so it's best to think of it as a set :

>>> {*utils.factor.gen_divisors(120)}
{1, 2, 3, 4, 5, 6, 40, 8, 10, 12, 15, 20, 120, 24, 60, 30}

utils.factor.sumDivisors(limit)

Returns the sum of the divisors for a given value. This is basically the same as :

sum{gen_divisors(limit))

but uses a much faster algorithm.

utils.fastfactor.*

The fastfactor utilities contain "drop-in" replacements for the functions in utils.factor - but these are implemented using fast libraries instead of pure Python. Many of the functions use factoring in their implementation, and the pyprimesieve library is used here to improve performance by orders of magnitude. If you use the "import ... as ..." syntax, you can simply change the library in one line, and all the referenced functions will use the new library.

utils.prod.prod(iterable)

This simply returns the product of multiplying each element of "iterable" :

\displaystyle {\prod{elem}}, \forall \text{ } elem \in iterable

However, as of Python 3.8, "math.prod()" is available - it's faster, and should be used instead.

utils.timing

Used to provide a wrapper around the Python "timeit" module to produce tabular or graphical display of performance of solutions. Each of the projects uses these to provide timing info so we can compare algorithms and implementations. Values for "count" and "scale" are typically chosen by hand using trial and error to come up with reasonable values that provide good timing information while still running in a reasonable amount of time (typically a couple seconds). For example, if a solution tends to run in the milliseconds range, and I want to plot 10 points, then I will pick a count size of 100 : 100 count * 10 plot points * msec yields a total time in the seconds range. Depending on how noisy the data is, the average of 100 runs / plot point may be good enough.

There are three functions defined :

timing(parm, count, scale)

Wraps "timeit" to call the "solution()" method defined in each problem. Assumes "solution()" takes a parameter, which is passed through from the provided arguments. "timeit" is set up to run "solution()" multiple times, as specified by "count", and then an average time is computed. The resulting time is then multiplied by "scale" to allow for return values in scales other than seconds.

table_timing(parms, count, scale)

Steps through the provided "parms" to run several timing runs. "count" and "scale" are passed to the timing call above, along with the current part, to get a timing result for that parm. The results are printed out in tabular format with an autogenerated title composed of the problem name and the solution number extracted from the OS path of the solution.

plot_timing(parms, count, scale, ticks = True)

Similar to "table_timing()" above, but the results are graphed using PyPlot. "scale" is also used to determine a scale key on the time axis of the plot (sec, msec, µsec, or nsec). Default behavior is to use every provided parm as a tick on the x-axis, but when there are more than 10-20 points, the ticks overlap and are messy - setting "ticks" to "False" allows PyPlot to automatically determine what ticks to use for the x-axis.