Since this started, I've been using variants of the following in my own
code, wrapping `accumulate`:
from itertools import accumulate, chain, cycle, islice
def accum(iterable, func=None, *, initial=None, skipfirst=False):
if initial is not None:
iterable = chain([initial], iterable)
if func is None:
iterable = accumulate(iterable)
else:
iterable = accumulate(iterable, func)
if skipfirst:
iterable = islice(iterable, 1, None)
return iterable
I quite like it! It handles everything that's come up pretty naturally. A
difference from what was discussed before: I opposed having a `skipfirst`
argument because I didn't want an optional argument that _only_ applied if
another optional argument was specified. But `skipfirst` in the above
applies regardless of whether `initial` is specified. It turned out to be
useful in cases where the _effect_ of `initial` had been gotten instead via
slamming the initial value into the first object returned by `iterable`,
and then ignored later by a special first case to throw away the first
result `accumulate` returned.
I'm writing this now because it turned out I used it eight times yesterday,
which raised it above background noise level ;-)
The first use captures a sequence countless thousands of Python programmers
have crafted in various ways by hand:
def firstfactor(n, limit=1000):
for p in chain([2, 3],
accum(cycle([2, 4]), initial=5)):
# 2, 3, and integers not divisible by 2 or 3
# 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, ...
if p*p > n:
return n
if p > limit:
return 0
if n % p == 0:
return p
The same sequence can be gotten more obscurely via:
for p in chain([2, 3],
accum(cycle([4, 2]), initial=1, skipfirst=True)):
The remaining 7 uses were in transcribing's Lehman's elegant[1]
optimization of Fermat's "difference of squares" factorization method:
def large(deltas, init):
for k in accum(cycle(deltas), initial=init):
...
# ints divisible by 30
large([30], 30)
# ints divisible by 24 but not by 30
large([24, 24, 24, 48], 24)
# ints divisible by 12 but not by 30 or 24
large([24, 48, 24, 24], 12)
# ints divisible by 18 but not by 30, 24, or 12
large([36, 72, 36, 36], 18)
# ints divisible by 6 but not by 30, 24, 12, or 18
large([36, 24, 12, 24, 12, 24, 36, 12], 6)
# ints divisible by 2 but not by 30, 24, 12, 18, or 6
large([2, 4], 2)
# ints not divisible by 30, 24, 12, 18, 6, or 2
large([2], 1)
Lehman built his sequence generator "by hand" in Algol. where the delta
array (`c` in his code) is inherited from `large`'s enclosing scope, and
`large()` is passed just the number of deltas and the initial value. A
more literal transcription of his code would have used:
def large(deltas, init):
for k in accum(cycle(deltas), initial=init, skipfirst=True):
...
instead with the delta lists rotated and with a different initial value.
For example, instead of
large([24, 24, 24, 48], 24)
above his code uses
large([48, 24, 24, 24], -24)
The latter needs to ignore the initial (-24) value (except to add it to the
first delta: -24 + 48 = 24). That was more natural in context, due to the
way he advanced the generated in a `while True:` loop built out of gotos ;-)
[1]
https://math.boisestate.edu/~liljanab/Cryptology1Fall2013/LehmanFactoring.pdf
Historical gloss: Lehman surprisingly transformed Fermat's O(n) method
into an O(cube_root(n)) method. I believe that was the first deterministic
factoring method known beating trial division's O(sqrt(n)) time. Alas for
Lehman, Pollard very soon after published his `rho` method, which runs in
probabilistic O(sqrt(p)) time where p is n's smallest prime factor, so in
worst-case probabilistic O(fourth_root(n)) time. That relegated Lehman's
method to an academic curiosity, although it remains supremely effective if
N is the product of two odd primes whose ratio is close to a fraction with
"small" numerator and denominator.
_______________________________________________
Python-ideas mailing list
[email protected]
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/
