Fast algorithm to calculate Pi in parallel -


i starting learn cuda , think calculating long digits of pi nice, introductory project.

i have implemented simple monte carlo method parallelize-able. have each thread randomly generate points on unit square, figure out how many lie within unit circle, , tally results using reduction operation.

but not fastest algorithm calculating constant. before, when did exercise on single threaded cpu, used machin-like formulae calculation far faster convergence. interested, involves expressing pi sum of arctangents , using taylor series evaluate expression.

an example of such formula:

enter image description here

unfortunately, found parallelizing technique thousands of gpu threads not easy. problem majority of operations doing high precision math opposed doing floating point operations on long vectors of data.

so i'm wondering, what efficient way calculate arbitrarily long digits of pi on gpu?

you should use bailey–borwein–plouffe formula

why? first of all, need algorithm can broken down. so, first thing came mind having representation of pi infinite sum. then, each processor computes 1 term, , sum them in end.

then, preferable each processor manipulates small-precision values, opposed high precision ones. example, if want 1 billion decimals, , use of expressions used here, chudnovsky algorithm, each of processor need manipulate billion long number. that's not appropriate method gpu.

so, in all, bbp formula allow compute digits of pi separately (the algorithm cool), , "low precision" processors! read "bbp digit-extraction algorithm π"

advantages of bbp algorithm computing π algorithm computes π without requiring custom data types having thousands or millions of digits. method calculates nth digit without calculating first n − 1 digits, , can use small, efficient data types. algorithm fastest way compute nth digit (or few digits in neighborhood of nth), π-computing algorithms using large data types remain faster when goal compute digits 1 n.


Comments

Post a Comment

Popular posts from this blog

java - Play! framework 2.0: How to display multiple image? -

i need display gallery of photos. here template: @(photos: list[photo]) @title = { <bold>gallery</bold> } @main(title,"photo"){ <ul class="thumbnails"> @for(photo <- photos) { <li class="span3"> <a href="#" class="thumbnail"> <img src="@photo.path" alt=""> </a> </li> } </ul> } and here controller method: public static result getphotos() { return ok(views.html.photo.gallery.render(photo.get())); } and here photo bean : @entity public class photo extends model { @id public long id; @required public string label; public string path; public photo(string path, string label) { this.path = path; this.label = label; } private static finder<long, photo> find = new finder<long, photo>( long.class, photo.class); public static list<phot...
Read more

gmail - Is there any documentation for read-only access to the Google Contacts API? -

i want read-only access user's google contacts. there stackoverflow member wanted this, , received following answer : yes, there is, use https://www.googleapis.com/auth/contacts.readonly scope , "view contacts". this exchange reference read-only access google contacts can find using google. simply using access token obtained attempt read usual google contacts api (i.e. https://www.google.com/m8/feeds ) fails insufficient permissions. similarly, using google contacts api on new target fails 404 errors (for example https://www.googleapis.com/auth/contacts.readonly/default/full ). is there documentation anywhere on how use api, or permissible way access google contacts api full read-write access?
Read more

php - Controller/JToolBar not working in Joomla 2.5 -

relevant code: jtoolbarhelper::custom('savecategories', 'save', '', 'save', false, false); ... <input type="hidden" name="controller" value="easyblogcontroller"> according can dig docs , own previous questions, should call savecategories() function in easyblogcontroller . i've tried setting value easyblog , easyblog.php (file name) current easyblogcontroller (class name). clicking on save button refreshes page. not redirect, echo or var_dump test code put in savecategories() function. var_dump ing jrequest::getvar('controller') , 'task' return correct values. creating controller object , using $controller->execute('task'); works. the values going depend on location of controller trying call, , have couple options here. typically there controller in base folder of component (likely components/com_easyblog) in file called controller.php , class name inside ...
Read more