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

Groups > comp.lang.python > #93298 > unrolled thread

Linear time baseconversion

Back to article view | Back to comp.lang.python

Contents

  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

Page 1 of 2  [1] 2  Next page →

#93298 — Linear time baseconversion

http://jt.node365.se/baseconversion8.html 

[toc] | [next] | [standalone]

#93299

On Mon, Jun 29, 2015 at 4:39 PM,  <jonas.thornvall@gmail.com> wrote:
> http://jt.node365.se/baseconversion8.html

Back of the envelope mental calculation, that appears to be quadratic,
not linear. Doubling the length of the input results in an approximate
quadrupling of the time taken to produce the output.

That noted, this is off-topic for this list, which is for discussion
about Python. Please take this to somewhere else like
comp.lang.javascript instead.

[toc] | [prev] | [next] | [standalone]

#93300

On Mon, Jun 29, 2015 at 4:56 PM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> On Mon, Jun 29, 2015 at 4:39 PM,  <jonas.thornvall@gmail.com> wrote:
>> http://jt.node365.se/baseconversion8.html
>
> Back of the envelope mental calculation, that appears to be quadratic,
> not linear. Doubling the length of the input results in an approximate
> quadrupling of the time taken to produce the output.
>
> That noted, this is off-topic for this list, which is for discussion
> about Python. Please take this to somewhere else like
> comp.lang.javascript instead.

By the way, I think you have a bug. I did my time testing by
concatenating the default input number to itself several times. At
5184 decimal digits, which was the last case I tried, the 58th output
digit was 1111111, after which point the remaining 672 output digits
are all 12665464, which seemed rather improbable.

[toc] | [prev] | [next] | [standalone]

#93301

Den tisdag 30 juni 2015 kl. 01:11:51 UTC+2 skrev Ian:
> On Mon, Jun 29, 2015 at 4:56 PM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> > On Mon, Jun 29, 2015 at 4:39 PM,  <jonas.thornvall@gmail.com> wrote:
> >> http://jt.node365.se/baseconversion8.html
> >
> > Back of the envelope mental calculation, that appears to be quadratic,
> > not linear. Doubling the length of the input results in an approximate
> > quadrupling of the time taken to produce the output.
> >
> > That noted, this is off-topic for this list, which is for discussion
> > about Python. Please take this to somewhere else like
> > comp.lang.javascript instead.
> 
> By the way, I think you have a bug. I did my time testing by
> concatenating the default input number to itself several times. At
> 5184 decimal digits, which was the last case I tried, the 58th output
> digit was 1111111, after which point the remaining 672 output digits
> are all 12665464, which seemed rather improbable.

No there is no bug, try 12665465^77 wolfram alpha gives
7976781785088446084873306945009387424538813088491673402748035781202063831184317457635773873975198429536727051788368983080016275695338973787545408588270715883570324803120051806974411884509607864124408509087974736382639726555779113221450078243163340395784592348080359062163885323462144257596380766496966084237358222613649636595300081207683175410584139478853066960795599027150403706812116411354218686846750615496852415389467898730884554700066802269059177874281189887271741594702334892800692129299635716260471508809448693000376806594431400299072265625

Try that number you get a ONE followed by 77 ZEROS

[toc] | [prev] | [next] | [standalone]

#93302

Ian Kelly <ian.g.kelly@gmail.com> writes:

> On Mon, Jun 29, 2015 at 4:56 PM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
>> On Mon, Jun 29, 2015 at 4:39 PM,  <jonas.thornvall@gmail.com> wrote:
>>> http://jt.node365.se/baseconversion8.html
<snip>
> By the way, I think you have a bug. I did my time testing by
> concatenating the default input number to itself several times. At
> 5184 decimal digits, which was the last case I tried, the 58th output
> digit was 1111111, after which point the remaining 672 output digits
> are all 12665464, which seemed rather improbable.

Yes, it's a bug.  Because it's off-topic, I won't say more here but I
posted a simpler test case to comp.lang.javacript just now (10000000
converted to base 100).  I would not normally reply here, but I wanted
to acknowledge your post as prompting me to look for other cases.
Followup-to: set.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#93317

