On 03/05/2012 09:55, Martin Brown wrote:
> On 03/05/2012 08:40, David Brown wrote:
>> On 02/05/2012 17:32, Uwe Hercksen wrote:
>>>
>>>
>>> David Brown schrieb:
>>>
>>>> <
http://en.wikipedia.org/wiki/Lazy_evaluation>
>>>>
>>>> The most relevant section, "working with infinite data structures", is
>>>> missing - but I hope you get the point anyway.
>>>
>>> Hello,
>>>
>>> even with infinite data structures, with finite time and finite RAM, it
>>> is not possible to compute all digits of pi.
>>>
>>> Bye
>>>
>>
>> Calculate pi using "infinite precision" numbers, and you get it to
>> infinite precision. Obviously you can't print out the whole answer - but
>> you can print out as much of the answer as you want, until the machine
>> runs out of memory or time.
>
> But that isn't how the trick was done. There is a cute expression for
> the Nth hexadecimal digit representation of pi detailed at:
>
I think you missed the earlier post in which I said that I /did/ do
this, as a project at university. There may be other ways to calculate
pi that are more efficient in base 16 - but that's a different matter
entirely.
>
http://crd-legacy.lbl.gov/~dhbailey/pi/pi-alg
>>
>> An "infinite precision number" is usually held as a list of digits,
>> along with a method for calculating more digits. You can then write
>> functions that can add, subtract, multiply and divide such numbers. It
>> is particularly convenient to use a functional programming language for
>> such tasks, as they are good at working with unlimited lists, and with
>> manipulating functions (such as the digit generator function).
>>
>> To calculate pi, the easiest way is to note that atan(1) = pi/4, and
>> atan(x) = x - x^3 / 3 + x^5 / 5 - x^7 / 7 + ... Once you have the
>> individual parts in place, the rest is easy. Of course, you end up with
>> lots of unlimited lists of unlimited lists, etc.
>
> No-one in their right mind would start from that crude series today -
> its convergence for x=1 is absolutely hopeless. See for example:
>
>
http://en.wikipedia.org/wiki/Pi#Infinite_series
As I said, it was a university project. The aim was not to calculate
pi, but to understand the usage of infinite lists, infinite precision
numbers, ways to manipulate them, and ways to prove that the code to do
so is correct. The rate of convergence is utterly irrelevant.
Just for fun, I figured out an alternative series that was faster to
converge (possibly (atan(1/2) + atan(1/3)), though I can't remember for
sure).
>
>> Mathematically speaking, what you have is precise representation of
>> /all/ the digits of pi. You can't display them all, as you have limited
>> ram and time - but it /is/ precise and contains /all/ the digits - just
>> as "0.33..." is a precise decimal representation of /all/ the digits of
>> 1/3 (the "..." gives the method of producing any digits you want).
>
> The algorithm that can supply the Nth digits of pi lazily *only* works
> for hexadecimal digits (or base 2^N for certain N).
>
> It doesn't work at all for the *decimal* representation of pi.
>
Nonsense. I did it, and I didn't find it particularly hard.
Perhaps you misunderstand what "lazy evaluation" actually is. The
algorithm you reference is a way to calculate a hexadecimal digit of pi
without having to calculate the previous digits - no such method is
known for calculating the decimal digits (though that does not mean one
does not exist). But that has nothing at all to do with lazy
evaluation, which simply means that the relevant numbers are calculated
when needed rather than in advance. It means you can work with an
unlimited list, and treat it as though it were a fully calculated
infinite list, without the computer actually having to calculate
anything until the last minute.