ما هي اسرع وسيلة للحصول على قيمة π؟
https://stackoverflow.com/questions/19
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
وأنا أبحث عن أسرع طريقة للحصول على قيمة π، باعتباره تحديا شخصيا. وبشكل أكثر تحديدا، أنا باستخدام الطرق التي لا تنطوي على استخدام الثوابت #define مثل M_PI، أو من الصعب الترميز الرقم في.
وهذا البرنامج باختبار أدناه الطرق المختلفة أعرف. إصدار التجميع مضمنة هو، من الناحية النظرية، أسرع الخيار، على الرغم من الواضح أنه لا المحمولة. لقد شملت كخط أساس لمقارنة ضد إصدارات أخرى. في بلدي التجارب، مع الإضافية بنيت، وإصدار 4 * atan(1) هو الأسرع في دول مجلس التعاون الخليجي 4.2، لأنها لصناعة السيارات في طيات atan(1) إلى ثابت. مع -fno-builtin المحدد، وإصدار atan2(0, -1) هو الأسرع.
وهنا برنامج الاختبار الرئيسي (pitimes.c):
#include <math.h>
#include <stdio.h>
#include <time.h>
#define ITERS 10000000
#define TESTWITH(x) { \
diff = 0.0; \
time1 = clock(); \
for (i = 0; i < ITERS; ++i) \
diff += (x) - M_PI; \
time2 = clock(); \
printf("%s\t=> %e, time => %f\n", #x, diff, diffclock(time2, time1)); \
}
static inline double
diffclock(clock_t time1, clock_t time0)
{
return (double) (time1 - time0) / CLOCKS_PER_SEC;
}
int
main()
{
int i;
clock_t time1, time2;
double diff;
/* Warmup. The atan2 case catches GCC's atan folding (which would
* optimise the ``4 * atan(1) - M_PI'' to a no-op), if -fno-builtin
* is not used. */
TESTWITH(4 * atan(1))
TESTWITH(4 * atan2(1, 1))
#if defined(__GNUC__) && (defined(__i386__) || defined(__amd64__))
extern double fldpi();
TESTWITH(fldpi())
#endif
/* Actual tests start here. */
TESTWITH(atan2(0, -1))
TESTWITH(acos(-1))
TESTWITH(2 * asin(1))
TESTWITH(4 * atan2(1, 1))
TESTWITH(4 * atan(1))
return 0;
}
والاشياء التجميع مضمنة (fldpi.c) من شأنها أن تعمل فقط لأنظمة x86 و x64:
double
fldpi()
{
double pi;
asm("fldpi" : "=t" (pi));
return pi;
}
والسيناريو الذي يبني بناء كافة تكوينات أنا على اختبار (build.sh):
#!/bin/sh
gcc -O3 -Wall -c -m32 -o fldpi-32.o fldpi.c
gcc -O3 -Wall -c -m64 -o fldpi-64.o fldpi.c
gcc -O3 -Wall -ffast-math -m32 -o pitimes1-32 pitimes.c fldpi-32.o
gcc -O3 -Wall -m32 -o pitimes2-32 pitimes.c fldpi-32.o -lm
gcc -O3 -Wall -fno-builtin -m32 -o pitimes3-32 pitimes.c fldpi-32.o -lm
gcc -O3 -Wall -ffast-math -m64 -o pitimes1-64 pitimes.c fldpi-64.o -lm
gcc -O3 -Wall -m64 -o pitimes2-64 pitimes.c fldpi-64.o -lm
gcc -O3 -Wall -fno-builtin -m64 -o pitimes3-64 pitimes.c fldpi-64.o -lm
وبصرف النظر عن التجارب بين مختلف الأعلام المترجم (لقد مقابل 32 بت على 64 بت أيضا لأن تحسينات مختلفة)، لقد حاول أيضا تبديل ترتيب التجارب حولها. ولكن لا يزال، وإصدار atan2(0, -1) لا يزال يخرج على رأس كل الوقت.
المحلول
طريقة مونت كارلو ، كما ذكر، ينطبق بعض المفاهيم كبيرة لكنها، بشكل واضح، لا أسرع، وليس عن طريق تسديدة طويلة، وليس بأي مقياس معقول. أيضا، كل هذا يتوقف على نوع من الدقة كنت تبحث عنه. أسرع π أعرف من هو واحد مع الأرقام الثابت ترميز. وعند النظر إلى بي و <لأ href = "HTTP: // الوظائف. wolfram.com/PDF/Pi.pdf "يختلط =" noreferrer "عنوان =" الصيغ بي "> بي [PDF] ، وهناك الكثير من الصيغ.
وهنا هو الطريقة التي يتقاطع بسرعة - حوالي 14 رقما في التكرار. PiFast و أسرع التطبيق الحالي، يستخدم هذه الصيغة مع الاتحاد الفرنسي للتنس. أنا مجرد كتابة الصيغة، لأن رمز واضح ومباشر. تم العثور على هذه الصيغة تقريبا رامانوجان واكتشف من قبل Chudnovsky . هو في الواقع كيف انه يحسب عدة مليارات من أرقام من رقم - حتى لا يكون وسيلة لتجاهل. والصيغة تجاوز بسرعة و، لأننا تقسيم عاملي، سيكون من المفيد بعد ذلك إلى تأخير مثل هذه الحسابات لإزالة الشروط.
حيث
وفيما يلي برنت السلامين خوارزمية . ويكيبيديا يذكر أنه عندما <قوية> إلى و <قوية> ب هي "قريبة بما فيه الكفاية"، ثم على (أ + ب) ² / 4T سوف يكون تقريب π. لست متأكدا ما "إغلاق كافية" وسيلة، ولكن من بلدي التجارب، حصلت التكرار واحد 2 أرقام، وهما حصل 7، وثلاثة كان 15، وبطبيعة الحال هذا هو الحال مع زوجي، لذلك قد يكون خطأ على أساس التمثيل و و<م> صحيح حساب يمكن أن يكون أكثر دقة.
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)
وأخيرا، ماذا عن بعض بي الغولف (800 أرقام)؟ 160 حرفا!
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);}
نصائح أخرى
وأنا أحب هذا البرنامج، لأنه يقترب π من خلال النظر في مجال اختصاصه.
وIOCCC 1988: westley.c
<اقتباس فقرة>#define _ -F<00||--F-OO--;
int F=00,OO=00;main(){F_OO();printf("%1.3f\n",4.*-F/OO/OO);}F_OO()
{
_-_-_-_
_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_
_-_-_-_
}
وفيما يلي وصفا عاما للتقنية لحساب بي أن تعلمت في المدرسة الثانوية.
وأشارك هذا فقط لأنني أعتقد أنها بسيطة بما فيه الكفاية أن أي شخص يمكن أن نتذكر أنه، إلى أجل غير مسمى، بالإضافة إلى أنه يعلمك مفهوم الأساليب "مونتي كارلو" - والتي هي الأساليب الإحصائية للتوصل إلى الإجابات التي لا فورا يبدو أن المتأتي من خلال العمليات العشوائية.
ورسم مربع، وإدراج رباعي (ربع نصف دائرة) داخل هذا المربع (رباعي مع دائرة نصف قطرها يساوي جانب الساحة، بحيث يملأ قدر من مربع ممكن)
والآن رمي النبال في الساحة، وسجل حيث الأراضي - وهذا هو، واختيار نقطة عشوائية في أي مكان داخل الساحة. بطبيعة الحال، فإنه سقطت داخل الساحة، ولكن هل هو داخل دائرة نصف؟ تسجيل هذه الحقيقة.
وكرر هذه العملية عدة مرات - وسوف تجد أن هناك نسبة من عدد من النقاط داخل نصف دائرة مقابل العدد الإجمالي القيت، استدعاء هذه النسبة س
.ومنذ مساحة المربع هي الأوقات ص ص، يمكنك استنتاج أن مساحة دائرة نصف هي الأوقات خ ص ص مرات (وهذا يعني، مرة س ص المربعة). س ومن هنا 4 مرات سوف اعطيكم بي.
وهذه ليست طريقة سريعة للاستخدام. ولكن هذا مثال جيد لطريقة مونت كارلو. وإذا نظرت حولك، قد تجد أن العديد من المشاكل على خلاف ذلك خارج المهارات الحسابية الخاصة بك يمكن حلها عن طريق هذه الأساليب.
في مصالح اكتمال، نسخة قالب C ++، والتي، لبناء الأمثل، وحساب تقريبي من PI في وقت الترجمة، وسوف مضمنة إلى قيمة واحدة.
#include <iostream>
template<int I>
struct sign
{
enum {value = (I % 2) == 0 ? 1 : -1};
};
template<int I, int J>
struct pi_calc
{
inline static double value ()
{
return (pi_calc<I-1, J>::value () + pi_calc<I-1, J+1>::value ()) / 2.0;
}
};
template<int J>
struct pi_calc<0, J>
{
inline static double value ()
{
return (sign<J>::value * 4.0) / (2.0 * J + 1.0) + pi_calc<0, J-1>::value ();
}
};
template<>
struct pi_calc<0, 0>
{
inline static double value ()
{
return 4.0;
}
};
template<int I>
struct pi
{
inline static double value ()
{
return pi_calc<I, I>::value ();
}
};
int main ()
{
std::cout.precision (12);
const double pi_value = pi<10>::value ();
std::cout << "pi ~ " << pi_value << std::endl;
return 0;
}
ملحوظة لI> 10، إلى أقصى حد يبني يمكن أن تكون بطيئة، وبالمثل ليدير غير الأمثل. لمدة 12 التكرار وأعتقد أن هناك حوالي 80K المكالمات إلى قيمة () (في حالة عدم وجود memoisation).
وهناك في الواقع كتاب كامل مخصص (من بين أمور أخرى) إلى <م> بسرعة طرق لاحتساب \ بي: 'بي وAGM "، جوناثان وبيتر بورواين (<لأ href =" HTTPS : //rads.stackoverflow.com/amzn/click/com/047131515X "يختلط =" noreferrer "عنوان =" متاح في الأمازون "> متاح في الأمازون )
.ودرست الجمعية العامة العادية و الخوارزميات ذات الصلة لا بأس به: انها مثيرة للاهتمام للغاية (على الرغم أحيانا غير تافهة)
لاحظ أن تنفيذ معظم الخوارزميات الحديثة لحساب \ بي، وسوف تحتاج إلى مكتبة multiprecision حسابي ( GMP تماما اختيار جيد، على الرغم من انها كانت فترة من الوقت منذ آخر مرة استخدامه).
والساعة التعقيد من أفضل الخوارزميات في O (M (ن) سجل (ن))، حيث M (ن) هو التعقيد الوقت المناسب لتكاثر عددين ن بت (M (ن) = O (ن تسجيل (ن) السجل (سجل (ن))) باستخدام خوارزميات الاتحاد الفرنسي للتنس، التي هي بحاجة عادة عند حساب أرقام من \ بي، ويتم تنفيذ هذه الخوارزمية في GMP).
ملاحظة أنه على الرغم من الرياضيات وراء خوارزميات قد لا تكون تافهة، خوارزميات نفسها هي عادة بضعة أسطر من شبه الرمز، وتنفيذها هو عادة واضحة جدا (إذا اخترت عدم إكبس multiprecision الحساب الخاص: - )).
والأجوبة التالية على على وجه التحديد كيفية القيام بذلك في اسرع طريقة ممكنة - مع أقل جهد الحوسبة . حتى لو كنت لا تحب الجواب، يجب أن نعترف أنه في الواقع أسرع طريقة للحصول على قيمة PI.
و <قوية> أسرع طريقة للحصول على قيمة بي هي:
1) اختار لغة البرمجة المفضلة لديك 2) تحميل مكتبة الرياضيات لها 3) ونجد أن بي بالفعل تعرف هناك - جاهزة للاستخدام
في حالة لم يكن لديك مكتبة الرياضيات في متناول اليد ..
ويعني اسرع طريقة (حل عالمي أكثر) الثانية هي:
وبالبحث بي على شبكة الإنترنت، على سبيل المثال هنا:
http://www.eveandersson.com/pi/digits/1000000 (1 مليون أرقام .. ما بك النقطة العائمة الدقة؟)
وأو هنا:
http://3.141592653589793238462643383279502884197169399375105820974944592.com/
وأو هنا:
http://en.wikipedia.org/wiki/Pi
وانها سريعة جدا للعثور على الأرقام تحتاج لأي الحساب الدقة التي ترغب في استخدامها، وتحديد ثابت، يمكنك التأكد من أنك لا تضيعوا وقتكم الثمين وحدة المعالجة المركزية.
وليس هذا فقط هو الإجابة روح الدعابة جزئيا، لكن في الواقع، إذا كان أي شخص أن يذهب إلى الأمام وحساب قيمة بي في تطبيق حقيقي .. هذا سيكون مضيعة كبيرة جدا من الوقت وحدة المعالجة المركزية، أليس كذلك؟ على الأقل أنا لا أرى تطبيق حقيقي لمحاولة إعادة حساب هذه.
عزيزي المشرف: يرجى ملاحظة أن OP سأل: "أسرع طريقة للحصول على قيمة PI"
صيغة BBP يسمح لك لحساب الرقم الألف - في قاعدة 2 (أو 16) - دون الحاجة إلى عناء حتى مع ن 1 الأرقام السابقة أولا:)
وبدلا من تحديد بي كما ثابت، وأنا دائما استخدام acos(-1).
وجاء للتو عبر هذا واحد ينبغي أن يكون هنا للتأكد من اكتمالها:
وانها ملك لطيفة بدلا من أن دقة يمكن تحسين جعل البرنامج أكبر.
هنا الصورة بعض التبصر في اللغة نفسها
إذا هذه المقالة هو صحيح، ثم في الخوارزمية التي خلقت Bellard يمكن أن يكون واحدا من أسرع المتاحة. وقد خلق بي إلى 2.7 تريليون الأرقام باستخدام PC DESKTOP!
... وكان قد نشر عمله هنا
والعمل الجيد Bellard، أنت رائدا!
وهذا هو أسلوب "الكلاسيكية"، من السهل جدا لتنفيذ. هذا التنفيذ، في بيثون (اللغة يست سريعة جدا) يفعل:
from math import pi
from time import time
precision = 10**6 # higher value -> higher precision
# lower value -> higher speed
t = time()
calc = 0
for k in xrange(0, precision):
calc += ((-1)**k) / (2*k+1.)
calc *= 4. # this is just a little optimization
t = time()-t
print "Calculated: %.40f" % calc
print "Costant pi: %.40f" % pi
print "Difference: %.40f" % abs(calc-pi)
print "Time elapsed: %s" % repr(t)
ويمكنك العثور على مزيد من المعلومات هنا .
وعلى أي حال أسرع طريقة للحصول على دقة القيمة ك-كثيرا-كما عند عدم وبي في بيثون هو:
from gmpy import pi
print pi(3000) # the rule is the same as
# the precision on the previous code
وهنا هو قطعة من مصدر للأسلوب بي gmpy، وأنا لا أعتقد رمز كما هو مفيد بقدر التعليق في هذه الحالة:
static char doc_pi[]="\
pi(n): returns pi with n bits of precision in an mpf object\n\
";
/* This function was originally from netlib, package bmp, by
* Richard P. Brent. Paulo Cesar Pereira de Andrade converted
* it to C and used it in his LISP interpreter.
*
* Original comments:
*
* sets mp pi = 3.14159... to the available precision.
* uses the gauss-legendre algorithm.
* this method requires time o(ln(t)m(t)), so it is slower
* than mppi if m(t) = o(t**2), but would be faster for
* large t if a faster multiplication algorithm were used
* (see comments in mpmul).
* for a description of the method, see - multiple-precision
* zero-finding and the complexity of elementary function
* evaluation (by r. p. brent), in analytic computational
* complexity (edited by j. f. traub), academic press, 1976, 151-176.
* rounding options not implemented, no guard digits used.
*/
static PyObject *
Pygmpy_pi(PyObject *self, PyObject *args)
{
PympfObject *pi;
int precision;
mpf_t r_i2, r_i3, r_i4;
mpf_t ix;
ONE_ARG("pi", "i", &precision);
if(!(pi = Pympf_new(precision))) {
return NULL;
}
mpf_set_si(pi->f, 1);
mpf_init(ix);
mpf_set_ui(ix, 1);
mpf_init2(r_i2, precision);
mpf_init2(r_i3, precision);
mpf_set_d(r_i3, 0.25);
mpf_init2(r_i4, precision);
mpf_set_d(r_i4, 0.5);
mpf_sqrt(r_i4, r_i4);
for (;;) {
mpf_set(r_i2, pi->f);
mpf_add(pi->f, pi->f, r_i4);
mpf_div_ui(pi->f, pi->f, 2);
mpf_mul(r_i4, r_i2, r_i4);
mpf_sub(r_i2, pi->f, r_i2);
mpf_mul(r_i2, r_i2, r_i2);
mpf_mul(r_i2, r_i2, ix);
mpf_sub(r_i3, r_i3, r_i2);
mpf_sqrt(r_i4, r_i4);
mpf_mul_ui(ix, ix, 2);
/* Check for convergence */
if (!(mpf_cmp_si(r_i2, 0) &&
mpf_get_prec(r_i2) >= (unsigned)precision)) {
mpf_mul(pi->f, pi->f, r_i4);
mpf_div(pi->f, pi->f, r_i3);
break;
}
}
mpf_clear(ix);
mpf_clear(r_i2);
mpf_clear(r_i3);
mpf_clear(r_i4);
return (PyObject*)pi;
}
تعديل: كان لي بعض المشاكل مع قص ولصق وidentation، على أية حال يمكنك العثور على مصدر <لأ href = "http://code.google.com/p/gmpy/source/ تصفح / الفروع / aleax-رمل / SRC / gmpy.c "يختلط =" نوفولو noreferrer "> هنا .
وإذا كان عن طريق أسرع تقصد أسرع لكتابة رمز، وهنا الحل golfscript :
;''6666,-2%{2+.2/@*\/10.3??2*+}*`1000<~\;
استخدم الصيغة ماشين مثل
176 * arctan (1/57) + 28 * arctan (1/239) - 48 * arctan (1/682) + 96 * arctan(1/12943)
[; \left( 176 \arctan \frac{1}{57} + 28 \arctan \frac{1}{239} - 48 \arctan \frac{1}{682} + 96 \arctan \frac{1}{12943}\right) ;], for you TeX the World people.
ونفذت في مخطط، على سبيل المثال:
و(+ (- (+ (* 176 (atan (/ 1 57))) (* 28 (atan (/ 1 239)))) (* 48 (atan (/ 1 682)))) (* 96 (atan (/ 1 12943))))
إذا كنت على استعداد لاستخدام التقريب، 355 / 113 هو جيد لمدة 6 أرقام عشرية، ولها ميزة إضافية تتمثل في كونها قابلة للاستخدام مع التعبيرات عدد صحيح. هذا ليس من الأهمية في هذه الأيام، إذ أن "النقطة العائمة الرياضيات المشارك معالج" يعد لها أي معنى، ولكن من المهم جدا مرة واحدة.
ومع الزوجي:
4.0 * (4.0 * Math.Atan(0.2) - Math.Atan(1.0 / 239.0))
وهذه سوف تكون دقيقة تصل إلى 14 منازل عشرية، أي ما يكفي لملء مزدوج (عدم دقة وربما لأن بقية الكسور العشرية في الظلال قوس يتم اقتطاع).
وأيضا سيث، انها 3.14159265358979323846 <ب> 3 ، وليس 64.
حساب PI في الترجمة من الوقت مع D.
و(نسخ من DSource.org )
/** Calculate pi at compile time
*
* Compile with dmd -c pi.d
*/
module calcpi;
import meta.math;
import meta.conv;
/** real evaluateSeries!(real x, real metafunction!(real y, int n) term)
*
* Evaluate a power series at compile time.
*
* Given a metafunction of the form
* real term!(real y, int n),
* which gives the nth term of a convergent series at the point y
* (where the first term is n==1), and a real number x,
* this metafunction calculates the infinite sum at the point x
* by adding terms until the sum doesn't change any more.
*/
template evaluateSeries(real x, alias term, int n=1, real sumsofar=0.0)
{
static if (n>1 && sumsofar == sumsofar + term!(x, n+1)) {
const real evaluateSeries = sumsofar;
} else {
const real evaluateSeries = evaluateSeries!(x, term, n+1, sumsofar + term!(x, n));
}
}
/*** Calculate atan(x) at compile time.
*
* Uses the Maclaurin formula
* atan(z) = z - z^3/3 + Z^5/5 - Z^7/7 + ...
*/
template atan(real z)
{
const real atan = evaluateSeries!(z, atanTerm);
}
template atanTerm(real x, int n)
{
const real atanTerm = (n & 1 ? 1 : -1) * pow!(x, 2*n-1)/(2*n-1);
}
/// Machin's formula for pi
/// pi/4 = 4 atan(1/5) - atan(1/239).
pragma(msg, "PI = " ~ fcvt!(4.0 * (4*atan!(1/5.0) - atan!(1/239.0))) );
وبي هو بالضبط 3! [البروفيسور فرينك (عائلة سمبسون)]
ونكتة، ولكن هنا واحد في C # (. NET الإطار مطلوب).
using System;
using System.Text;
class Program {
static void Main(string[] args) {
int Digits = 100;
BigNumber x = new BigNumber(Digits);
BigNumber y = new BigNumber(Digits);
x.ArcTan(16, 5);
y.ArcTan(4, 239);
x.Subtract(y);
string pi = x.ToString();
Console.WriteLine(pi);
}
}
public class BigNumber {
private UInt32[] number;
private int size;
private int maxDigits;
public BigNumber(int maxDigits) {
this.maxDigits = maxDigits;
this.size = (int)Math.Ceiling((float)maxDigits * 0.104) + 2;
number = new UInt32[size];
}
public BigNumber(int maxDigits, UInt32 intPart)
: this(maxDigits) {
number[0] = intPart;
for (int i = 1; i < size; i++) {
number[i] = 0;
}
}
private void VerifySameSize(BigNumber value) {
if (Object.ReferenceEquals(this, value))
throw new Exception("BigNumbers cannot operate on themselves");
if (value.size != this.size)
throw new Exception("BigNumbers must have the same size");
}
public void Add(BigNumber value) {
VerifySameSize(value);
int index = size - 1;
while (index >= 0 && value.number[index] == 0)
index--;
UInt32 carry = 0;
while (index >= 0) {
UInt64 result = (UInt64)number[index] +
value.number[index] + carry;
number[index] = (UInt32)result;
if (result >= 0x100000000U)
carry = 1;
else
carry = 0;
index--;
}
}
public void Subtract(BigNumber value) {
VerifySameSize(value);
int index = size - 1;
while (index >= 0 && value.number[index] == 0)
index--;
UInt32 borrow = 0;
while (index >= 0) {
UInt64 result = 0x100000000U + (UInt64)number[index] -
value.number[index] - borrow;
number[index] = (UInt32)result;
if (result >= 0x100000000U)
borrow = 0;
else
borrow = 1;
index--;
}
}
public void Multiply(UInt32 value) {
int index = size - 1;
while (index >= 0 && number[index] == 0)
index--;
UInt32 carry = 0;
while (index >= 0) {
UInt64 result = (UInt64)number[index] * value + carry;
number[index] = (UInt32)result;
carry = (UInt32)(result >> 32);
index--;
}
}
public void Divide(UInt32 value) {
int index = 0;
while (index < size && number[index] == 0)
index++;
UInt32 carry = 0;
while (index < size) {
UInt64 result = number[index] + ((UInt64)carry << 32);
number[index] = (UInt32)(result / (UInt64)value);
carry = (UInt32)(result % (UInt64)value);
index++;
}
}
public void Assign(BigNumber value) {
VerifySameSize(value);
for (int i = 0; i < size; i++) {
number[i] = value.number[i];
}
}
public override string ToString() {
BigNumber temp = new BigNumber(maxDigits);
temp.Assign(this);
StringBuilder sb = new StringBuilder();
sb.Append(temp.number[0]);
sb.Append(System.Globalization.CultureInfo.CurrentCulture.NumberFormat.CurrencyDecimalSeparator);
int digitCount = 0;
while (digitCount < maxDigits) {
temp.number[0] = 0;
temp.Multiply(100000);
sb.AppendFormat("{0:D5}", temp.number[0]);
digitCount += 5;
}
return sb.ToString();
}
public bool IsZero() {
foreach (UInt32 item in number) {
if (item != 0)
return false;
}
return true;
}
public void ArcTan(UInt32 multiplicand, UInt32 reciprocal) {
BigNumber X = new BigNumber(maxDigits, multiplicand);
X.Divide(reciprocal);
reciprocal *= reciprocal;
this.Assign(X);
BigNumber term = new BigNumber(maxDigits);
UInt32 divisor = 1;
bool subtractTerm = true;
while (true) {
X.Divide(reciprocal);
term.Assign(X);
divisor += 2;
term.Divide(divisor);
if (term.IsZero())
break;
if (subtractTerm)
this.Subtract(term);
else
this.Add(term);
subtractTerm = !subtractTerm;
}
}
}
وهذا الإصدار (في دلفي) هو شيء خاص، ولكنه أسرع على الأقل من <لأ href = "http://blogs.codegear.com/nickhodges/2009/01/09/39174" يختلط = "noreferrer نوفولو "> النسخة نيك هودج نشرت على بلوق :). على الجهاز الخاص بي، ويستغرق حوالي 16 ثانية للقيام مليار التكرار، وإعطاء قيمة على 3.14159265 25879 (الجزء دقة هو بالخط العريض).
program calcpi;
{$APPTYPE CONSOLE}
uses
SysUtils;
var
start, finish: TDateTime;
function CalculatePi(iterations: integer): double;
var
numerator, denominator, i: integer;
sum: double;
begin
{
PI may be approximated with this formula:
4 * (1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 .......)
//}
numerator := 1;
denominator := 1;
sum := 0;
for i := 1 to iterations do begin
sum := sum + (numerator/denominator);
denominator := denominator + 2;
numerator := -numerator;
end;
Result := 4 * sum;
end;
begin
try
start := Now;
WriteLn(FloatToStr(CalculatePi(StrToInt(ParamStr(1)))));
finish := Now;
WriteLn('Seconds:' + FormatDateTime('hh:mm:ss.zz',finish-start));
except
on E:Exception do
Writeln(E.Classname, ': ', E.Message);
end;
end.
ومرة أخرى في الأيام الخوالي، مع أحجام كلمة صغيرة وعمليات الفاصلة العائمة بطيئة أو معدومة، كنا نفعل مثل هذه الاشياء:
/* Return approximation of n * PI; n is integer */
#define pi_times(n) (((n) * 22) / 7)
لالتطبيقات التي لا تتطلب الكثير من الدقة (ألعاب الفيديو، على سبيل المثال)، وهذا هو سريع جدا وغير دقيقة بما فيه الكفاية.
إذا كنت تريد حساب تقريبي من قيمة π (لسبب ما)، عليك أن تحاول خوارزمية استخراج الثنائية. تحسين Bellard في من <لأ href = "http://en.wikipedia.org/wiki / بيلي٪ E2٪ 80٪ 93Borwein٪ E2٪ 80٪ 93Plouffe_formula "يختلط =" noreferrer "> BBP يعطي يفعل PI في O (N ^ 2).
إذا كنت تريد الحصول تقريبي من قيمة π إلى القيام بعمليات حسابية، ثم:
PI = 3.141592654
ومنح، وهذا هو فقط تقريبي، وليس دقيقا تماما. انها من قبل ما يزيد قليلا على ،00000000004102. (أربعة عشر التريليون، حول <سوب> 4 / <الفرعية> 10000000000 ).
إذا كنت تريد أن تفعل <م> الرياضيات مع π، ثم الحصول على نفسك ورقة وقلم أو مجموعة الجبر الكمبيوتر، واستخدام π في القيمة الدقيقة، π.
إذا كنت تريد حقا صيغة، هذا هو واحد متعة:
π = - <م> <ط / م> قانون الجنسية (-1)
وطريقة برنت نشرت أعلاه كريس هو جيد جدا. برنت عموما عملاقة في مجال حساب دقيق تعسفي.
وإذا كان كل ما نريده هو الرقم نطة، الشهير BBP صيغة غير مفيدة في عرافة
وحساب π من منطقة الدوار: -)
<input id="range" type="range" min="10" max="960" value="10" step="50" oninput="calcPi()">
<br>
<div id="cont"></div>
<script>
function generateCircle(width) {
var c = width/2;
var delta = 1.0;
var str = "";
var xCount = 0;
for (var x=0; x <= width; x++) {
for (var y = 0; y <= width; y++) {
var d = Math.sqrt((x-c)*(x-c) + (y-c)*(y-c));
if (d > (width-1)/2) {
str += '.';
}
else {
xCount++;
str += 'o';
}
str += " "
}
str += "\n";
}
var pi = (xCount * 4) / (width * width);
return [str, pi];
}
function calcPi() {
var e = document.getElementById("cont");
var width = document.getElementById("range").value;
e.innerHTML = "<h4>Generating circle...</h4>";
setTimeout(function() {
var circ = generateCircle(width);
e.innerHTML = "<pre>" + "π = " + circ[1].toFixed(2) + "\n" + circ[0] +"</pre>";
}, 200);
}
calcPi();
</script>
أفضل نهج
لتحصل على إخراج الثوابت القياسية مثل <القوي> بي أو المفاهيم القياسية، يجب علينا أولا الذهاب مع الأساليب المتاحة builtins اللغة التي تستخدمه. فإنه سيعود قيمة في أسرع وسيلة وأفضل طريقة أيضا. أنا أستخدم الثعبان للحصول على أسرع طريقة للحصول على بي قيمة
- وعلى بي متغير من مكتبة الرياضيات . مكتبة الرياضيات مخزن بي متغير كما مستمر.
وmath_pi.py
import math
print math.pi
وتشغيل البرنامج النصي مع أداة وقت /usr/bin/time -v python math_pi.py لينكس
وإخراج:
Command being timed: "python math_pi.py"
User time (seconds): 0.01
System time (seconds): 0.01
Percent of CPU this job got: 91%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.03
- وعلى استخدام القوس كوس طريقة الرياضيات
وacos_pi.py
import math
print math.acos(-1)
وتشغيل البرنامج النصي مع أداة وقت /usr/bin/time -v python acos_pi.py لينكس
وإخراج:
Command being timed: "python acos_pi.py"
User time (seconds): 0.02
System time (seconds): 0.01
Percent of CPU this job got: 94%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.03
- وعلى صيغة BBP
وbbp_pi.py
from decimal import Decimal, getcontext
getcontext().prec=100
print sum(1/Decimal(16)**k *
(Decimal(4)/(8*k+1) -
Decimal(2)/(8*k+4) -
Decimal(1)/(8*k+5) -
Decimal(1)/(8*k+6)) for k in range(100))
وتشغيل البرنامج النصي مع أداة وقت /usr/bin/time -v python bbp_pi.py لينكس
وإخراج:
Command being timed: "python c.py"
User time (seconds): 0.05
System time (seconds): 0.01
Percent of CPU this job got: 98%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.06
<قوية> لذلك أفضل طريقة هي استخدام builtins طريقة التي تقدمها قضية اللغة التي هي أسرع وأفضل للحصول على المخرجات. في استخدام الثعبان math.pi