|
|
|
| Authored by: Anonymous on Thursday, January 31 2013 @ 04:53 PM EST |
Nothing here.
[ Reply to This | Parent | # ]
|
| |
| Authored by: bugstomper on Thursday, January 31 2013 @ 05:59 PM EST |
| For some reason I read the title as referring to the trillionth digit of pi and
I got all excited and wrote up this comment about an article I found and then
noticed that you actually said something about trillionth digit of a prime
number. (Which, by the way, I have no idea what you mean, e.g. finding the first
trillion digits of a trillion digit prime number or finding the first prime
number with a trillion digits or something else like that). Anyway since I wrote
it up I have to post it :)
Here is a O(n) time O(log n) space algorithm for
finding nth digit of pi
Finding the N-th
digit of Pi
Here is a very interesting formula for pi,
discovered by David Bailey, Peter Borwein, and Simon Plouffe in
1995:
Pi = SUMk=0 to infinity 16-k
[ 4/(8k+1) -
2/(8k+4) - 1/(8k+5) - 1/(8k+6) ]
The reason this pi formula is so
interesting is because it can be used to calculate the N-th digit of Pi (in base
16) without having to calculate all of the previous digits!
Moreover, one
can even do the calculation in a time that is essentially linear in N, with
memory requirements only logarithmic in N. This is far better than previous
algorithms for finding the N-th digit of Pi, which required keeping track of all
the previous digits!
[ Reply to This | Parent | # ]
|
| |
| Authored by: Wol on Friday, February 01 2013 @ 11:33 AM EST |
You missed the first line of his specification.
"There are functions that are easily specified, but not easily
computed."
Your example falls very neatly into this category - we know how it can be done -
indeed it's obvious how to do it, but we do not have the means to do it.
In other words, pretty much all knapsack-hard algorithms, of which there are A
LOT. Breaking RSA falls into this category, too - it's easy to specify *how* to
break it, just a lot harder to actually *do* it.
Cheers,
Wol[ Reply to This | Parent | # ]
|
|
|
|
|
