Surely all funsters carrying smartphones in their pockets immediately see the need for the "Find this sequence of digits in pi" app available at http://fathom.info/pi. This seems to be implemented in the obvious way: the app itself is 47.68 MB large, which is precisely what you would need to store 100,000,000 digits at two decimal digits in each byte. Loading and searching both take a while. At the other end of the spectrum, the app could be tiny and just include an algorithm to generate the digits itself. It would end up quite slow, certainly. But for some trade-off between data transmission time and cpu speed, that would be the right implementation. Are there any other interesting points on this trade-off curve? What might one want to do, other than pre-compute all or none of the digits? --Michael -- Forewarned is worth an octopus in the bush.
Query a faster, larger web server in parallel :) - Scott On Tue, Apr 8, 2014 at 7:40 PM, Michael Kleber <michael.kleber@gmail.com>wrote:
Surely all funsters carrying smartphones in their pockets immediately see the need for the "Find this sequence of digits in pi" app available at http://fathom.info/pi.
This seems to be implemented in the obvious way: the app itself is 47.68 MB large, which is precisely what you would need to store 100,000,000 digits at two decimal digits in each byte. Loading and searching both take a while.
At the other end of the spectrum, the app could be tiny and just include an algorithm to generate the digits itself. It would end up quite slow, certainly. But for some trade-off between data transmission time and cpu speed, that would be the right implementation.
Are there any other interesting points on this trade-off curve? What might one want to do, other than pre-compute all or none of the digits?
--Michael
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Obviously use even more memory and store the digits referenced by locations found - just for 0 to 9 or from 00 to 99 etc. On 9 Apr 2014, at 03:40, Michael Kleber wrote:
Surely all funsters carrying smartphones in their pockets immediately see the need for the "Find this sequence of digits in pi" app available at http://fathom.info/pi.
This seems to be implemented in the obvious way: the app itself is 47.68 MB large, which is precisely what you would need to store 100,000,000 digits at two decimal digits in each byte. Loading and searching both take a while.
At the other end of the spectrum, the app could be tiny and just include an algorithm to generate the digits itself. It would end up quite slow, certainly. But for some trade-off between data transmission time and cpu speed, that would be the right implementation.
Are there any other interesting points on this trade-off curve? What might one want to do, other than pre-compute all or none of the digits?
--Michael
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The meaning and purpose of life is to give life purpose and meaning. The instigation of violence indicates a lack of spirituality.
Oh sure, if you were trying to make retrieval more efficient, then certainly you do all sorts of indexing to improve on just searching the whole string. But I'm wondering about ways to pay more CPU in exchange for less pre-computed data, short of just calculating all the digits in the app. --Michael On Wed, Apr 9, 2014 at 8:26 AM, David Makin <makinmagic@tiscali.co.uk>wrote:
Obviously use even more memory and store the digits referenced by locations found - just for 0 to 9 or from 00 to 99 etc.
On 9 Apr 2014, at 03:40, Michael Kleber wrote:
Surely all funsters carrying smartphones in their pockets immediately see the need for the "Find this sequence of digits in pi" app available at http://fathom.info/pi.
This seems to be implemented in the obvious way: the app itself is 47.68 MB large, which is precisely what you would need to store 100,000,000 digits at two decimal digits in each byte. Loading and searching both take a while.
At the other end of the spectrum, the app could be tiny and just include an algorithm to generate the digits itself. It would end up quite slow, certainly. But for some trade-off between data transmission time and cpu speed, that would be the right implementation.
Are there any other interesting points on this trade-off curve? What might one want to do, other than pre-compute all or none of the digits?
--Michael
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The meaning and purpose of life is to give life purpose and meaning. The instigation of violence indicates a lack of spirituality.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
Try piologie. See this for a review by Dan Bernstein http://cr.yp.to/speed/mult/piologie.html Victor
On Apr 9, 2014, at 8:58, Michael Kleber <michael.kleber@gmail.com> wrote:
Oh sure, if you were trying to make retrieval more efficient, then certainly you do all sorts of indexing to improve on just searching the whole string. But I'm wondering about ways to pay more CPU in exchange for less pre-computed data, short of just calculating all the digits in the app.
--Michael
On Wed, Apr 9, 2014 at 8:26 AM, David Makin <makinmagic@tiscali.co.uk>wrote:
Obviously use even more memory and store the digits referenced by locations found - just for 0 to 9 or from 00 to 99 etc.
On 9 Apr 2014, at 03:40, Michael Kleber wrote:
Surely all funsters carrying smartphones in their pockets immediately see the need for the "Find this sequence of digits in pi" app available at http://fathom.info/pi.
This seems to be implemented in the obvious way: the app itself is 47.68 MB large, which is precisely what you would need to store 100,000,000 digits at two decimal digits in each byte. Loading and searching both take a while.
At the other end of the spectrum, the app could be tiny and just include an algorithm to generate the digits itself. It would end up quite slow, certainly. But for some trade-off between data transmission time and cpu speed, that would be the right implementation.
Are there any other interesting points on this trade-off curve? What might one want to do, other than pre-compute all or none of the digits?
--Michael
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The meaning and purpose of life is to give life purpose and meaning. The instigation of violence indicates a lack of spirituality.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The link Dan Bernstein mentions for piologie seems to be dead. But piologie seems to be a free educational iphone app which is here: pp.downloadatoz.com/publisher-sebastian-wedeniwski.html . There are also screenshots here: http://app.downloadatoz.com/iphone/piologie/screenshots.html . Apparently it can calculate many digits of pi, sqrt(2), and do integer factorization. But I don't have an iphone, so I can't try it out or say anything more. On Wed, Apr 9, 2014 at 9:17 AM, Victor S. Miller <victorsmiller@gmail.com>wrote:
Try piologie. See this for a review by Dan Bernstein http://cr.yp.to/speed/mult/piologie.html
Victor
On Apr 9, 2014, at 8:58, Michael Kleber <michael.kleber@gmail.com> wrote:
Oh sure, if you were trying to make retrieval more efficient, then certainly you do all sorts of indexing to improve on just searching the whole string. But I'm wondering about ways to pay more CPU in exchange for less pre-computed data, short of just calculating all the digits in the app.
--Michael
On Wed, Apr 9, 2014 at 8:26 AM, David Makin <makinmagic@tiscali.co.uk wrote:
Obviously use even more memory and store the digits referenced by locations found - just for 0 to 9 or from 00 to 99 etc.
On 9 Apr 2014, at 03:40, Michael Kleber wrote:
Surely all funsters carrying smartphones in their pockets immediately see the need for the "Find this sequence of digits in pi" app available at http://fathom.info/pi.
This seems to be implemented in the obvious way: the app itself is 47.68 MB large, which is precisely what you would need to store 100,000,000 digits at two decimal digits in each byte. Loading and searching both take a while.
At the other end of the spectrum, the app could be tiny and just include an algorithm to generate the digits itself. It would end up quite slow, certainly. But for some trade-off between data transmission time and cpu speed, that would be the right implementation.
Are there any other interesting points on this trade-off curve? What might one want to do, other than pre-compute all or none of the digits?
--Michael
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The meaning and purpose of life is to give life purpose and meaning. The instigation of violence indicates a lack of spirituality.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Somehow the answers have nothing to do with my question, so I must be asking wrong. I'm content to agree that the GPM-based program at https://gmplib.org/pi-with-gmp.html is a fine way to compute lots of digits of pi. It has zero pre-computation: there is no pi-specific data file that ships with the routine, everything is calculated by the program. The app I mentioned at the beginning of this thread has the opposite property: it does no computation, and instead ships with a pre-computed list of 10^8 digits, which it just searches. If you have a fast CPU and data storage is expensive, you would want the first option. If you have a slow CPU and cheap data storage, you would want the second. My question is, is there any CPU-speed-vs-storage-cost trade-off at which it makes sense to do something *other* than these two extremes? Or are these the only two plausible approaches for an app that answers "where does 23867242 first appear in pi?" --Michael On Wed, Apr 9, 2014 at 12:56 PM, Joerg Arndt <arndt@jjj.de> wrote:
https://gmplib.org/pi-with-gmp.html No reason to look elsewhere.
Best, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
I don't think there is any reasonable tradeoff. To do any computation with fast algorithms you might as well do all your computation. Plouffe's spigot algorithm might conceivably give a very small time-space tradeoff but it's highly unlikely to be practical for this application. Charles Greathouse Analyst/Programmer Case Western Reserve University On Wed, Apr 9, 2014 at 2:26 PM, Michael Kleber <michael.kleber@gmail.com>wrote:
Somehow the answers have nothing to do with my question, so I must be asking wrong.
I'm content to agree that the GPM-based program at https://gmplib.org/pi-with-gmp.html is a fine way to compute lots of digits of pi. It has zero pre-computation: there is no pi-specific data file that ships with the routine, everything is calculated by the program.
The app I mentioned at the beginning of this thread has the opposite property: it does no computation, and instead ships with a pre-computed list of 10^8 digits, which it just searches.
If you have a fast CPU and data storage is expensive, you would want the first option. If you have a slow CPU and cheap data storage, you would want the second.
My question is, is there any CPU-speed-vs-storage-cost trade-off at which it makes sense to do something *other* than these two extremes? Or are these the only two plausible approaches for an app that answers "where does 23867242 first appear in pi?"
--Michael
On Wed, Apr 9, 2014 at 12:56 PM, Joerg Arndt <arndt@jjj.de> wrote:
https://gmplib.org/pi-with-gmp.html No reason to look elsewhere.
Best, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I don't know enough about the various methods for calculating the digits of pi, however I would assume that at least one of them only requires a constant finite amount of data to continue the process from digit n to digit n+1 and for such a method it should be possible to pre-store set positions a certain number of digits apart - the faster the next digit algorithm then the further apart each pre-stored position. On 9 Apr 2014, at 19:26, Michael Kleber wrote:
Somehow the answers have nothing to do with my question, so I must be asking wrong.
I'm content to agree that the GPM-based program at https://gmplib.org/pi-with-gmp.html is a fine way to compute lots of digits of pi. It has zero pre-computation: there is no pi-specific data file that ships with the routine, everything is calculated by the program.
The app I mentioned at the beginning of this thread has the opposite property: it does no computation, and instead ships with a pre-computed list of 10^8 digits, which it just searches.
If you have a fast CPU and data storage is expensive, you would want the first option. If you have a slow CPU and cheap data storage, you would want the second.
My question is, is there any CPU-speed-vs-storage-cost trade-off at which it makes sense to do something *other* than these two extremes? Or are these the only two plausible approaches for an app that answers "where does 23867242 first appear in pi?"
--Michael
On Wed, Apr 9, 2014 at 12:56 PM, Joerg Arndt <arndt@jjj.de> wrote:
https://gmplib.org/pi-with-gmp.html No reason to look elsewhere.
Best, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The meaning and purpose of life is to give life purpose and meaning. The instigation of violence indicates a lack of spirituality.
participants (7)
-
Charles Greathouse -
David Makin -
James Buddenhagen -
Joerg Arndt -
Michael Kleber -
Scott Huddleston -
Victor S. Miller