Den tisdag 30 juni 2015 kl. 02:09:17 UTC+2 skrev Ben Bacarisse:
> Ian Kelly <ian.g.kelly@gmail.com> writes:
> 
> > On Mon, Jun 29, 2015 at 4:56 PM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> >> On Mon, Jun 29, 2015 at 4:39 PM,  <jonas.thornvall@gmail.com> wrote:
> >>> http://jt.node365.se/baseconversion8.html
> <snip>
> > By the way, I think you have a bug. I did my time testing by
> > concatenating the default input number to itself several times. At
> > 5184 decimal digits, which was the last case I tried, the 58th output
> > digit was 1111111, after which point the remaining 672 output digits
> > are all 12665464, which seemed rather improbable.
> 
> Yes, it's a bug.  Because it's off-topic, I won't say more here but I
> posted a simpler test case to comp.lang.javacript just now (10000000
> converted to base 100).  I would not normally reply here, but I wanted
> to acknowledge your post as prompting me to look for other cases.
> Followup-to: set.
> 
> -- 
> Ben.

Thank you, for finding the bug Ben, it turned out i did basicly same thing two times. One of the times was the more general case and that turned out to do the correct thing.

jt.node365.se/baseconversion9.html

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.
I will read in base into an array holding bignumb, and then it should work for anybase and any number as far i can understand. 

[toc] | [prev] | [next] | [standalone]

#93318

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).

	Christian

[toc] | [prev] | [next] | [standalone]

#93321

Den tisdag 30 juni 2015 kl. 11:08:01 UTC+2 skrev Christian Gollwitzer:
> 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).
> 
> 	Christian

There is not a single division "except for the 2 one, used in halfinterval search" 
This algorithm only use multiplication and a modified GCD search algorithm.

http://jt.node365.se/baseconversion9.html

[toc] | [prev] | [next] | [standalone]

#93323

Den tisdag 30 juni 2015 kl. 11:08:01 UTC+2 skrev Christian Gollwitzer:
> 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).
> 
> 	Christian

Any new digit will be found in SQRT(base) comparissons. 
Averaged case will be in (SQRT(base)*(SQRT(base)+1))/2

[toc] | [prev] | [next] | [standalone]

#93324

Den tisdag 30 juni 2015 kl. 11:35:06 UTC+2 skrev jonas.t...@gmail.com:
> Den tisdag 30 juni 2015 kl. 11:08:01 UTC+2 skrev Christian Gollwitzer:
> > 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).
> > 
> > 	Christian
> 
> Any new digit will be found in SQRT(base) comparissons. 
> Averaged case will be in (SQRT(base)*(SQRT(base)+1))/2

Well that averaging was balloney. How do i write that the digit will be found in.
Average values from 1 to SQRT(base)?

[toc] | [prev] | [next] | [standalone]

#93328

Den tisdag 30 juni 2015 kl. 11:43:55 UTC+2 skrev jonas.t...@gmail.com:
> Den tisdag 30 juni 2015 kl. 11:35:06 UTC+2 skrev jonas.t...@gmail.com:
> > Den tisdag 30 juni 2015 kl. 11:08:01 UTC+2 skrev Christian Gollwitzer:
> > > 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).
> > > 
> > > 	Christian
> > 
> > Any new digit will be found in SQRT(base) comparissons. 
> > Averaged case will be in (SQRT(base)*(SQRT(base)+1))/2
> 
> Well that averaging was balloney. How do i write that the digit will be found in.
> Average values from 1 to SQRT(base)?

Regarding the time it seem to double the digits quadruple the time. And that is still linear or?

[toc] | [prev] | [next] | [standalone]

#93329

Den tisdag 30 juni 2015 kl. 15:22:44 UTC+2 skrev jonas.t...@gmail.com:
> Den tisdag 30 juni 2015 kl. 11:43:55 UTC+2 skrev jonas.t...@gmail.com:
> > Den tisdag 30 juni 2015 kl. 11:35:06 UTC+2 skrev jonas.t...@gmail.com:
> > > Den tisdag 30 juni 2015 kl. 11:08:01 UTC+2 skrev Christian Gollwitzer:
> > > > 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).
> > > > 
> > > > 	Christian
> > > 
> > > Any new digit will be found in SQRT(base) comparissons. 
> > > Averaged case will be in (SQRT(base)*(SQRT(base)+1))/2
> > 
> > Well that averaging was balloney. How do i write that the digit will be found in.
> > Average values from 1 to SQRT(base)?
> 
> Regarding the time it seem to double the digits quadruple the time. And that is still linear or?

2x seem linear to me?

[toc] | [prev] | [next] | [standalone]

#93331

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.

[toc] | [prev] | [next] | [standalone]

#93333

On Tue, Jun 30, 2015 at 9:40 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> 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.

Actually, I think you need up to b1 * b2 mappings, as you're
effectively building a state machine with b1 * b2 states. The mappings
can be pre-computed, however, so actually running the state machine
would then just be a linear algorithm.

[toc] | [prev] | [next] | [standalone]

#93335

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.

[toc] | [prev] | [next] | [standalone]

#93351

