Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #65415 > unrolled thread
| Started by | Ayushi Dalmia <ayushidalmia2604@gmail.com> |
|---|---|
| First post | 2014-02-04 03:28 -0800 |
| Last post | 2014-02-05 15:22 +0000 |
| Articles | 20 on this page of 137 — 29 participants |
Back to article view | Back to comp.lang.python
Finding size of Variable Ayushi Dalmia <ayushidalmia2604@gmail.com> - 2014-02-04 03:28 -0800
Re: Finding size of Variable Peter Otten <__peter__@web.de> - 2014-02-04 12:40 +0100
Re: Finding size of Variable Ayushi Dalmia <ayushidalmia2604@gmail.com> - 2014-02-04 04:43 -0800
Re: Finding size of Variable Asaf Las <roegltd@gmail.com> - 2014-02-04 04:53 -0800
Re: Finding size of Variable Ayushi Dalmia <ayushidalmia2604@gmail.com> - 2014-02-04 05:18 -0800
Re: Finding size of Variable Dave Angel <davea@davea.name> - 2014-02-04 08:09 -0500
Re: Finding size of Variable Ayushi Dalmia <ayushidalmia2604@gmail.com> - 2014-02-04 05:19 -0800
Re: Finding size of Variable Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2014-02-04 09:06 -0500
Re: Finding size of Variable Ayushi Dalmia <ayushidalmia2604@gmail.com> - 2014-02-04 21:00 -0800
Re:Finding size of Variable Dave Angel <davea@davea.name> - 2014-02-04 14:21 -0500
Re: Finding size of Variable Ayushi Dalmia <ayushidalmia2604@gmail.com> - 2014-02-04 21:15 -0800
Re: Finding size of Variable Peter Otten <__peter__@web.de> - 2014-02-05 09:27 +0100
Re: Finding size of Variable Tim Golden <mail@timgolden.me.uk> - 2014-02-04 19:28 +0000
Re: Finding size of Variable Tim Chase <python.list@tim.thechases.com> - 2014-02-04 13:29 -0600
Re: Finding size of Variable Ayushi Dalmia <ayushidalmia2604@gmail.com> - 2014-02-04 21:35 -0800
Re: Finding size of Variable Rustom Mody <rustompmody@gmail.com> - 2014-02-04 21:45 -0800
Re: Finding size of Variable Ayushi Dalmia <ayushidalmia2604@gmail.com> - 2014-02-04 22:00 -0800
Re: Finding size of Variable Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-02-05 11:00 +0000
Re: Finding size of Variable Chris Angelico <rosuav@gmail.com> - 2014-02-05 22:44 +1100
Re: Finding size of Variable wxjmfauth@gmail.com - 2014-02-06 02:15 -0800
Re: Finding size of Variable Ned Batchelder <ned@nedbatchelder.com> - 2014-02-06 06:10 -0500
Re: Finding size of Variable wxjmfauth@gmail.com - 2014-02-06 05:51 -0800
Re: Finding size of Variable wxjmfauth@gmail.com - 2014-02-06 06:15 -0800
Re: Finding size of Variable Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-02-08 02:48 +0000
Re: Finding size of Variable Ethan Furman <ethan@stoneleaf.us> - 2014-02-07 19:02 -0800
Re: Finding size of Variable Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-02-08 13:17 +0000
Re: Finding size of Variable David Hutto <dwightdhutto@gmail.com> - 2014-02-08 17:45 -0500
Re: Finding size of Variable Rustom Mody <rustompmody@gmail.com> - 2014-02-08 17:25 -0800
Re: Finding size of Variable David Hutto <dwightdhutto@gmail.com> - 2014-02-08 21:56 -0500
Re: Finding size of Variable Chris Angelico <rosuav@gmail.com> - 2014-02-09 13:59 +1100
Re: Finding size of Variable David Hutto <dwightdhutto@gmail.com> - 2014-02-08 22:07 -0500
Re: Finding size of Variable Ned Batchelder <ned@nedbatchelder.com> - 2014-02-08 22:09 -0500
Re: Finding size of Variable David Hutto <dwightdhutto@gmail.com> - 2014-02-08 22:09 -0500
Re: Finding size of Variable Ned Batchelder <ned@nedbatchelder.com> - 2014-02-08 22:16 -0500
Re: Finding size of Variable Rustom Mody <rustompmody@gmail.com> - 2014-02-08 19:30 -0800
Re: Finding size of Variable wxjmfauth@gmail.com - 2014-02-10 06:07 -0800
Re: Finding size of Variable Asaf Las <roegltd@gmail.com> - 2014-02-10 06:25 -0800
Re: Finding size of Variable Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-02-10 14:39 +0000
Re: Finding size of Variable Tim Chase <python.list@tim.thechases.com> - 2014-02-10 08:43 -0600
Re: Finding size of Variable wxjmfauth@gmail.com - 2014-02-11 10:53 -0800
Re: Finding size of Variable Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-02-11 19:04 +0000
Re: Finding size of Variable wxjmfauth@gmail.com - 2014-02-11 23:49 -0800
Re: Finding size of Variable Chris Angelico <rosuav@gmail.com> - 2014-02-12 19:06 +1100
Re: Finding size of Variable Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2014-02-12 10:57 +0200
Re: Finding size of Variable Chris Angelico <rosuav@gmail.com> - 2014-02-12 20:24 +1100
Re: Finding size of Variable Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2014-02-12 11:35 +0200
Working with the set of real numbers (was: Finding size of Variable) Ben Finney <ben+python@benfinney.id.au> - 2014-02-12 19:17 +1100
Re: Working with the set of real numbers (was: Finding size of Variable) wxjmfauth@gmail.com - 2014-02-12 00:35 -0800
Re: Working with the set of real numbers (was: Finding size of Variable) wxjmfauth@gmail.com - 2014-02-12 00:46 -0800
Re: Working with the set of real numbers Ben Finney <ben+python@benfinney.id.au> - 2014-02-12 19:52 +1100
Re: Working with the set of real numbers (was: Finding size of Variable) Grant Edwards <invalid@invalid.invalid> - 2014-02-12 15:24 +0000
Re: Working with the set of real numbers (was: Finding size of Variable) "Gisle Vanem" <gvanem@yahoo.no> - 2014-02-12 17:23 +0100
Re: Working with the set of real numbers (was: Finding size of Variable) Chris Angelico <rosuav@gmail.com> - 2014-02-12 19:47 +1100
Re: Working with the set of real numbers (was: Finding size of Variable) Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2014-02-12 11:23 +0200
Re: Working with the set of real numbers (was: Finding size of Variable) albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-03-04 02:45 +0000
Re: Working with the set of real numbers (was: Finding size of Variable) Chris Angelico <rosuav@gmail.com> - 2014-03-04 14:02 +1100
Re: Working with the set of real numbers (was: Finding size of Variable) Rustom Mody <rustompmody@gmail.com> - 2014-03-03 19:13 -0800
Re: Working with the set of real numbers (was: Finding size of Variable) Chris Angelico <rosuav@gmail.com> - 2014-03-04 14:46 +1100
Re: Working with the set of real numbers (was: Finding size of Variable) Rustom Mody <rustompmody@gmail.com> - 2014-03-03 21:19 -0800
Re: Working with the set of real numbers (was: Finding size of Variable) Steven D'Aprano <steve@pearwood.info> - 2014-03-04 05:53 +0000
Re: Working with the set of real numbers (was: Finding size of Variable) Chris Angelico <rosuav@gmail.com> - 2014-03-04 17:35 +1100
Re: Working with the set of real numbers Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-03-05 00:05 +1300
Re: Working with the set of real numbers Chris Angelico <rosuav@gmail.com> - 2014-03-04 23:43 +1100
Re: Working with the set of real numbers Marko Rauhamaa <marko@pacujo.net> - 2014-03-04 21:49 +0200
Re: Working with the set of real numbers Chris Angelico <rosuav@gmail.com> - 2014-03-05 06:58 +1100
Re: Working with the set of real numbers Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-03-04 20:55 +0000
Re: Working with the set of real numbers Marko Rauhamaa <marko@pacujo.net> - 2014-03-04 23:05 +0200
Re: Working with the set of real numbers Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-03-04 22:08 +0000
Re: Working with the set of real numbers Chris Angelico <rosuav@gmail.com> - 2014-03-05 08:18 +1100
Re: Working with the set of real numbers Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-03-04 22:02 +0000
Re: Working with the set of real numbers Chris Angelico <rosuav@gmail.com> - 2014-03-05 09:18 +1100
Re: Working with the set of real numbers Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-03-04 22:54 +0000
Re: Working with the set of real numbers Chris Angelico <rosuav@gmail.com> - 2014-03-05 10:01 +1100
Re: Working with the set of real numbers Dave Angel <davea@davea.name> - 2014-03-04 18:20 -0500
Re: Working with the set of real numbers (was: Finding size of Variable) Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-04 04:19 -0700
Re: Working with the set of real numbers (was: Finding size of Variable) albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-03-05 02:27 +0000
Re: Working with the set of real numbers (was: Finding size of Variable) Ian Kelly <ian.g.kelly@gmail.com> - 2014-03-04 04:23 -0700
Re: Working with the set of real numbers (was: Finding size of Variable) albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-03-05 02:15 +0000
Re: Working with the set of real numbers (was: Finding size of Variable) Steven D'Aprano <steve@pearwood.info> - 2014-03-05 03:41 +0000
Re: Working with the set of real numbers (was: Finding size of Variable) Rustom Mody <rustompmody@gmail.com> - 2014-03-04 20:15 -0800
Re: Working with the set of real numbers (was: Finding size of Variable) Roy Smith <roy@panix.com> - 2014-03-04 23:25 -0500
Re: Working with the set of real numbers Ben Finney <ben+python@benfinney.id.au> - 2014-03-05 15:37 +1100
Re: Working with the set of real numbers Rustom Mody <rustompmody@gmail.com> - 2014-03-04 20:57 -0800
Re: Working with the set of real numbers Roy Smith <roy@panix.com> - 2014-03-05 00:29 -0500
Re: Working with the set of real numbers Ben Finney <ben+python@benfinney.id.au> - 2014-02-12 19:56 +1100
Re: Working with the set of real numbers Chris Angelico <rosuav@gmail.com> - 2014-02-12 20:16 +1100
Re: Working with the set of real numbers Ben Finney <ben+python@benfinney.id.au> - 2014-02-12 21:07 +1100
Re: Working with the set of real numbers Rustom Mody <rustompmody@gmail.com> - 2014-02-12 06:11 -0800
Re: Working with the set of real numbers Ian Kelly <ian.g.kelly@gmail.com> - 2014-02-12 13:45 -0700
Re: Working with the set of real numbers Rustom Mody <rustompmody@gmail.com> - 2014-02-12 17:47 -0800
Re: Working with the set of real numbers Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-02-13 11:09 +1300
Re: Working with the set of real numbers Steven D'Aprano <steve@pearwood.info> - 2014-02-13 03:31 +0000
Re: Working with the set of real numbers Ben Finney <ben+python@benfinney.id.au> - 2014-02-13 14:45 +1100
Re: Working with the set of real numbers Chris Angelico <rosuav@gmail.com> - 2014-02-13 15:17 +1100
Re: Working with the set of real numbers Chris Angelico <rosuav@gmail.com> - 2014-02-12 21:20 +1100
Re: Working with the set of real numbers wxjmfauth@gmail.com - 2014-02-12 02:55 -0800
Re: Working with the set of real numbers Ned Batchelder <ned@nedbatchelder.com> - 2014-02-12 06:55 -0500
Re: Working with the set of real numbers Marko Rauhamaa <marko@pacujo.net> - 2014-02-12 14:48 +0200
Re: Working with the set of real numbers Chris Angelico <rosuav@gmail.com> - 2014-02-13 00:20 +1100
Re: Working with the set of real numbers Marko Rauhamaa <marko@pacujo.net> - 2014-02-12 16:13 +0200
Re: Working with the set of real numbers Chris Angelico <rosuav@gmail.com> - 2014-02-13 04:52 +1100
Re: Working with the set of real numbers Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-02-13 11:24 +1300
Re: Working with the set of real numbers Dave Angel <davea@davea.name> - 2014-02-12 17:56 -0500
Re: Working with the set of real numbers Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-02-14 18:26 +1300
Re: Working with the set of real numbers Ben Finney <ben+python@benfinney.id.au> - 2014-02-12 22:44 +1100
Re: Working with the set of real numbers Chris Angelico <rosuav@gmail.com> - 2014-02-12 22:58 +1100
Re: Working with the set of real numbers Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-02-13 11:32 +1300
Re: Working with the set of real numbers Grant Edwards <invalid@invalid.invalid> - 2014-02-12 23:23 +0000
Re: Finding size of Variable Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-02-12 14:04 +0000
Re: Finding size of Variable Rustom Mody <rustompmody@gmail.com> - 2014-02-12 06:14 -0800
Re: Finding size of Variable Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-02-12 14:25 +0000
Re: Finding size of Variable Rustom Mody <rustompmody@gmail.com> - 2014-02-12 06:32 -0800
Re: Working with the set of real numbers Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-13 12:48 +0000
Re: Working with the set of real numbers Marko Rauhamaa <marko@pacujo.net> - 2014-02-13 16:00 +0200
Re: Working with the set of real numbers Chris Angelico <rosuav@gmail.com> - 2014-02-14 06:25 +1100
Re: Working with the set of real numbers Marko Rauhamaa <marko@pacujo.net> - 2014-02-13 21:47 +0200
Re: Working with the set of real numbers Chris Angelico <rosuav@gmail.com> - 2014-02-14 07:08 +1100
Re: Working with the set of real numbers Devin Jeanpierre <jeanpierreda@gmail.com> - 2014-02-13 22:05 -0800
Re: Working with the set of real numbers Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-02-15 00:30 +1300
Re: Working with the set of real numbers Devin Jeanpierre <jeanpierreda@gmail.com> - 2014-02-14 16:26 -0800
Re: Working with the set of real numbers albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-03-05 02:38 +0000
Re: Working with the set of real numbers Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-02-14 19:37 +1300
Re: Working with the set of real numbers Chris Angelico <rosuav@gmail.com> - 2014-02-14 17:44 +1100
Re: Working with the set of real numbers Rustom Mody <rustompmody@gmail.com> - 2014-02-14 07:13 -0800
Re: Working with the set of real numbers Dave Angel <davea@davea.name> - 2014-02-14 07:30 -0500
Re: Working with the set of real numbers Grant Edwards <invalid@invalid.invalid> - 2014-02-14 15:09 +0000
Re: Working with the set of real numbers Rotwang <sg552@hotmail.co.uk> - 2014-02-13 21:29 +0000
Re: Working with the set of real numbers Marko Rauhamaa <marko@pacujo.net> - 2014-02-14 00:00 +0200
Re: Working with the set of real numbers Rotwang <sg552@hotmail.co.uk> - 2014-02-13 22:21 +0000
Re: Working with the set of real numbers Marko Rauhamaa <marko@pacujo.net> - 2014-02-14 01:16 +0200
Re: Working with the set of real numbers Ben Finney <ben+python@benfinney.id.au> - 2014-02-14 03:57 +1100
Re: Finding size of Variable Ned Batchelder <ned@nedbatchelder.com> - 2014-02-10 10:02 -0500
Re: Finding size of Variable Neil Cerutti <neilc@norwich.edu> - 2014-02-11 14:29 +0000
Re: Finding size of Variable Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2014-02-05 22:14 -0500
Re: Finding size of Variable Dave Angel <davea@davea.name> - 2014-02-05 08:43 -0500
Re: Finding size of Variable Ayushi Dalmia <ayushidalmia2604@gmail.com> - 2014-02-05 06:33 -0800
Re: Finding size of Variable Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-02-05 15:22 +0000
Page 4 of 7 — ← Prev page 1 2 3 [4] 5 6 7 Next page →
| From | Chris Angelico <rosuav@gmail.com> |
|---|---|
| Date | 2014-03-04 17:35 +1100 |
| Subject | Re: Working with the set of real numbers (was: Finding size of Variable) |
| Message-ID | <mailman.7696.1393914922.18130.python-list@python.org> |
| In reply to | #67647 |
On Tue, Mar 4, 2014 at 4:53 PM, Steven D'Aprano <steve@pearwood.info> wrote:
> On Tue, 04 Mar 2014 14:46:25 +1100, Chris Angelico wrote:
>
>> That's neat, didn't know that. Is there an efficient way to figure out,
>> for any integer N, what its sqrt's CF sequence is? And what about the
>> square roots of non-integers - can you represent √π that way? I suspect,
>> though I can't prove, that there will be numbers that can't be
>> represented even with an infinite series - or at least numbers whose
>> series can't be easily calculated.
>
> Every irrational number can be written as a
> continued fraction with an infinite number of terms, just as every
> irrational number can be written as a decimal number with an infinite
> number of digits.
It's easy enough to have that kind of expansion, I'm wondering if it's
possible to identify it directly. To render the decimal expansion of a
square root by the cut-and-try method, you effectively keep dividing
until you find that you're "close enough"; that means you (a) have to
keep the entire number around for each step, and (b) need to do a few
steps to find that the digits aren't changing. But if you can take a
CF (finite or infinite) and do an O(n) transformation on it to produce
that number's square root, then you have an effective means of
representing square roots. Suppose I make a generator function that
represents a fraction:
def one_third():
while True:
yield 3
def one_seventh():
while True:
yield 1; yield 4; yield 2; yield 8; yield 5; yield 7
I could then make a generator that returns the sum of those two:
def add_without_carry(x, y):
whiile True:
yield next(x)+next(y)
Okay, that's broken for nearly any case, but with a bit more sophistication:
def add(x, y):
prev=None
nines=0
while True:
xx,yy=next(x),next(y)
tot=xx+yy
if tot==9:
nines+=1
continue
if tot>9:
if prev is None: raise OverflowError("exceeds 1.0")
yield prev+1
tot-=10
for _ in range(nines): yield 0
nines=0
else:
if prev is not None: yield prev
prev=tot
def show(n):
return ''.join(str(_) for _ in itertools.islice(n,20))
>>> show(add(one_third(),one_seventh()))
'47619047619047619047'
>>> show(add(add(add(one_seventh(),one_seventh()),add(one_seventh(),one_seventh())),add(one_seventh(),one_seventh())))
'85714285714285714285'
In constant space, that will produce the sum of two infinite sequences
of digits. (And it's constant time, too, except when it gets a stream
of nines. Adding three thirds together will produce an infinite loop
as it waits to see if there'll be anything that triggers an infinite
cascade of carries.) Now, if there's a way to do that for square
rooting a number, then the CF notation has a distinct benefit over the
decimal expansion used here. As far as I know, there's no simple way,
in constant space and/or time, to progressively yield more digits of a
number's square root, working in decimal.
ChrisA
[toc] | [prev] | [next] | [standalone]
| From | Gregory Ewing <greg.ewing@canterbury.ac.nz> |
|---|---|
| Date | 2014-03-05 00:05 +1300 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <bnlqb5F3pcrU1@mid.individual.net> |
| In reply to | #67651 |
Chris Angelico wrote: > In constant space, that will produce the sum of two infinite sequences > of digits. It's not constant space, because the nines counter can grow infinitely large. -- Greg
[toc] | [prev] | [next] | [standalone]
| From | Chris Angelico <rosuav@gmail.com> |
|---|---|
| Date | 2014-03-04 23:43 +1100 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <mailman.7705.1393937036.18130.python-list@python.org> |
| In reply to | #67660 |
On Tue, Mar 4, 2014 at 10:05 PM, Gregory Ewing <greg.ewing@canterbury.ac.nz> wrote: > Chris Angelico wrote: >> >> In constant space, that will produce the sum of two infinite sequences >> of digits. > > > It's not constant space, because the nines counter > can grow infinitely large. Okay, okay, technically yes. But the counter can go a long way up before it takes up any additional space, so all that's really saying is that this has a major flaw with anything that produces a long stream of nines. It can't tell the difference between .99999999999999998 and .999999999999999999999999[11] where the 11 suddenly carries and it has to flip it all back. Anyway, that was like ten minutes' knocking-together work, you can't expect it to be perfect. I'm amazed it even worked. :) ChrisA
[toc] | [prev] | [next] | [standalone]
| From | Marko Rauhamaa <marko@pacujo.net> |
|---|---|
| Date | 2014-03-04 21:49 +0200 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <87iortoic0.fsf@elektro.pacujo.net> |
| In reply to | #67651 |
Chris Angelico <rosuav@gmail.com>: > As far as I know, there's no simple way, in constant space and/or > time, to progressively yield more digits of a number's square root, > working in decimal. I don't know why the constant space/time requirement is crucial. Anyway, producing more digits simple: <URL: http://nrich.maths.org/5955>. I believe producing the nth digit is O(n) in time and space. Still, there's more to arithmetics than that. For example, if you have two generated decimal expansions, you don't have an effective algorithm to generate the decimal expansion of their ratio. That's because there's no effective algorithm to decide if a < b. Marko
[toc] | [prev] | [next] | [standalone]
| From | Chris Angelico <rosuav@gmail.com> |
|---|---|
| Date | 2014-03-05 06:58 +1100 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <mailman.7736.1393963107.18130.python-list@python.org> |
| In reply to | #67711 |
On Wed, Mar 5, 2014 at 6:49 AM, Marko Rauhamaa <marko@pacujo.net> wrote: > Chris Angelico <rosuav@gmail.com>: > >> As far as I know, there's no simple way, in constant space and/or >> time, to progressively yield more digits of a number's square root, >> working in decimal. > > I don't know why the constant space/time requirement is crucial. Anyway, > producing more digits simple: <URL: http://nrich.maths.org/5955>. > > I believe producing the nth digit is O(n) in time and space. The reason for striving for constant space/time is because the obvious method (cut-and-try) is already O(n) for the nth digit, which means it's quadratic on the number of digits desired. That gets pretty nasty. So what I was asking was: By representing values as continued fractions rather than as decimal digits, are you able to perform a straight-forward transformation that produces the square root, in constant time (which means linear in the length)? And I guess the answer's no. CF representation doesn't have the advantage I was wondering about. ChrisA
[toc] | [prev] | [next] | [standalone]
| From | Oscar Benjamin <oscar.j.benjamin@gmail.com> |
|---|---|
| Date | 2014-03-04 20:55 +0000 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <mailman.7739.1393966562.18130.python-list@python.org> |
| In reply to | #67711 |
On 4 March 2014 19:58, Chris Angelico <rosuav@gmail.com> wrote:
> On Wed, Mar 5, 2014 at 6:49 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> Chris Angelico <rosuav@gmail.com>:
>>
>>> As far as I know, there's no simple way, in constant space and/or
>>> time, to progressively yield more digits of a number's square root,
>>> working in decimal.
>>
>> I don't know why the constant space/time requirement is crucial. Anyway,
>> producing more digits simple: <URL: http://nrich.maths.org/5955>.
>>
>> I believe producing the nth digit is O(n) in time and space.
>
> The reason for striving for constant space/time is because the obvious
> method (cut-and-try) is already O(n) for the nth digit, which means
> it's quadratic on the number of digits desired. That gets pretty
> nasty.
I don't quite follow your reasoning here. By "cut-and-try" do you mean
bisection? If so it gives the first N decimal digits in N*log2(10)
iterations. However each iteration requires a multiply and when the
number of digits N becomes large the multiplication is worse than
linear. So the result is something like N**2 log(N)log(log(N)),
To me the obvious method is Newton iteration which takes O(sqrt(N))
iterations to obtain N digits of precision. This brings the above
complexity below quadratic:
#!/usr/bin/env python
from decimal import Decimal as D, localcontext
def sqrt(y, prec=1000):
'''Solve x**2 = y'''
assert y > 0
eps = D(10) ** -(prec + 5)
x = D(y)
with localcontext() as ctx:
ctx.prec = prec + 10
while x ** 2 - y > x * eps:
x = (x + y/x) / 2
return x
print(sqrt(2))
Some modification would be required to handle a situation where it
ends in a run of nines or zeros if you really care about the exact
digits rather than having a bounded error.
Oscar
[toc] | [prev] | [next] | [standalone]
| From | Marko Rauhamaa <marko@pacujo.net> |
|---|---|
| Date | 2014-03-04 23:05 +0200 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <87y50pn08t.fsf@elektro.pacujo.net> |
| In reply to | #67718 |
Oscar Benjamin <oscar.j.benjamin@gmail.com>: > To me the obvious method is Newton iteration which takes O(sqrt(N)) > iterations to obtain N digits of precision. This brings the above > complexity below quadratic: > > #!/usr/bin/env python > > from decimal import Decimal as D, localcontext > > def sqrt(y, prec=1000): > '''Solve x**2 = y''' > assert y > 0 > eps = D(10) ** -(prec + 5) > x = D(y) > with localcontext() as ctx: > ctx.prec = prec + 10 > while x ** 2 - y > x * eps: > x = (x + y/x) / 2 > return x > > print(sqrt(2)) At a quick glance, I believe x ** 2 is O(N²) and so the total complexity should be O(N ** 2.5). Marko
[toc] | [prev] | [next] | [standalone]
| From | Oscar Benjamin <oscar.j.benjamin@gmail.com> |
|---|---|
| Date | 2014-03-04 22:08 +0000 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <mailman.7756.1393970947.18130.python-list@python.org> |
| In reply to | #67720 |
On 4 March 2014 21:05, Marko Rauhamaa <marko@pacujo.net> wrote: > Oscar Benjamin <oscar.j.benjamin@gmail.com>: > >> To me the obvious method is Newton iteration which takes O(sqrt(N)) >> iterations to obtain N digits of precision. This brings the above >> complexity below quadratic: >> >> #!/usr/bin/env python >> >> from decimal import Decimal as D, localcontext >> >> def sqrt(y, prec=1000): >> '''Solve x**2 = y''' >> assert y > 0 >> eps = D(10) ** -(prec + 5) >> x = D(y) >> with localcontext() as ctx: >> ctx.prec = prec + 10 >> while x ** 2 - y > x * eps: >> x = (x + y/x) / 2 >> return x >> >> print(sqrt(2)) > > At a quick glance, I believe x ** 2 is O(N²) and so the total complexity > should be O(N ** 2.5). x**2 is just a multiplication which can be done in better than O(N**2): http://en.wikipedia.org/wiki/Multiplication_algorithm#Fast_multiplication_algorithms_for_large_inputs Oscar
[toc] | [prev] | [next] | [standalone]
| From | Chris Angelico <rosuav@gmail.com> |
|---|---|
| Date | 2014-03-05 08:18 +1100 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <mailman.7742.1393967919.18130.python-list@python.org> |
| In reply to | #67711 |
On Wed, Mar 5, 2014 at 7:55 AM, Oscar Benjamin
<oscar.j.benjamin@gmail.com> wrote:
> I don't quite follow your reasoning here. By "cut-and-try" do you mean
> bisection? If so it gives the first N decimal digits in N*log2(10)
> iterations. However each iteration requires a multiply and when the
> number of digits N becomes large the multiplication is worse than
> linear. So the result is something like N**2 log(N)log(log(N)),
By "cut and try" I'm talking about the really REALLY simple algorithm
for calculating square roots. It's basically brute force.
epsilon = 0.0001
def sqrt(n):
guess1, guess2 = 1, n
while abs(guess1-guess2) > epsilon:
guess1 = n/guess2
guess2 = (guess1 + guess2)/2
return guess1
It's generally going to take roughly O(n*n) time to generate n digits,
give or take. That's the baseline against which anything else can be
compared. There are plenty of better ways to calculate them.
ChrisA
[toc] | [prev] | [next] | [standalone]
| From | Oscar Benjamin <oscar.j.benjamin@gmail.com> |
|---|---|
| Date | 2014-03-04 22:02 +0000 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <mailman.7754.1393970560.18130.python-list@python.org> |
| In reply to | #67711 |
On 4 March 2014 21:18, Chris Angelico <rosuav@gmail.com> wrote: > On Wed, Mar 5, 2014 at 7:55 AM, Oscar Benjamin > <oscar.j.benjamin@gmail.com> wrote: >> I don't quite follow your reasoning here. By "cut-and-try" do you mean >> bisection? If so it gives the first N decimal digits in N*log2(10) >> iterations. However each iteration requires a multiply and when the >> number of digits N becomes large the multiplication is worse than >> linear. So the result is something like N**2 log(N)log(log(N)), > > By "cut and try" I'm talking about the really REALLY simple algorithm > for calculating square roots. It's basically brute force. > > epsilon = 0.0001 > def sqrt(n): > guess1, guess2 = 1, n > while abs(guess1-guess2) > epsilon: > guess1 = n/guess2 > guess2 = (guess1 + guess2)/2 > return guess1 That's the exact same algorithm I showed! How on earth would you call that brute force? > It's generally going to take roughly O(n*n) time to generate n digits, > give or take. It does not take O(n*n) time. This is Newton iteration and for well-behaved problems such as this it generates more than n digits after n iterations. I modified my code to show the error (x**2 - y) at each iteration: $ python3.3 root.py 2 0.2 0.007 0.000006 5E-12 3E-24 8E-49 8E-98 8E-196 9E-392 1E-783 The number of correct digits doubles at each iteration so after n iterations you have 2**n digits (I misstated this as n**2 before). This means that it takes log(N) iterations to get N digits. See here for more: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method See also the section below that: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation > That's the baseline against which anything else can be > compared. There are plenty of better ways to calculate them. Such as? Oscar
[toc] | [prev] | [next] | [standalone]
| From | Chris Angelico <rosuav@gmail.com> |
|---|---|
| Date | 2014-03-05 09:18 +1100 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <mailman.7757.1393971516.18130.python-list@python.org> |
| In reply to | #67711 |
On Wed, Mar 5, 2014 at 9:02 AM, Oscar Benjamin <oscar.j.benjamin@gmail.com> wrote: > On 4 March 2014 21:18, Chris Angelico <rosuav@gmail.com> wrote: >> On Wed, Mar 5, 2014 at 7:55 AM, Oscar Benjamin >> <oscar.j.benjamin@gmail.com> wrote: >>> I don't quite follow your reasoning here. By "cut-and-try" do you mean >>> bisection? If so it gives the first N decimal digits in N*log2(10) >>> iterations. However each iteration requires a multiply and when the >>> number of digits N becomes large the multiplication is worse than >>> linear. So the result is something like N**2 log(N)log(log(N)), >> >> By "cut and try" I'm talking about the really REALLY simple algorithm >> for calculating square roots. It's basically brute force. >> >> epsilon = 0.0001 >> def sqrt(n): >> guess1, guess2 = 1, n >> while abs(guess1-guess2) > epsilon: >> guess1 = n/guess2 >> guess2 = (guess1 + guess2)/2 >> return guess1 > > That's the exact same algorithm I showed! How on earth would you call > that brute force? It uses a lot of division. There are various refinements that can be done that replace some of that division with multiplication, but I'd have to go do some research to figure it out. This is the purest form of attempted-division algorithm. If you're describing it on a blackboard, you would write it pretty much like this. At each iteration, you have to divide by a number that's n digits long, and then do some additional arithmetic. >> It's generally going to take roughly O(n*n) time to generate n digits, >> give or take. > > It does not take O(n*n) time. This is Newton iteration and for > well-behaved problems such as this it generates more than n digits > after n iterations. I modified my code to show the error (x**2 - y) at > each iteration: > > $ python3.3 root.py > 2 > 0.2 > 0.007 > 0.000006 > 5E-12 > 3E-24 > 8E-49 > 8E-98 > 8E-196 > 9E-392 > 1E-783 > > The number of correct digits doubles at each iteration so after n > iterations you have 2**n digits (I misstated this as n**2 before). > This means that it takes log(N) iterations to get N digits. It seems I'm partly mistaken, though not entirely. Let's compare two versions. In the first, you set the precision (I'm talking in terms of REXX's "NUMERIC DIGITS" statement - anything beyond this many digits will be rounded (and represented exponentially, if necessary); I'm not sure if decimal.Decimal precision works this way) such that you get 10 digits. Each iteration requires division by a 10-digit number, which is an operation that takes a certain amount of time; and it's going to take some number of iterations to get to the final answer. Second version, you set the precision so you get 20 digits. Now, it's going to take you approximately one more iteration to get to the final answer. (This bit I was mistaken on. I thought it would take something like 25% more or 50% more iterations.) But each iteration will take longer. The complexity of division depends on the algorithm - grade school long division would be O(n) with a fixed-length dividend, I think, but you could probably pull that down a bit. So that's why I said it'd be very roughly O(n*n) - because the division in each step is O(n), and I thought it'd take O(n) steps. Turns out it's O(n*log(n)), which is a lot better. >> That's the baseline against which anything else can be >> compared. There are plenty of better ways to calculate them. > > Such as? Improved versions of the above, and I was under the impression that there were some completely different techniques that converged a lot more quickly. But it may be that I was mistaken, as I'd been expecting this to converge in O(n) steps. Reducing the amount of division would speed things up significantly, although it probably won't change the algorithmic complexity. So, put it down to misremembering and thinking the simple algorithm was worse than it actually is :) ChrisA
[toc] | [prev] | [next] | [standalone]
| From | Oscar Benjamin <oscar.j.benjamin@gmail.com> |
|---|---|
| Date | 2014-03-04 22:54 +0000 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <mailman.7762.1393973669.18130.python-list@python.org> |
| In reply to | #67711 |
On 4 March 2014 22:18, Chris Angelico <rosuav@gmail.com> wrote: > On Wed, Mar 5, 2014 at 9:02 AM, Oscar Benjamin > <oscar.j.benjamin@gmail.com> wrote: >> On 4 March 2014 21:18, Chris Angelico <rosuav@gmail.com> wrote: >>> On Wed, Mar 5, 2014 at 7:55 AM, Oscar Benjamin >>> <oscar.j.benjamin@gmail.com> wrote: >>> >>> epsilon = 0.0001 >>> def sqrt(n): >>> guess1, guess2 = 1, n >>> while abs(guess1-guess2) > epsilon: >>> guess1 = n/guess2 >>> guess2 = (guess1 + guess2)/2 >>> return guess1 >> >> That's the exact same algorithm I showed! How on earth would you call >> that brute force? > > It uses a lot of division. There are various refinements that can be > done that replace some of that division with multiplication, but I'd > have to go do some research to figure it out. There's a description of such a method here: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots I don't know whether that would work out faster (when using decimal - for float it would probably be slower). > Let's compare two > versions. In the first, you set the precision (I'm talking in terms of > REXX's "NUMERIC DIGITS" statement I have no idea what that is. >- anything beyond this many digits > will be rounded (and represented exponentially, if necessary); I'm not > sure if decimal.Decimal precision works this way) such that you get 10 > digits. With the decimal module if you set the precision to 5 digits then it basically represents the number in "standard form" with 5 digits .e.g: 1.2345 x 10**21. > Each iteration requires division by a 10-digit number, which > is an operation that takes a certain amount of time; and it's going to > take some number of iterations to get to the final answer. > > Second version, you set the precision so you get 20 digits. If we're talking about 10-20 digits then the decimal module is overkill: just use float. The speed up from hardware arithmetic will massively out-weigh any other performance considerations. My version was intended to produce large numbers of digits which is when the big-O comes in: $ python3.3 -m timeit -s 'from root import sqrt' 'sqrt(2, 10)' 10000 loops, best of 3: 22.4 usec per loop $ python3.3 -m timeit -s 'from root import sqrt' 'sqrt(2, 100)' 10000 loops, best of 3: 59.1 usec per loop $ python3.3 -m timeit -s 'from root import sqrt' 'sqrt(2, 1000)' 1000 loops, best of 3: 1.15 msec per loop $ python3.3 -m timeit -s 'from root import sqrt' 'sqrt(2, 10000)' 10 loops, best of 3: 85.9 msec per loop $ python3.3 -m timeit -s 'from root import sqrt' 'sqrt(2, 100000)' 10 loops, best of 3: 1.59 sec per loop Oscar
[toc] | [prev] | [next] | [standalone]
| From | Chris Angelico <rosuav@gmail.com> |
|---|---|
| Date | 2014-03-05 10:01 +1100 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <mailman.7764.1393974098.18130.python-list@python.org> |
| In reply to | #67711 |
On Wed, Mar 5, 2014 at 9:54 AM, Oscar Benjamin <oscar.j.benjamin@gmail.com> wrote: >> Let's compare two >> versions. In the first, you set the precision (I'm talking in terms of >> REXX's "NUMERIC DIGITS" statement > > I have no idea what that is. > >>- anything beyond this many digits >> will be rounded (and represented exponentially, if necessary); I'm not >> sure if decimal.Decimal precision works this way) such that you get 10 >> digits. > > With the decimal module if you set the precision to 5 digits then it > basically represents the number in "standard form" with 5 digits .e.g: > 1.2345 x 10**21. That's how NUMERIC DIGITS works, so we're on the same page. I'm not familiar enough with decimal.Decimal and how precision is configured, but it seems to function the same way. >> Each iteration requires division by a 10-digit number, which >> is an operation that takes a certain amount of time; and it's going to >> take some number of iterations to get to the final answer. >> >> Second version, you set the precision so you get 20 digits. > > If we're talking about 10-20 digits then the decimal module is > overkill: just use float. The speed up from hardware arithmetic will > massively out-weigh any other performance considerations. Yeah, I'm just digging into the algorithm. The same concept applies when going from 100 to 200 digits, or 1000 to 2000, and in each case, the division will get way slower, but the number of iterations won't go up as fast as I thought it would. In theory, it should be possible to do the first few divisions at lower precision, and scale up as you have need. In practice, would the churning of precisions mean that you lose all the benefit? ChrisA
[toc] | [prev] | [next] | [standalone]
| From | Dave Angel <davea@davea.name> |
|---|---|
| Date | 2014-03-04 18:20 -0500 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <mailman.7767.1393974980.18130.python-list@python.org> |
| In reply to | #67711 |
Oscar Benjamin <oscar.j.benjamin@gmail.com> Wrote in message:
> On 4 March 2014 21:18, Chris Angelico <rosuav@gmail.com> wrote:
>
>
> It does not take O(n*n) time. This is Newton iteration and for
> well-behaved problems such as this it generates more than n digits
> after n iterations. I modified my code to show the error (x**2 - y) at
> each iteration:
>
> $ python3.3 root.py
> 2
> 0.2
> 0.007
> 0.000006
> 5E-12
> 3E-24
> 8E-49
> 8E-98
> 8E-196
> 9E-392
> 1E-783
>
> The number of correct digits doubles at each iteration so after n
> iterations you have 2**n digits (I misstated this as n**2 before).
> This means that it takes log(N) iterations to get N digits. See here
> for more:
> http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method
>
> See also the section below that:
> http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation
>
>> That's the baseline against which anything else can be
>> compared. There are plenty of better ways to calculate them.
>
> Such as?
>
One problem with complexity claims is that it's easy to miss some
contributing time eaters. I haven't done any measuring on modern
machines nor in python, but I'd assume that multiplies take
*much* longer for large integers, and that divides are much
worse. So counting iterations isn't the whole story.
On the assumption that division by 2 is very fast, and that a
general multiply isn't too bad, you could improve on Newton by
observing that the slope is 2.
err = n - guess * guess
guess += err/2
Some 37 years ago I microcoded a math package which included
square root. All the math was decimal, and there was no hardware
multiply or divide. The algorithm I came up with generated the
answer one digit at a time, with no subsequent rounding needed.
And it took just a little less time than two divides. For that
architecture, Newton's method would've been too
slow.
Incidentally, the algorithm did no divides, not even by 2. No
multiplies either. Just repeated subtraction, sorta like divide
was done.
If anyone is curious, I'll be glad to describe the algorithm;
I've never seen it published, before or since. I got my
inspiration from a method used in mechanical, non-motorized,
adding machines. My father had shown me that approach in the
50's.
--
DaveA
[toc] | [prev] | [next] | [standalone]
| From | Ian Kelly <ian.g.kelly@gmail.com> |
|---|---|
| Date | 2014-03-04 04:19 -0700 |
| Subject | Re: Working with the set of real numbers (was: Finding size of Variable) |
| Message-ID | <mailman.7702.1393932047.18130.python-list@python.org> |
| In reply to | #67647 |
On Mon, Mar 3, 2014 at 11:35 PM, Chris Angelico <rosuav@gmail.com> wrote:
> In constant space, that will produce the sum of two infinite sequences
> of digits. (And it's constant time, too, except when it gets a stream
> of nines. Adding three thirds together will produce an infinite loop
> as it waits to see if there'll be anything that triggers an infinite
> cascade of carries.) Now, if there's a way to do that for square
> rooting a number, then the CF notation has a distinct benefit over the
> decimal expansion used here. As far as I know, there's no simple way,
> in constant space and/or time, to progressively yield more digits of a
> number's square root, working in decimal.
The code for that looks like this:
def cf_sqrt(n):
"""Yield the terms of the square root of n as a continued fraction."""
m = 0
d = 1
a = a0 = floor_sqrt(n)
while True:
yield a
next_m = d * a - m
next_d = (n - next_m * next_m) // d
if next_d == 0:
break
next_a = (a0 + next_m) // next_d
m, d, a = next_m, next_d, next_a
def floor_sqrt(n):
"""Return the integer part of the square root of n."""
n = int(n)
if n == 0: return 0
lower = 2 ** int(math.log(n, 2) // 2)
upper = lower * 2
while upper - lower > 1:
mid = (upper + lower) // 2
if n < mid * mid:
upper = mid
else:
lower = mid
return lower
The floor_sqrt function is merely doing a simple binary search and
could probably be optimized, but then it's only called once during
initialization anyway. The meat of the loop, as you can see, is just
a constant amount of integer arithmetic. If it were desired to halt
once the continued fraction starts to repeat, that would just be a
matter of checking whether the triple (m, d, a) has been seen already.
Going back to your example of adding generated digits though, I don't
know how to add two continued fractions together without evaluating
them.
[toc] | [prev] | [next] | [standalone]
| From | albert@spenarnc.xs4all.nl (Albert van der Horst) |
|---|---|
| Date | 2014-03-05 02:27 +0000 |
| Subject | Re: Working with the set of real numbers (was: Finding size of Variable) |
| Message-ID | <53168ba7$0$25064$e4fe514c@dreader37.news.xs4all.nl> |
| In reply to | #67662 |
In article <mailman.7702.1393932047.18130.python-list@python.org>, Ian Kelly <ian.g.kelly@gmail.com> wrote: >On Mon, Mar 3, 2014 at 11:35 PM, Chris Angelico <rosuav@gmail.com> wrote: >> In constant space, that will produce the sum of two infinite sequences >> of digits. (And it's constant time, too, except when it gets a stream >> of nines. Adding three thirds together will produce an infinite loop >> as it waits to see if there'll be anything that triggers an infinite >> cascade of carries.) Now, if there's a way to do that for square >> rooting a number, then the CF notation has a distinct benefit over the >> decimal expansion used here. As far as I know, there's no simple way, >> in constant space and/or time, to progressively yield more digits of a >> number's square root, working in decimal. > >The code for that looks like this: > >def cf_sqrt(n): > """Yield the terms of the square root of n as a continued fraction.""" > m = 0 > d = 1 > a = a0 = floor_sqrt(n) > while True: > yield a > next_m = d * a - m > next_d = (n - next_m * next_m) // d > if next_d == 0: > break > next_a = (a0 + next_m) // next_d > m, d, a = next_m, next_d, next_a > > >def floor_sqrt(n): > """Return the integer part of the square root of n.""" > n = int(n) > if n == 0: return 0 > lower = 2 ** int(math.log(n, 2) // 2) > upper = lower * 2 > while upper - lower > 1: > mid = (upper + lower) // 2 > if n < mid * mid: > upper = mid > else: > lower = mid > return lower > > >The floor_sqrt function is merely doing a simple binary search and >could probably be optimized, but then it's only called once during >initialization anyway. The meat of the loop, as you can see, is just >a constant amount of integer arithmetic. If it were desired to halt >once the continued fraction starts to repeat, that would just be a >matter of checking whether the triple (m, d, a) has been seen already. > >Going back to your example of adding generated digits though, I don't >know how to add two continued fractions together without evaluating >them. That is highly non-trivial indeed. See the gosper.txt reference I gave in another post. Groetjes Albert -- Albert van der Horst, UTRECHT,THE NETHERLANDS Economic growth -- being exponential -- ultimately falters. albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
[toc] | [prev] | [next] | [standalone]
| From | Ian Kelly <ian.g.kelly@gmail.com> |
|---|---|
| Date | 2014-03-04 04:23 -0700 |
| Subject | Re: Working with the set of real numbers (was: Finding size of Variable) |
| Message-ID | <mailman.7703.1393932233.18130.python-list@python.org> |
| In reply to | #67647 |
On Tue, Mar 4, 2014 at 4:19 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> def cf_sqrt(n):
> """Yield the terms of the square root of n as a continued fraction."""
> m = 0
> d = 1
> a = a0 = floor_sqrt(n)
> while True:
> yield a
> next_m = d * a - m
> next_d = (n - next_m * next_m) // d
> if next_d == 0:
> break
> next_a = (a0 + next_m) // next_d
> m, d, a = next_m, next_d, next_a
Sorry, all that "next" business is totally unnecessary. More simply:
def cf_sqrt(n):
"""Yield the terms of the square root of n as a continued fraction."""
m = 0
d = 1
a = a0 = floor_sqrt(n)
while True:
yield a
m = d * a - m
d = (n - m * m) // d
if d == 0:
break
a = (a0 + m) // d
[toc] | [prev] | [next] | [standalone]
| From | albert@spenarnc.xs4all.nl (Albert van der Horst) |
|---|---|
| Date | 2014-03-05 02:15 +0000 |
| Subject | Re: Working with the set of real numbers (was: Finding size of Variable) |
| Message-ID | <531688b1$0$25064$e4fe514c@dreader37.news.xs4all.nl> |
| In reply to | #67631 |
In article <mailman.7687.1393902132.18130.python-list@python.org>, Chris Angelico <rosuav@gmail.com> wrote: >On Tue, Mar 4, 2014 at 1:45 PM, Albert van der Horst ><albert@spenarnc.xs4all.nl> wrote: >>>No, the Python built-in float type works with a subset of real numbers: >> >> To be more precise: a subset of the rational numbers, those with a denominator >> that is a power of two. > >And no more than N bits (53 in a 64-bit float) in the numerator, and >the denominator between the limits of the exponent. (Unless it's >subnormal. That adds another set of small numbers.) It's a pretty >tight set of restrictions, and yet good enough for so many purposes. > >But it's a far cry from "all real numbers". Even allowing for >continued fractions adds only some more; I don't think you can >represent surds that way. Adding cf's adds all computable numbers in infinite precision. However that is not even a drop in the ocean, as the computable numbers have measure zero. A cf object yielding its coefficients amounts to a program that generates an infinite amount of data (in infinite time), so it is not very surprising it can represent any computable number. Pretty humbling really. > >ChrisA Groetjes Albert -- Albert van der Horst, UTRECHT,THE NETHERLANDS Economic growth -- being exponential -- ultimately falters. albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
[toc] | [prev] | [next] | [standalone]
| From | Steven D'Aprano <steve@pearwood.info> |
|---|---|
| Date | 2014-03-05 03:41 +0000 |
| Subject | Re: Working with the set of real numbers (was: Finding size of Variable) |
| Message-ID | <53169cd9$0$2923$c3e8da3$76491128@news.astraweb.com> |
| In reply to | #67781 |
On Wed, 05 Mar 2014 02:15:14 +0000, Albert van der Horst wrote: > Adding cf's adds all computable numbers in infinite precision. However > that is not even a drop in the ocean, as the computable numbers have > measure zero. On the other hand, it's not really clear that the non-computable numbers are useful or necessary for anything. They exist as mathematical abstractions, but they'll never be the result of any calculation or measurement that anyone might do. -- Steven
[toc] | [prev] | [next] | [standalone]
| From | Rustom Mody <rustompmody@gmail.com> |
|---|---|
| Date | 2014-03-04 20:15 -0800 |
| Subject | Re: Working with the set of real numbers (was: Finding size of Variable) |
| Message-ID | <c39d5b44-6c7b-40d1-bbb5-791a36af6857@googlegroups.com> |
| In reply to | #67787 |
On Wednesday, March 5, 2014 9:11:13 AM UTC+5:30, Steven D'Aprano wrote: > On Wed, 05 Mar 2014 02:15:14 +0000, Albert van der Horst wrote: > > Adding cf's adds all computable numbers in infinite precision. However > > that is not even a drop in the ocean, as the computable numbers have > > measure zero. > On the other hand, it's not really clear that the non-computable numbers > are useful or necessary for anything. They exist as mathematical > abstractions, but they'll never be the result of any calculation or > measurement that anyone might do. There are even more extreme versions of this amounting to roughly this view: "Any infinity supposedly 'larger' than the natural numbers is a nonsensical notion." See eg http://en.wikipedia.org/wiki/Controversy_over_Cantor%27s_theory and Weyl/Polya bet (pg 10 of http://research.microsoft.com/en-us/um/people/gurevich/Opera/123.pdf ) I cannot find the exact quote so from memory Weyl says something to this effect: Cantor's diagonalization PROOF is not in question. Its CONCLUSION very much is. The classical/platonic mathematician (subject to wooly thinking) concludes that the real numbers are a superset of the integers The constructvist mathematician (who supposedly thinks clearly) only concludes the obvious, viz that real numbers cannot be enumerated To go from 'cannot be enumerated' to 'is a proper superset of' requires the assumption of 'completed infinities' and that is not math but theology
[toc] | [prev] | [next] | [standalone]
Page 4 of 7 — ← Prev page 1 2 3 [4] 5 6 7 Next page →
Back to top | Article view | comp.lang.python
csiph-web