Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #93335
| References | (1 earlier) <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 | 2015-06-30 09:40 -0600 |
| Subject | Re: Linear time baseconversion |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.193.1435680388.3674.python-list@python.org> (permalink) |
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
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