Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #67845
| From | Dave Angel <davea@davea.name> |
|---|---|
| Subject | Re: Working with the set of real numbers |
| Date | 2014-03-05 08:32 -0500 |
| Organization | news.gmane.org |
| References | (13 earlier) <CAPTjJmocK7Wpi765JKiNxEtquabm4No9GWomHv-vX7auFkqZ=w@mail.gmail.com> <CAHVvXxTSFnzZbRH2=xRr+yxidmTrUyCYsFPABOQBp3U5_2_-tQ@mail.gmail.com> <lf5mr8$ttr$1@ger.gmane.org> <CAHVvXxQo2-B8t+xmG04Awr1Z9V0o+w9az5UtpSEY=AmaW9pe0A@mail.gmail.com> <lf76nv$3s9$1@ger.gmane.org> |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.7821.1394026110.18130.python-list@python.org> (permalink) |
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
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web