The Monte Carlo method, as mentioned, applies some great concepts but it is, clearly, not the fastest, not by a long shot, not by any reasonable measure. Also, it all depends on what kind of accuracy you are looking for. The fastest π I know of is the one with the digits hard coded. Looking at Pi and Pi[PDF], there are a lot of formulae.

Here is a method that converges quickly — about 14 digits per iteration. PiFast, the current fastest application, uses this formula with the FFT. I'll just write the formula, since the code is straightforward. This formula was almost found by Ramanujan and discovered by Chudnovsky. It is actually how he calculated several billion digits of the number — so it isn't a method to disregard. The formula will overflow quickly and, since we are dividing factorials, it would be advantageous then to delay such calculations to remove terms.

where,

Below is the Brent–Salamin algorithm. Wikipedia mentions that when **a** and **b** are "close enough" then **(a + b)² / 4t** will be an approximation of π. I'm not sure what "close enough" means, but from my tests, one iteration got 2 digits, two got 7, and three had 15, of course this is with doubles, so it might have an error based on its representation and the *true* calculation could be more accurate.

```
let pi_2 iters =
let rec loop_ a b t p i =
if i = 0 then a,b,t,p
else
let a_n = (a +. b) /. 2.0
and b_n = sqrt (a*.b)
and p_n = 2.0 *. p in
let t_n = t -. (p *. (a -. a_n) *. (a -. a_n)) in
loop_ a_n b_n t_n p_n (i - 1)
in
let a,b,t,p = loop_ (1.0) (1.0 /. (sqrt 2.0)) (1.0/.4.0) (1.0) iters in
(a +. b) *. (a +. b) /. (4.0 *. t)
```

Lastly, how about some pi golf (800 digits)? 160 characters!

```
int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5;for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);}
```

Be extremely careful using any of the other suggestions. It all depends on context.

I have spent a long time tracing a bugs in a system that presumed `a==b`

if `|a-b|<epsilon`

. The underlying problems were:

The implicit presumption in an algorithm that if `a==b`

and `b==c`

then `a==c`

.

Using the same epsilon for lines measured in inches and lines measured in mils (.001 inch). That is `a==b`

but `1000a!=1000b`

. (This is why AlmostEqual2sComplement asks for the epsilon or max ULPS).

The use of the same epsilon for both the cosine of angles and the length of lines!

Using such a compare function to sort items in a collection. (In this case using the builtin C++ operator == for doubles produced correct results.)

Like I said: it all depends on context and the expected size of `a`

and `b`

.

BTW, `std::numeric_limits<double>::epsilon()`

is the "machine epsilon". It is the difference between 1.0 and the next value representable by a double. I guess that it could be used in the compare function but only if the expected values are less than 1. (This is in response to @cdv's answer...)

Also, if you basically have `int`

arithmetic in `doubles`

(here we use doubles to hold int values in certain cases) your arithmetic will be correct. For example 4.0/2.0 will be the same as 1.0+1.0. This is as long as you do not do things that result in fractions (4.0/3.0) or do not go outside of the size of an int.

## Best Solution

The UITableView is not really designed to handle 10s of thousands of records. If would take a long time for a user to find what they want.

It would be better to load a portion of the table, perhaps a few hundred rows, as the user enters data so that it appears they have all the records available to them (Perhaps providing a label which shows the number of records that they have got left in there filtered view.)

The SQLite db should be perfect for this job. Add an index to the words table and then select a limited number of rows from it to show the user some progress. Adding an index makes a big difference to the performance of the even this simple table.

For example, I created two tables in a sqlite db and populated them with around 80,000 words

Then I ran the following query and got the CPU Time taken for each query

The results vary but the indexed version was consistently faster that the unindexed one.

With fast access to parts of the dictionary through an indexed table, you can bind the UITableView to the database using

`NSFecthedResultsController`

. This class takes care of fecthing records as required, caches results to improve performance and allows predicates to be easily specified.An example of how to use the NSFetchedResultsController is included in the iPhone Developers Cookbook. See main.m