π Sayısını Hesaplama Algoritmaları

Bailey-Borwein-Plouffe (BBP) formülü

Bailey-Borwein-Plouffe (BBP) formülü, önceki haneleri hesaplamadan pi’nin (veya herhangi bir tabanda diğer sayıların) n’inci onaltılık hanesini hesaplamak için kullanılan bir formüldür. Formül, Simon Plouffe tarafından 1995 yılında keşfedilmiş olup, Peter Borwein ve Simon Plouffe’nin daha önceki çalışmalarına dayanmaktadır ve ayrıca David Bailey, Peter Borwein ve Simon Plouffe tarafından bağımsız olarak bulunmuştur.

BBP formülü, pi’yi, her bir terimin bir rasyonel sayı ile çarpıldığı ve 16’nın üsleri içeren bir toplam olarak ifade eden hızla yakınsayan bir seridir. Formül şöyledir:

pi = sum(k=0 to infinity) 16^(-k) * [4/(8k+1) – 2/(8k+4) – 1/(8k+5) – 1/(8k+6)]

BBP formülü, hesaplanan hanelerin önceki haneleri hesaplama gereksinimini ortadan kaldırdığı için, pi’nin onaltılık hanelerini hesaplama konusunda çok etkili bir yöntemdir. Formül, diğer sayı tabanları için de 16’nın uygun üssünü kullanarak adapte edilebilir.

BBP formülü, yüksek hassasiyete sahip pi hesaplamanın verimli bir yöntemi gerektiren bilgisayar bilimi ve kriptografi gibi alanlarda birçok uygulama bulmuştur. Ancak, BBP formülü, pi’nin genel olarak hesaplanması için daha genel bir formül sağlamadığından, pi’nin çoğu bilimsel uygulamasında sınırlı pratik kullanıma sahiptir.

C dilinde yazılmış π sayısını hesaplayan program

Altaki programı https://www.onlinegdb.com/ sitesinde test edebilirsiniz

#include "stdio.h"
#include "stdlib.h"
#include "gmp.h"

mpz_t tmp1, tmp2, t5, t239, pows;
void actan(mpz_t res, unsigned long base, mpz_t pows)
{
	int i, neg = 1;
	mpz_tdiv_q_ui(res, pows, base);
	mpz_set(tmp1, res);
	for (i = 3; ; i += 2) {
		mpz_tdiv_q_ui(tmp1, tmp1, base * base);
		mpz_tdiv_q_ui(tmp2, tmp1, i);
		if (mpz_cmp_ui(tmp2, 0) == 0) break;
		if (neg) mpz_sub(res, res, tmp2);
		else	  mpz_add(res, res, tmp2);
		neg = !neg;
	}
}

char * get_digits(int n, size_t* len)
{
	mpz_ui_pow_ui(pows, 10, n + 20);

	actan(t5, 5, pows);
	mpz_mul_ui(t5, t5, 16);

	actan(t239, 239, pows);
	mpz_mul_ui(t239, t239, 4);

	mpz_sub(t5, t5, t239);
	mpz_ui_pow_ui(pows, 10, 20);
	mpz_tdiv_q(t5, t5, pows);

	*len = mpz_sizeinbase(t5, 10);
	return mpz_get_str(0, 0, t5);
}

int main(int c, char **v)
{
	unsigned long accu = 16384, done = 0;
	size_t got;
	char *s;

	mpz_init(tmp1);
	mpz_init(tmp2);
	mpz_init(t5);
	mpz_init(t239);
	mpz_init(pows);

	while (1) {
		s = get_digits(accu, &got);

		
		got -= 2; 
		while (s[got] == '0' || s[got] == '9') got--;

		printf("%.*s", (int)(got - done), s + done);
		free(s);

		done = got;
		accu *= 2;
	}

	return 0;
}

Amstrad CPC BASIC dilinde π sayısını hesaplayan Spigot Algortiması

Spigot algoritması, tüm önceki basamakları hesaplamadan pi sayısının basamaklarını birer birer hesaplamak için kullanılan bir yöntemdir. İlk olarak Stanley Rabinowitz ve Stan Wagon tarafından 1995 yılında önerilmiştir ve bir “musluk” veya “tap” fikrine dayanır, bu tap birer birer pi sayısının basamaklarını çıkarmak için kullanılabilir.

Algoritma aşağıdaki gibi çalışır:

1. Algoritmanın durumunu temsil etmek için bir dizi değişkeni başlatın.
2. Her bir pi basamağını tek tek hesaplayın, ilk basamaktan başlayarak.
3. Yeni basamağı eklemek için önceki tüm basamakları sağa kaydırın.
4. İstenilen sayıda basamağı hesaplamak için adımları 2-3 tekrarlayın.

