Python BUG?

[Tim Peters]

[Oleg Orlov]
> This script:
>
> d = [1L, 2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L,
>     10L, 9L, 8L, 7L, 6L, 5L, 4L, 3L, 2L, 1L]
> print reduce(lambda x, y: x*x + y*y, d)
>
> hangs up my python interpreter (on NT4).
>
> Is it a bug or my mistake?
> How about UNIX?

[Oleg Broytmann]
>    My computer worked about 10 minutes and printed a very looong
> result. :)
> Pentium-150, Debian GNU/Linux.

This is a cute one!  It's much faster than you think <wink>.

Do x=reduce(...) instead of printing it, and it should take about 30 seconds
on your machine.

The enormous expense here isn't the (unintended) iterated squaring, it's the
conversion of the gigantic result (well over 300,000 bits) into a base-10
string (on the order of 100,000 digits).

Conversion to decimal is a quadratic-time (in the number of bits) process.
Converting to a hex (hex(x)) or octal string instead is almost instantaneous
(in Python 1.5.2; in earlier Pythons conversion to hex was also
quadratic-time).

longs-have-subtleties-too-ly y'rs  - tim