Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #102756

Re: Why Python is slow

Show all headers | View raw

Richard Heathfield <rjh@cpax.org.uk> writes:

> [.. evaluating 3 ** 3 ** 3 ** 3 ..]
>
> 3 to the power 3 took 0.008 seconds on my system.
>
> 3 to the power 27 took 0.018 seconds.
>
> I bottled out of the full monty, but:
>
> 3 to the power 81 took 0.029 seconds.
> 3 to the power 243 took 0.042 seconds.
> 3 to the power 729 took 0.111 seconds.
> 3 to the power 2187 took 0.740 seconds.
> 3 to the power 6561 took 6.427 seconds.
> 3 to the power 19683 took 56.875 seconds.
>
> Multiplying the power term by 3, then, seems to multiply the
> run-time by about 9.  So we can estimate the time it would take
> (machine resources permitting) to perform 3 to the power
> 7625597484987 as 56.875 * (9 to the power 22), which is roughly
> 1,774,861,793,744,000 years.

The timings given suggest an algorithm that is O( n**2 ).  There
are faster (and also still practical) algorithms.

> You can probably cut this time down a lot by using bigger bigits
> (my bigits are deliberately small, 0-255).

For results of this size, a better way is to use an algorithm
that is O( n ** (log2 3) ) or O( n * log n * log log n ).  I
believe python uses an O( n ** (log2 3) ) algorithm.  It looks
like an O( n * log n * log log n ) algorithm could complete (if
running on a system with several terabytes of ram) in one or two
digits of CPU months.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Why Python is slow thunderbirdmember@gmail.com - 2017-01-24 10:22 -0800
  Re: Why Python is slow Richard Heathfield <rjh@cpax.org.uk> - 2017-01-24 18:33 +0000
  Re: Why Python is slow Richard Heathfield <rjh@cpax.org.uk> - 2017-01-24 20:14 +0000
    Re: Why Python is slow luser droog <luser.droog@gmail.com> - 2017-01-26 10:13 -0800
    Re: Why Python is slow Tim Rentsch <txr@alumni.caltech.edu> - 2017-01-30 05:50 -0800
  Re: Why Python is slow bart4858@gmail.com - 2017-01-24 13:21 -0800
  Re: Why Python is slow BartC <bc@freeuk.com> - 2017-01-24 22:23 +0000
  Re: Why Python is slow "Chris M. Thomasson" <invalid@invalid.invalid> - 2017-01-24 17:11 -0800
    Re: Why Python is slow "Chris M. Thomasson" <invalid@invalid.invalid> - 2017-01-24 19:26 -0800
    Re: Why Python is slow "Chris M. Thomasson" <invalid@invalid.invalid> - 2017-01-25 12:50 -0800
      Re: Why Python is slow BartC <bc@freeuk.com> - 2017-01-25 21:52 +0000
        Re: Why Python is slow "Chris M. Thomasson" <invalid@invalid.invalid> - 2017-01-25 14:30 -0800
          Re: Why Python is slow BartC <bc@freeuk.com> - 2017-01-25 22:59 +0000
            Re: Why Python is slow "Chris M. Thomasson" <invalid@invalid.invalid> - 2017-01-27 13:20 -0800
      Re: Why Python is slow DFS <nospam@dfs.com> - 2017-01-25 19:22 -0500
        Re: Why Python is slow "Chris M. Thomasson" <invalid@invalid.invalid> - 2017-01-26 13:40 -0800
  Re: Why Python is slow David Brown <david.brown@hesbynett.no> - 2017-01-25 10:29 +0100
    Re: Why Python is slow gazelle@shell.xmission.com (Kenny McCormack) - 2017-01-25 10:38 +0000
    Re: Why Python is slow Malcolm McLean <malcolm.mclean5@btinternet.com> - 2017-01-26 06:44 -0800
      Re: Why Python is slow Richard Heathfield <rjh@cpax.org.uk> - 2017-01-26 15:00 +0000
        Re: Why Python is slow Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-01-26 17:23 +0000
          Re: Why Python is slow supercat@casperkitty.com - 2017-01-26 09:42 -0800
            Re: Why Python is slow Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-01-26 18:24 +0000
      Re: Why Python is slow David Brown <david.brown@hesbynett.no> - 2017-01-26 16:14 +0100
        Re: Why Python is slow Malcolm McLean <malcolm.mclean5@btinternet.com> - 2017-01-26 12:49 -0800
          Re: Why Python is slow Robert Wessel <robertwessel2@yahoo.com> - 2017-01-26 15:11 -0600
          Re: Why Python is slow David Brown <david.brown@hesbynett.no> - 2017-01-26 23:56 +0100
        Re: Why Python is slow Keith Thompson <kst-u@mib.org> - 2017-01-26 15:20 -0800
          Re: Why Python is slow David Brown <david.brown@hesbynett.no> - 2017-01-27 09:31 +0100
      Re: Why Python is slow fir <profesor.fir@gmail.com> - 2017-01-27 07:24 -0800
        Re: Why Python is slow fir <profesor.fir@gmail.com> - 2017-01-27 07:57 -0800
          Re: Why Python is slow fir <profesor.fir@gmail.com> - 2017-01-27 08:46 -0800
        Re: Why Python is slow supercat@casperkitty.com - 2017-01-27 08:06 -0800
          Re: Why Python is slow fir <profesor.fir@gmail.com> - 2017-01-27 08:39 -0800
            Re: Why Python is slow fir <profesor.fir@gmail.com> - 2017-01-27 13:29 -0800
  Re: 3**3**3**3 Noob <root@127.0.0.1> - 2017-01-27 14:33 +0100

csiph-web