Spigot algoritması, pi sayısı için seri kimlik ve yaklaşımlar kullanarak, her basamağı sadece tamsayı aritmetiği kullanarak hesaplayan bir yöntemdir. Temel fikir, pi’nin bir devam eden kesir genişlemesini kullanmaktır, bu genişleme şu şekilde yazılabilir:

pi = 3 + 1/(7 + 1/(15 + 1/(1 + 1/(292 + …))))

Bu devam eden kesir, her adımda sadece birkaç terim hesaplamayı gerektiren şekilde kullanılabilir. Anahtar fikir, bu devam eden kesirden birer birer pi sayısının basamaklarını hesaplamak için “musluk” veya “tap” kullanmaktır, böylece önceki tüm basamakları hesaplamak gerekmez.

Spigot algoritması, C, Python ve Java gibi çeşitli programlama dilleri ve ortamlarında uygulanmıştır. Algoritma, hesaplama karmaşıklığı ve algoritma ile hesaplanabilecek büyük sayıda basamaklar nedeniyle, bilgisayar donanımı ve yazılımının performansını test etmek için sıklıkla bir ölçüt olarak kullanılmaktadır.

Altaki BASIC dilinde yazılmış olan programı https://benchmarko.github.io/CPCBasic/index.html bu sitede deneybilirsiniz

10 REM Amstrad CPC464
20 n = 1000
21 pi2$=””
30 ln = int(10*n/3)+16
40 nd = 1
50 dim a(ln)
60 n9 = 0
70 pd = 0 : rem First pre-digit is a 0
80 rem
90 for j = 1 to ln
100 a(j-1) = 2 : rem Start wirh 2S
110 next j
120 rem
130 for j = 1 to n
140 q = 0
150 for i = ln to 1 step -1 : rem Work backwards
160 x = 10*a(i-1)+q*i
170 a(i-1) = x-(2*i-1)*int(x/(2*i-1)) : rem X – Int ( X / Y) * Y
180 q = int(x/(2*i-1))
190 next i
200 a(0) = q-10*int(q/10)
210 q = int(q/10)
220 if q = 9 then n9 = n9+1 : goto 420
230 if q 10 then goto 350 ‘ burada eşit işaretini kaldırın
240 rem Q == 10
250 d = pd+1 : gosub 480
260 if n9 <= 0 then goto 310
270 for k = 1 to n9
280 d = 0 : gosub 480
290 next k
300 rem End If
310 pd = 0
320 n9 = 0
330 goto 420
340 rem Q 10
350 d = pd : gosub 480
360 pd = q
370 if n9 = 0 then goto 420
380 for k = 1 to n9
390 d = 9 : gosub 480
400 next k
410 n9 = 0
420 next j
430 pi2$=pi2$+mid$(str$(d),2) ‘print str$(pd)
440 print pi2$
450 end
460 rem
470 rem Output digits
480 if nd=0 then pi2$=pi2$+mid$(str$(d),2):return
500 if d = 0 then return
510 pi2$=pi2$+str$(d)+”.”
520 nd = 0
530 return

Program tarafından hesaplanan Pi 1000 basamak
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118548074462379962749567351885752724891227938183011949129833673362440656643086021394946395224737190702179860943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901224953430146549585371050792279689258923542019956112129021960864034418159813629774771309960518707211349999998372978049951059731732816096318595024459455346908302642522308253344685035261931188171010003137838752886587533208381420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909216420199

Full Precision Calculator sonucu

https://www.mathsisfun.com/calculator-precision.html

3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118548074462379962749567351885752724891227938183011949129833673362440656643086021394946395224737190702179860943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901224953430146549585371050792279689258923542019956112129021960864034418159813629774771309960518707211349999998372978049951059731732816096318595024459455346908302642522308253344685035261931188171010003137838752886587533208381420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909216420199

François Viète’nin pi sayısı için formülü

“François Viète’nin pi sayısı için formülü” olarak bahsettiğinizi düşünüyorum. François Viète, 16. yüzyılda yaşamış bir Fransız matematikçidir ve pi sayısının yaklaşık bir değerini hesaplamak için bir formül keşfetmiştir.

Bu formül, iç içe geçmiş köklerin oranlarının sonsuz bir çarpımına dayanır ve şöyle yazılabilir:

π = 2 × (2/√2) × (2/√(2+√2)) × (2/√(2+√(2+√2))) × …

Bu formül, sonsuz bir çarpımın bir örneğidir ve ilk n terimini çarparak pi’yi yüksek bir doğruluk derecesine kadar hesaplamak için kullanılabilir. Ancak, çok yavaş bir şekilde yakınsar, bu nedenle iyi bir yaklaşım elde etmek için birçok terim gereklidir.

Değerlendirme yapmak için Viète’nin formülünden daha verimli olan birçok başka algoritma bulunması da dikkat çekicidir.