Skip to content

Improve good_size and export to python

Peter Bell requested to merge good_size into master

This improves the algorithm for good_size. The main observation is that division by 2 is cheap, so we can alternate between multiplying by 3 and dividing by 2 to reduce the search space to only numbers near n. This also adds an early return when n matches a composite number. You can play around with the micro-benchmarks here (this is good_size2).

This also adds a variant for real transforms with 5-smooth numbers and exports both of them to python as a single function.

Edited by Peter Bell

Merge request reports