Iteration over recursion?

[Nick Maclaren]

Re: Iteration over recursion?


In article <1150873424.345 733.165730@m73g 2000cwd.googleg roups.com>,
"Kay Schluehr" <kay.schluehr@g mx.net> writes:
|>
|> You might use a separate prime generator to produce prime factors. The
|> factorize algorithm becomes quite simple and configurable by prime
|> generators. For demonstration purposes I use the eratosthenes sieve.

That is a good point. The differences between iteration and recursion
are well-understood (by some people, at least), but the difference
between those two and generators is not. I have mixed feelings whether
they are a good idea or not, largely because I have never seen a
language that provides a declaration to guarantee that a generator is
'clean'. And an unclean generator (e.g. one with side-effects) is a
most revolting object, from a software engineering (including validation)
point of view.

One good example of this is streaming input (I/O). Traditional,
clean streaming input can be implemented efficiently and with good
error diagnostics. The unclean C- and POSIX-like streaming input can't
be, or at least only one of the two can be provided at once.


Regards,
Nick Maclaren.

[Tim Peters]

Re: Iteration over recursion?

[Kay Schluehr][color=blue]
> You might use a separate prime generator to produce prime factors. The
> factorize algorithm becomes quite simple and configurable by prime
> generators.[/color]

Alas, yours was _so_ simple that it always takes time proportional to
the largest prime factor of n (which may be n) instead of worst-case
time proportional to sqrt(n). Repair that, and it's not quite so
simple anymore. The speed of the sieve generator would also benefit a
lot by never looking at even integers, beyond an initial "yield 2" ...
the OP said he was looking for speed more than elegance, and they're
not good buddies here ;-)
[color=blue]
> def eratosthenes():
> memo = {}
> q = 2
> while True:
> p = memo.pop(q, None)
> if p is None:
> yield q
> memo[q*q] = q
> else:
> x = p + q
> while x in memo:
> x += p
> memo[x] = p
> q+=1
>
> def factorize(n, sieve = eratosthenes):
> if n <= 1:
> return [n]
> factors = []
> primes = sieve()
> for q in primes:
> while n % q == 0:
> factors.append( q)
> n //= q
> if n == 1:
> return factors[/color]

At _some_ point you might think that's bound to be faster than only
skipping multiples of 2 and 3, because it does fewer divisions. But
to get to a particular prime p, the sieve there has to go around its
outer loop about 3x as often as the trial() function goes around its
inner loop, and grows a dict with about p/ln(p) entries (while the
trial() function's memory use is constant), and those aren't free.

Applied to 9999991**2 (constructed so that both functions take time
proportional to sqrt(n)), on my box the factorize() function took 4x
longer than trial() (approximately 16 seconds versus 4). Trial
division isn't practical for such large inputs, but I picked the
square of a "large" prime to give factorize() maximum advantage in
skipping division attempts (by the time we get to a prime p,
factorize() tries about p/ln(p) divisions, while trial() does about
p/3; so trial() does about ln(p)/3 times as many divisions as
factorize(): the larger the p we need, the larger that _factor_
gets).

Alas, it appears that made the dict so big that cache faults on dict
accesses more than wiped out the division advantage. At the smaller
999983**2, factorize() took only about 3.6x longer, despite losing
some of its relative division advantage.

In short, it's never what you think it is ;-)

[MTD]

Re: Iteration over recursion?

I've been testing my recursive function against your iterative
function, and yours is generally a quite steady 50% faster on
factorizing 2**n +/- 1 for 0 < n < 60. I think that, for a challenge,
I'll try to make a recursive function that matche or beats the
iterative function -- it's worth the experiment!

Cheers,
MTD

[Tim Peters]

Re: Iteration over recursion?

[MTD <marc.t.davies@ gmail.com>][color=blue]
> I've been testing my recursive function against your iterative
> function, and yours is generally a quite steady 50% faster on
> factorizing 2**n +/- 1 for 0 < n < 60.[/color]

If you're still not skipping multiples of 3, that should account for most of it.
[color=blue]
> I think that, for a challenge, I'll try to make a recursive function that
> matche or beats the iterative function -- it's worth the experiment![/color]

Don't stop on that one before you succeed ;-) Provided you make no
more than one recursive call per factor, you can't make more than
log(n, 2) recursive calls in total, and _typically_ far fewer than
that. IOW, the number of recursive calls should generally be trivial,
and factoring 2**n will be the worst case.