On Mon, Oct 2, 2017 at 10:24 PM, bartc <b...@freeuk.com> wrote: > On 02/10/2017 08:41, Peter Otten wrote: >> >> Daniel Bastos wrote: >> >>> def make_sequence_non_recursive(N, x0 = 2, c = -1): >>> "What's wrong with this function? It's very slow." >>> last = x0 >>> def sequence(): >>> nonlocal last >>> next = last >>> last = last**2 + c >>> return next % N >>> return sequence > > >>>>> x.bit_length() >> >> 12534884 >> >> So at this point it alreay would take 1.5 MB to store the number in >> binary. >> The actual format requires even a bit more memory: >> >>>>> import sys >>>>> sys.getsizeof(x) >> >> 1671344 >> >> So for every operation you have to touch a lot of memory -- and that takes >> time. > > > If it recalculates 'last' once for each of those couple of dozen printed > lines, that I doubt accessing a few MB of memory is the issue. More doing > such a big calculation.
Yes, but when you're working with a number with that many limbs, it's bound to take some time. Squaring arbitrary numbers is a big job - it's more efficient than O(n²) but still a lot worse than linear time, so on huge numbers it's going to take hugely huge time. *handwave furiously* ChrisA -- https://mail.python.org/mailman/listinfo/python-list