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 159 — 30 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 Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-03-05 11:59 +0000
Re: Working with the set of real numbers Dave Angel <davea@davea.name> - 2014-03-05 07:57 -0500
Re: Working with the set of real numbers Dave Angel <davea@davea.name> - 2014-03-05 08:32 -0500
Re: Working with the set of real numbers Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-03-06 12:27 +0000
Re: Working with the set of real numbers Chris Angelico <rosuav@gmail.com> - 2014-03-07 00:16 +1100
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 (was: Finding size of Variable) Steven D'Aprano <steve@pearwood.info> - 2014-03-05 07:52 +0000
Re: Working with the set of real numbers (was: Finding size of Variable) Steven D'Aprano <steve@pearwood.info> - 2014-03-05 08:38 +0000
Re: Working with the set of real numbers (was: Finding size of Variable) wxjmfauth@gmail.com - 2014-03-05 01:00 -0800
Re: Working with the set of real numbers Ned Batchelder <ned@nedbatchelder.com> - 2014-03-05 06:23 -0500
Re: Working with the set of real numbers (was: Finding size of Variable) Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-03-05 12:21 +0000
Re: Working with the set of real numbers (was: Finding size of Variable) Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-05 17:43 +0000
Re: Working with the set of real numbers (was: Finding size of Variable) Chris Angelico <rosuav@gmail.com> - 2014-03-06 05:01 +1100
Re: Working with the set of real numbers (was: Finding size of Variable) Chris Kaynor <ckaynor@zindagigames.com> - 2014-03-05 10:03 -0800
Re: Working with the set of real numbers (was: Finding size of Variable) Grant Edwards <invalid@invalid.invalid> - 2014-03-05 19:13 +0000
Re: Working with the set of real numbers (was: Finding size of Variable) Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-03-05 21:22 +0000
Re: Working with the set of real numbers (was: Finding size of Variable) Roy Smith <roy@panix.com> - 2014-03-05 21:31 -0500
Re: Working with the set of real numbers (was: Finding size of Variable) Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-06 03:06 +0000
Re: Working with the set of real numbers (was: Finding size of Variable) Chris Angelico <rosuav@gmail.com> - 2014-03-06 14:14 +1100
Re: Working with the set of real numbers (was: Finding size of Variable) Roy Smith <roy@panix.com> - 2014-03-05 23:05 -0500
Re: Working with the set of real numbers (was: Finding size of Variable) Grant Edwards <invalid@invalid.invalid> - 2014-03-06 03:34 +0000
Re: Working with the set of real numbers Mark Lawrence <breamoreboy@yahoo.co.uk> - 2014-03-05 12:50 +0000
Re: Working with the set of real numbers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-03-05 17:49 +0000
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 8 — ← Prev page 1 2 3 [4] 5 6 7 8 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 | Oscar Benjamin <oscar.j.benjamin@gmail.com> |
|---|---|
| Date | 2014-03-05 11:59 +0000 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <mailman.7810.1394020816.18130.python-list@python.org> |
| In reply to | #67711 |
On 4 March 2014 23:20, Dave Angel <davea@davea.name> wrote:
>
> 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.
Agreed but there's a big difference between log(N) iterations and N iterations!
> 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
I gues you mean like this:
def sqrt(n):
err = guess = 1
while err > 1e-10:
err = n - guess * guess
guess += err/2
return guess
This requires log2(10)*N iterations to get N digits. So the penalty
for using division would have to be extreme in order for this to
better. Using Decimal to get many digits we can write that as:
def sqrt2(n, prec=1000):
'''Solve x**2 = y'''
eps = D(10) ** -(prec + 5)
err = guess = D(1)
with localcontext() as ctx:
ctx.prec = prec + 10
while abs(err) > eps:
err = n - guess*guess
guess += err/2
return guess
This method works out much slower than Newton with division at 10000
digits: 40s (based on a single trial) vs 80ms (timeit result).
> 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.
If you're working with a fixed small precision then it might be.
> 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.
I'm curious.
Oscar
[toc] | [prev] | [next] | [standalone]
| From | Dave Angel <davea@davea.name> |
|---|---|
| Date | 2014-03-05 07:57 -0500 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <mailman.7820.1394024033.18130.python-list@python.org> |
| In reply to | #67711 |
Oscar Benjamin <oscar.j.benjamin@gmail.com> Wrote in message:
> On 4 March 2014 23:20, Dave Angel <davea@davea.name> wrote:
>>
>> 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.
>
> Agreed but there's a big difference between log(N) iterations and N iterations!
>
>> 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
>
> I gues you mean like this:
>
> def sqrt(n):
> err = guess = 1
> while err > 1e-10:
> err = n - guess * guess
> guess += err/2
> return guess
>
> This requires log2(10)*N iterations to get N digits.
No idea how you came up with that, but I see an error in my
stated algorithm, which does surely penalize it. The slope isn't
2, but 2x. So the line should have been
guess += err/(2*guess)
Now if you stop the loop after 3 iterations (or use some other
approach to get a low-precision estimate, then you can calculate
scale = 1/(2*estimate)
and then for remaining iterations,
guess += err *scale
> So the penalty
> for using division would have to be extreme in order for this to
> better. Using Decimal to get many digits we can write that as:
>
> def sqrt2(n, prec=1000):
> '''Solve x**2 = y'''
> eps = D(10) ** -(prec + 5)
> err = guess = D(1)
> with localcontext() as ctx:
> ctx.prec = prec + 10
> while abs(err) > eps:
> err = n - guess*guess
> guess += err/2
> return guess
>
> This method works out much slower than Newton with division at 10000
> digits: 40s (based on a single trial) vs 80ms (timeit result).
Well considering you did not special-case the divide by 2, I'm not
surprised it's slower.
>
>> 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.
>
> If you're working with a fixed small precision then it might be.
>
>> 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.
>
> I'm curious.
>
A later message, I guess. I can't write that much on the tablet.
--
DaveA
[toc] | [prev] | [next] | [standalone]
| From | Dave Angel <davea@davea.name> |
|---|---|
| Date | 2014-03-05 08:32 -0500 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <mailman.7821.1394026110.18130.python-list@python.org> |
| In reply to | #67711 |
Dave Angel <davea@davea.name> Wrote in message: > Oscar Benjamin <oscar.j.benjamin@gmail.com> Wrote in message: >> On 4 March 2014 23:20, Dave Angel <davea@davea.name> wrote: >>> >>> 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. >> >> I'm curious. >> > > A later message, I guess. I can't write that much on the tablet. > > Given a microcodable architecture with no hardware support for multiply or divide, clearly multiply will be several times as fast as divide (at least). There was a BCD ALU, so add and subtract of decimal values was quite reasonable. All floating point logic, however, is just microcode. Divide is implemented via repeated subtraction of the divisor from the dividend. The count of how many subtracts is done is the quotient. Naturally, this is combined with digit shifts, so you find one quotient digit at a time. For a 13 digit result, the maximum subtracts are 13*10. Multiply is much faster, as you know ahead of time for each column how many adds you're supposed to do. So you can have precalculated multiples of the divisor on hand, and you can subtract instead of add when appropriate. Square root is implemented as a kind of variable division, where the "divisor" is changing constantly. Everyone knows that the sum of the first n odd numbers is n squared. So if you started with a square, you could repeatedly subtract odd numbers from it till you reached zero, and the square root will be roughly half the last odd number subtracted. So to make this work across multiple columns it turns out you can accumulate these odd numbers, doing the appropriate shifts after each column, and if you take the last number shifted, you can just add 1 and divide by 2. In many architectures, that would be as far as you can go, but in the particular one I was using, generating those pesky odd numbers was more expensive than you'd expect. So it turned out to be quicker to just do twice as many subtracts. Instead of subtracting 1,3, 5, etc., till the value went negative, we subtract 0 and 1, 1 and 2, 2 and 3, etc. You have twice as many subtracts, but no divide by 2 at the end. And for each column, you need not go beyond 8 + 9, since if it were more than that, we would have picked it up in the previous column. So you do not have to propagate the carry across the trial divisor. Supposing the correct result will be 7.1234567, you will at one stage of operations, be subtracting 71230 71231 71231 71232 71232 71233 71233 71234 The next subtract will make the result go negative, so you either do it, detect negative and undo it, or you do some compare operation. I am here glossing over all the details of normalizing the dividend so the exponent is even, and calculating the final exponent, which at first approximation is half the original one. -- DaveA
[toc] | [prev] | [next] | [standalone]
| From | Oscar Benjamin <oscar.j.benjamin@gmail.com> |
|---|---|
| Date | 2014-03-06 12:27 +0000 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <mailman.7864.1394108860.18130.python-list@python.org> |
| In reply to | #67711 |
On 5 March 2014 12:57, Dave Angel <davea@davea.name> wrote:
> Oscar Benjamin <oscar.j.benjamin@gmail.com> Wrote in message:
>> On 4 March 2014 23:20, Dave Angel <davea@davea.name> wrote:
>>>
>>> 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
>>
>> I gues you mean like this:
>>
>> def sqrt(n):
>> err = guess = 1
>> while err > 1e-10:
>> err = n - guess * guess
>> guess += err/2
>> return guess
>>
>> This requires log2(10)*N iterations to get N digits.
>
> No idea how you came up with that, but I see an error in my
> stated algorithm, which does surely penalize it. The slope isn't
> 2, but 2x. So the line should have been
> guess += err/(2*guess)
Ah, now I understand. This is the same algorithm that Chris posted
which in turn is the same as the one that I had previously posted: all
three are just using Newton's method.
Newton's method uses the slope argument to find a root of f(x) i.e. an
x0 such that f(x0) = 0. We start with a guess x[n]. We then find the
value of the function f(x[n]) and slope fp(x[n]) and extrapolating to
the point where f(x) hits the x-axis we find an improved estimate with
x[n+1] = x[n] - f(x[n]) / fp(x[n])
In our case f(x) = x**2 - y and so fp(x) = 2*x which gives
x[n+1] = x[n] - (x[n]**2 - y) / (2*x[n])
and after rearranging we can express this as
x[n+1] = (x[n] + y/x[n]) / 2.
So my loop
while x ** 2 - y > x * eps:
x = (x + y/x) / 2
and Chris' loop:
while abs(guess1-guess2) > epsilon:
guess1 = n/guess2
guess2 = (guess1 + guess2)/2
and now your loop
while err > 1e-10:
err = n - guess * guess
guess += err/(2 * guess)
are all performing the same basic algorithm. The only significant
difference is that mine tests for a relative error condition where as
the other two test for absolute error. This means that it will still
converge to an answer with the correct precision even when the root is
large e.g. sqrt(1e100). The other two are susceptible to infinite
loops in this case.
> Now if you stop the loop after 3 iterations (or use some other
> approach to get a low-precision estimate, then you can calculate
> scale = 1/(2*estimate)
>
> and then for remaining iterations,
> guess += err *scale
Fair enough. That's a reasonable suggestion for improvement. This is
often known as the "modified Newton's method". For lack of a better
reference see here:
http://math.stackexchange.com/questions/645088/modified-newtons-method
Using an approximate slope to avoid division can be a significant
optimisation. This is especially true when using the multidimensional
generalisation of Newton's method since in this case the division is
replaced with solving a system of linear equations (vastly more
expensive). However as noted in that stackexchange answer the use of
an approximate slope prevents quadratic convergence so in the
asymptotic case where we want large numbers of digits it can be much
slower.
Actually it's worse than that since we are guaranteed to converge to
an incorrect answer. The update step x = (x + y/x) / 2 will converge
when x^2 = y but we replace it with x = (x + y/x0)/2 where x0 is near
to the true root. This will converge when x == (x + y/x0)/2 i.e. when
x = y/x0 which is not the correct answer (and can be computed without
a loop in any case). It's possible to fix that by alternating between
steps where we improve our estimate of the slope and steps where we
use that estimate for refinement but I don't think that the advantage
of not using division counts against the loss of quadratic convergence
once we get to more than 10s of digits.
You can compare them yourself with this code:
def sqrt1(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 abs(x ** 2 - y) > x * eps:
x = (x + y/x) / 2
return x
def sqrt2(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
for n in range(7):
x = (x + y/x) / 2
x0r = 1 / x
while abs(x ** 2 - y) > x * eps:
err = x**2 - y
err2 = x - x0r * y
x = (x + x0r * y) / 2
return x
sqrt2(2) goes into an infinite loop at an error level of ~1e-100 (the
exact point where this happens depends on how many warmup iterations
it uses).
[snip]
>>
>> This method works out much slower than Newton with division at 10000
>> digits: 40s (based on a single trial) vs 80ms (timeit result).
>
> Well considering you did not special-case the divide by 2, I'm not
> surprised it's slower.
Multiplying by D('0.5') instead of dividing by 2 makes no measurable
difference to the timings. I don't know whether that's because it's
already special-cased by Decimal or just that the performance costs
don't match up in the same way for the multiprecision algorithms (when
the divisor is a single digit number).
Oscar
[toc] | [prev] | [next] | [standalone]
| From | Chris Angelico <rosuav@gmail.com> |
|---|---|
| Date | 2014-03-07 00:16 +1100 |
| Subject | Re: Working with the set of real numbers |
| Message-ID | <mailman.7866.1394111795.18130.python-list@python.org> |
| In reply to | #67711 |
On Thu, Mar 6, 2014 at 11:27 PM, Oscar Benjamin
<oscar.j.benjamin@gmail.com> wrote:
> So my loop
>
> while x ** 2 - y > x * eps:
> x = (x + y/x) / 2
>
> and Chris' loop:
>
> while abs(guess1-guess2) > epsilon:
> guess1 = n/guess2
> guess2 = (guess1 + guess2)/2
>
> and now your loop
>
> while err > 1e-10:
> err = n - guess * guess
> guess += err/(2 * guess)
>
> are all performing the same basic algorithm. The only significant
> difference is that mine tests for a relative error condition where as
> the other two test for absolute error. This means that it will still
> converge to an answer with the correct precision even when the root is
> large e.g. sqrt(1e100). The other two are susceptible to infinite
> loops in this case.
This is one place where I find the REXX 'numeric fuzz' setting to be a
useful trick. The definition is that, whenever two numbers are
compared for equality, the 'numeric digits' setting is effectively
reduced by the fuzz for that comparison. So let's say we're
calculating to a precision of 100 digits ('numeric digits 100'). You
could then code the loop as "do until guess1=guess2", with a numeric
fuzz of, say, 2. That'll give you 98 digits of accuracy, *regardless
of scale*. It's like setting epsilon to "whatever would be 1e-98 if we
were working with numbers between 0 and 1", more or less. A sliding
epsilon.
ChrisA
[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]
Page 4 of 8 — ← Prev page 1 2 3 [4] 5 6 7 8 Next page →
Back to top | Article view | comp.lang.python
csiph-web