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);}
Modern browsers have Array#includes
, which does exactly that and is widely supported by everyone except IE:
console.log(['joe', 'jane', 'mary'].includes('jane')); //true
You can also use Array#indexOf
, which is less direct, but doesn't require polyfills for outdated browsers.
console.log(['joe', 'jane', 'mary'].indexOf('jane') >= 0); //true
Many frameworks also offer similar methods:
- jQuery:
$.inArray(value, array, [fromIndex])
- Underscore.js:
_.contains(array, value)
(also aliased as _.include
and _.includes
)
- Dojo Toolkit:
dojo.indexOf(array, value, [fromIndex, findLast])
- Prototype:
array.indexOf(value)
- MooTools:
array.indexOf(value)
- MochiKit:
findValue(array, value)
- MS Ajax:
array.indexOf(value)
- Ext:
Ext.Array.contains(array, value)
- Lodash:
_.includes(array, value, [from])
(is _.contains
prior 4.0.0)
- Ramda:
R.includes(value, array)
Notice that some frameworks implement this as a function, while others add the function to the array prototype.
Best Answer
Without recursion:
For very large arrays, it might be faster to use the fork-join pattern, where you split your array and calculate gcds in parallel. Here is some pseudocode: