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

Groups > comp.lang.python > #93331

Re: Linear time baseconversion

Path csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed7.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path <ian.g.kelly@gmail.com>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.062
X-Spam-Evidence '*H*': 0.88; '*S*': 0.00; 'linear': 0.07; 'subject:skip:b 10': 0.07; 'calculating': 0.09; 'sake': 0.09; 'algorithm': 0.13; 'times,': 0.13; 'dig': 0.16; 'growth.': 0.16; 'linear,': 0.16; 'quadratic': 0.16; 'wrote:': 0.16; "wouldn't": 0.16; 'input': 0.18; 'constant': 0.22; 'am,': 0.23; 'code,': 0.23; '2015': 0.23; 'header:In-Reply-To:1': 0.24; 'message- id:@mail.gmail.com': 0.28; "i'm": 0.29; 'factor': 0.29; 'lines': 0.30; 'subject:time': 0.31; 'maybe': 0.31; 'doubt': 0.33; 'me?': 0.34; 'received:google.com': 0.34; 'to:addr:python-list': 0.35; 'being': 0.36; '(i.e.': 0.36; 'subject:: ': 0.37; 'tue,': 0.38; 'does': 0.39; 'to:addr:python.org': 0.39; 'seem': 0.39; 'increased': 0.61; 'become': 0.62; 'matter': 0.63; '30,': 0.63; '500': 0.63; 'results': 0.66; 'analysis': 0.70; 'algorithm,': 0.84; 'complexity': 0.84; 'estimation': 0.84; 'proving': 0.84; 'taken.': 0.84; 'to:name:python': 0.84; 'doubling': 0.91
DKIM-Signature v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; bh=DUezcHBp1lBqTKU3JnJDMM3wt5WVVihgqj2uDs7quA4=; b=PnvB9Tsn136/O74fD9PlCMNqA2PT6HYdAEoDGNpFC1JLqN2mm6NpdSoA0fAIiXhnTG j8WV0nShlUUiInBM4e6RkPXcOtnj+h5tYxu2nAcs8Qe58TOCuosqi/j5pKR8v4UUNAgr Tl48Y1q+2Fng1VgEjpPjZjKlYXt7s4QTJmA3rIl48iW0j2dpRoRYG+p9kxCTu5TLLOIO BrA0O63ntNWnpuXnUsvaQ1WP/9TRlQBv1f9JFkG1QizbzDaNoWWmB0ZOJjJedNSCUIaE tyGD7qCFE7gQoOtb9pyAP6WEUo8p5hglWd5PwyJIwI4w5o6hsDrh18jS/H+EqF7nIPLi 1eQg==
X-Received by 10.13.251.199 with SMTP id l190mr26640594ywf.148.1435678218926; Tue, 30 Jun 2015 08:30:18 -0700 (PDT)
MIME-Version 1.0
In-Reply-To <84ac9885-f0f2-47fb-92bc-a856ede6d818@googlegroups.com>
References <777831f0-d4b4-48f6-ae0b-c9b1ea7ffc06@googlegroups.com> <CALwzidms2BGRjHCuLB5_uszbx9Q-rdtOob_LGHQoO3K3ZD=Q7Q@mail.gmail.com> <mailman.175.1435619500.3674.python-list@python.org> <87r3ouawgt.fsf@bsb.me.uk> <7c6dac9d-5722-4179-bd7e-ceaac6698490@googlegroups.com> <mmtm6k$8b7$1@dont-email.me> <c92c3dc9-8a00-4244-bbd7-383f34983935@googlegroups.com> <0439e7f6-2604-4a07-802b-81ea03782f62@googlegroups.com> <332f7cc7-4cc7-469f-a1c3-cbba40b7b641@googlegroups.com> <84ac9885-f0f2-47fb-92bc-a856ede6d818@googlegroups.com>
From Ian Kelly <ian.g.kelly@gmail.com>
Date Tue, 30 Jun 2015 09:29:39 -0600
Subject Re: Linear time baseconversion
To Python <python-list@python.org>
Content-Type text/plain; charset=UTF-8
X-BeenThere python-list@python.org
X-Mailman-Version 2.1.20+
Precedence list
List-Id General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive <http://mail.python.org/pipermail/python-list/>
List-Post <mailto:python-list@python.org>
List-Help <mailto:python-list-request@python.org?subject=help>
List-Subscribe <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups comp.lang.python
Message-ID <mailman.189.1435678221.3674.python-list@python.org> (permalink)
Lines 20
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1435678221 news.xs4all.nl 2875 [2001:888:2000:d::a6]:53065
X-Complaints-To abuse@xs4all.nl
Xref csiph.com comp.lang.python:93331

Show key headers only | View raw

On Tue, Jun 30, 2015 at 8:13 AM,  <jonas.thornvall@gmail.com> wrote:
>> Regarding the time it seem to double the digits quadruple the time. And that is still linear or?
>
> 2x seem linear to me?

That's not linear, nor is it "2x". If doubling the size of the input
quadruples the time, then doubling the size of the input twice (i.e.
quadrupling the size of the input) results in the time being increased
by a factor of 16. Double it three times, and the time taken is
increased by a factor of 64. That's quadratic behavior.

If the algorithm were actually linear, then a constant factor of "2x"
wouldn't matter when calculating the growth. Doubling the size of the
input would simply double the time taken.

Of course, this is just an empirical estimation of the asymptotic
complexity of the algorithm, not a proof. Maybe after 10,000 digits it
actually does become linear, although I doubt it. Proving it would
require analysis of the code, and I'm not willing to dig into 500
lines of Javascript just for the sake of it.

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

Thread

Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-29 15:39 -0700
  Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-29 16:56 -0600
  Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-29 17:10 -0600
    Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-29 16:23 -0700
    Re: Linear time baseconversion Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-06-30 01:09 +0100
      Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 01:52 -0700
        Re: Linear time baseconversion Christian Gollwitzer <auriocus@gmx.de> - 2015-06-30 11:07 +0200
          Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 02:20 -0700
          Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 02:34 -0700
            Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 02:43 -0700
              Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 06:22 -0700
                Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 07:13 -0700
                Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-30 09:29 -0600
          Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-30 09:45 -0600
          Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-30 09:40 -0600
            Re: Linear time baseconversion Christian Gollwitzer <auriocus@gmx.de> - 2015-07-01 00:22 +0200
          Re: Linear time baseconversion Chris Angelico <rosuav@gmail.com> - 2015-07-01 02:10 +1000
          Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-30 10:34 -0600
            Re: Linear time baseconversion Christian Gollwitzer <auriocus@gmx.de> - 2015-07-01 00:27 +0200
    Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-29 23:49 -0700
  Re: Linear time baseconversion Michael Torrie <torriem@gmail.com> - 2015-06-30 10:12 -0600
    Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 09:24 -0700
      Re: Linear time baseconversion Michael Torrie <torriem@gmail.com> - 2015-06-30 13:55 -0600

csiph-web