Am 30.06.15 um 17:40 schrieb Ian Kelly:
> On Tue, Jun 30, 2015 at 3:07 AM, Christian Gollwitzer <auriocus@gmx.de> wrote:
>> 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.
>

OK. Show it for bases 2 and 3. It will just be a table of 6 entries, no?

Actually, you showed a very special case, for conversion from base b^4 
to base b. I'm pretty convinced it is not possible for the general case.

	Christian

[toc] | [prev] | [next] | [standalone]

#93336

On Wed, Jul 1, 2015 at 1:45 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> On Tue, Jun 30, 2015 at 9:40 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
>> 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.
>
> Actually, I think you need up to b1 * b2 mappings, as you're
> effectively building a state machine with b1 * b2 states. The mappings
> can be pre-computed, however, so actually running the state machine
> would then just be a linear algorithm.

Arbitrary base conversion has to be stateful. You can take a shortcut
like this when the bases are related (eg binary, octal, hexadecimal),
but otherwise, you need the division. Consider what happens when you
convert the binary digit "1" to decimal, and then follow it with
varying numbers of zeros:

1, 2, 4, 8, 16, 32, 64,... 32768, 65536, 131072,... 1048576,... 1073741824,...

You can certainly do some useful analyses on the last digits (they'll
never be anything other than 2, 4, 8, 6, except for the special case
of 1 itself), but there's a lot of variation in the intermediate
digits.

When there's a simple ratio between the bases, it's fairly
straight-forward to convert a few digits at a time. Converting base
256 into base 64, for instance, can be done by taking three digits and
yielding four. But within that, you would still need a complete table
of all sixteen million possibilities, if you want to do the lookup
table. And that only works when there is that kind of relationship.

ChrisA

[toc] | [prev] | [next] | [standalone]

#93340

On Tue, Jun 30, 2015 at 10:10 AM, Chris Angelico <rosuav@gmail.com> wrote:
> When there's a simple ratio between the bases, it's fairly
> straight-forward to convert a few digits at a time. Converting base
> 256 into base 64, for instance, can be done by taking three digits and
> yielding four. But within that, you would still need a complete table
> of all sixteen million possibilities, if you want to do the lookup
> table. And that only works when there is that kind of relationship.

You're right. I was thinking that for base 5 to base 7, for instance,
one could read digits in groups of 7, but that doesn't work out; you
can't map any discrete number of base 5 digits to a corresponding
number of base 7 digits.

[toc] | [prev] | [next] | [standalone]

#93352

Am 30.06.15 um 18:34 schrieb Ian Kelly:
> On Tue, Jun 30, 2015 at 10:10 AM, Chris Angelico <rosuav@gmail.com> wrote:
>> When there's a simple ratio between the bases, it's fairly
>> straight-forward to convert a few digits at a time. Converting base
>> 256 into base 64, for instance, can be done by taking three digits and
>> yielding four. But within that, you would still need a complete table
>> of all sixteen million possibilities, if you want to do the lookup
>> table. And that only works when there is that kind of relationship.
>
> You're right. I was thinking that for base 5 to base 7, for instance,
> one could read digits in groups of 7, but that doesn't work out; you
> can't map any discrete number of base 5 digits to a corresponding
> number of base 7 digits.

Yes, because there is no n for which 5^n=7^n (except n=0). This gives 
more-or-less the proof that the algorithm must be O(N^2) - at least that 
is my feeling. Fun fact, though: you can convert pi to hexadeicmal base 
without computing the preceding digits:

https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula

	Christian

[toc] | [prev] | [next] | [standalone]

#93313

Den tisdag 30 juni 2015 kl. 01:11:51 UTC+2 skrev Ian:
> On Mon, Jun 29, 2015 at 4:56 PM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> > On Mon, Jun 29, 2015 at 4:39 PM,  <jonas.thornvall@gmail.com> wrote:
> >> http://jt.node365.se/baseconversion8.html
> >
> > Back of the envelope mental calculation, that appears to be quadratic,
> > not linear. Doubling the length of the input results in an approximate
> > quadrupling of the time taken to produce the output.
> >
> > That noted, this is off-topic for this list, which is for discussion
> > about Python. Please take this to somewhere else like
> > comp.lang.javascript instead.
> 
> By the way, I think you have a bug. I did my time testing by
> concatenating the default input number to itself several times. At
> 5184 decimal digits, which was the last case I tried, the 58th output
> digit was 1111111, after which point the remaining 672 output digits
> are all 12665464, which seemed rather improbable.

It isn't i used the power to check with wolfram, but there is a plus 1 bug as ben noticed.

But not in this slower version.
http://jt.node365.se/baseconversion5.html

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.python

csiph-web