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

Groups > comp.lang.python > #93335

Re: Linear time baseconversion

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.015
X-Spam-Evidence '*H*': 0.97; '*S*': 0.00; 'base.': 0.05; 'binary': 0.05; 'linear': 0.07; 'subject:skip:b 10': 0.07; 'logic': 0.09; 'bug': 0.10; 'def': 0.14; 'algorithmic': 0.16; 'complexity,': 0.16; 'hexadecimal': 0.16; 'scope.': 0.16; 'wrote:': 0.16; 'integer': 0.18; '>>>': 0.20; '(the': 0.22; 'am,': 0.23; '2015': 0.23; 'header:In-Reply-To:1': 0.24; 'converting': 0.27; 'operations,': 0.27; 'sequence': 0.27; 'message- id:@mail.gmail.com': 0.28; 'division': 0.29; 'function:': 0.29; 'value)': 0.29; 'subject:time': 0.31; "can't": 0.32; 'true.': 0.33; 'received:google.com': 0.34; 'to:addr:python-list': 0.35; 'faster': 0.36; 'subject:: ': 0.37; "skip:' 20": 0.37; 'tue,': 0.38; 'christian': 0.38; 'to:addr:python.org': 0.39; 'where': 0.40; 'some': 0.40; '30,': 0.63; 'relatively': 0.63; 'different': 0.64; 'therefore': 0.65; 'believe': 0.67; 'square': 0.76; 'faster.': 0.84; 'gollwitzer': 0.84; 'to:name:python': 0.84; 'ratio': 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=bmPwO8/DLQWpQBZ1Fy7Q1vYoThlReIzfqsjLWTPcR2Y=; b=jxjCGKVBZuXSchDJKatFNqxzOuYXXLppYmDaLSnYESzv8YrpPOoyhwS9ltMesLT92Z vxvTiRmbkbI9NRQY4djOCKA8UaAn4lR+35SZdg18Qk5kMEHEFOOiHNPN+gFQvga+rXSU Njk22e40Sp2ckRw3o0+5zojRLZC9pWysvZwV064eL1MADQ9bkDT6x8o6tBEEg8z5lW11 FS/ROLPgF25IUIsaVu2JxEwdW50ZYVV2WlzNhHFExOuwhnnhVmuueSvQsmAaTiaU9QiJ POyYJjdV7u+NuM8NfC2xpUtyKDUEGWou4p+/kohoJHsPdZwpVk1UMo8+K2jGu4KO08uJ j9dA==
X-Received by 10.170.141.4 with SMTP id i4mr26345696ykc.32.1435678872163; Tue, 30 Jun 2015 08:41:12 -0700 (PDT)
MIME-Version 1.0
In-Reply-To <mmtm6k$8b7$1@dont-email.me>
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>
From Ian Kelly <ian.g.kelly@gmail.com>
Date Tue, 30 Jun 2015 09:40:32 -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.193.1435680388.3674.python-list@python.org> (permalink)
Lines 28
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1435680388 news.xs4all.nl 2917 [2001:888:2000:d::a6]:38833
X-Complaints-To abuse@xs4all.nl
Path csiph.com!usenet.pasdenom.info!news.stben.net!border1.nntp.ams1.giganews.com!nntp.giganews.com!newsfeed.xs4all.nl!newsfeed7.news.xs4all.nl!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Xref csiph.com comp.lang.python:93335

Show key headers only | View raw

On Tue, Jun 30, 2015 at 3:07 AM, Christian Gollwitzer <auriocus@gmx.de> wrote:
> Am 30.06.15 um 10:52 schrieb jonas.thornvall@gmail.com:
>>
>> It still bug out on very big numbers if base outside integer scope.
>> I am very keen on suggestions regarding the logic to make it faster.
>
>
> Concerning the algorithmic complexity, it can't be faster than square time
> in the number of digits N. Baseconversion needs to do a sequence of division
> operations, where every operation gves you one digit in the new base. The
> number of digits in the new base is proportional to the number of digits in
> the old base (the ratio is log b1/log b2). Therefore it will be O(N^2).

I don't think that's true. Here's a linear hexadecimal to binary function:

>>> def hextobin(value):
...     digits = {'0': '0000', '1': '0001', '2': '0010', '3': '0011',
...         '4': '0100', '5': '0101', '6': '0110', '7': '0111',
...         '8': '1000', '9': '1001', 'A': '1010', 'B': '1011',
...         'C': '1100', 'D': '1101', 'E': '1110', 'F': '1111'}
...     return ''.join(digits[d.upper()] for d in value)
...
>>> hextobin('3f')
'00111111'

I believe this approach can be extended to arbitrary bases with some
effort, although for converting arbitrary base b1 to b2, you would
need up to b2 different mappings if b1 and b2 are relatively prime.

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