Можно сказать сразу — миллион не предел. Можно и больше. Подробности и реализация под катом.
Реализация вычислений
Даже животному семейства Erinaceidae (т.е. ежу) ясно что если мы хотим вычислить число Пи до миллиона знаков — типа float нам не хватит. И даже double тоже (где был тег «сарказм»?). Значит надо искать библиотеку для работы с длинными числами. На iOS используется Objective C (и Swift тоже но в данном случае он нам не нужен), который обратно совместим с Си, что несколько облегчает задачу — разных библиотек на Си довольно много. Небольшой поиск привел к библиотеке GMP, которая с одной стороны, делает то что нам нужно, с другой стороны, весьма проста в использовании.
Например, чтобы вывести 1000 знаков sqrt(3), достаточно следующего кода:
#include "gmp.h"
#include "gmpxx.h"
mpf_set_default_prec(4096);
mpf_class num;
mpf_sqrt_ui(num.get_mpf_t(), 3);
gmp_printf("%.*Ff\n", 1000, num.get_mpf_t());Полный список функций для работы с float можно найти здесь.
Алгоритм
С библиотекой разобрались. Следующим встает вопрос, какой алгоритм использовать. Вопрос не совсем праздный, т.к. способов вычисления Пи довольно-таки много. Формула Белларда:
Формула Бэйли — Боруэйна — Плаффа:
Формула Мачина:
Формула Чудновского (не спрашивайте меня как он ее вывел — не знаю):
Последняя формула на вид самая «страшная», но в то же время, самая быстрая.
Код
Для проверки алгоритмов, все они были собраны в один файл на Питоне (он тоже поддерживает «длинные числа» в типе Decimal).
import sys
import math
from decimal import *
from math import factorial
from time import time
# http://thelivingpearl.com/2013/05/28/computing-pi-with-python/
# http://www.numberworld.org/misc_runs/pi-5t/details.html
# Bellard's Formula PI
def bellard(n):
pi = Decimal(0)
k = 0
while k < n:
pi += (Decimal(-1)**k/(1024**k))*( Decimal(256)/(10*k+1) + Decimal(1)/(10*k+9) - Decimal(64)/(10*k+3) - Decimal(32)/(4*k+1) - Decimal(4)/(10*k+5) - Decimal(4)/(10*k+7) - Decimal(1)/(4*k+3))
k += 1
pi = pi * 1/(2**6)
return pi
# Bailey-Borwein-Plouffe formula
def bbp(n):
pi = Decimal(0)
k = 0
while k < n:
pi += (Decimal(1)/(16**k))*((Decimal(4)/(8*k+1))-(Decimal(2)/(8*k+4))-(Decimal(1)/(8*k+5))-(Decimal(1)/(8*k+6)))
k += 1
return pi
# http://www.craig-wood.com/nick/articles/pi-chudnovsky/
def chudnovsky(n):
pi = Decimal(0)
k = 0
while k < n:
pi += (Decimal(-1)**k)*(Decimal(factorial(6*k))/((factorial(k)**3)*(factorial(3*k)))* (13591409+545140134*k)/(640320**(3*k)))
k += 1
pi = pi * Decimal(10005).sqrt()/4270934400
pi = pi**(-1)
return pi
def chudnovsky2(n):
pi = Decimal(13591409)
ak = Decimal(1)
k = 1
while k < n:
ak *= -Decimal((6*k-5)*(2*k-1)*(6*k-1))/Decimal(k*k*k*26680*640320*640320)
val = ak*(13591409 + 545140134*k)
d = Decimal((6*k-5)*(2*k-1)*(6*k-1))/Decimal(k*k*k*26680*640320*640320)
pi += val
k += 1
pi = pi * Decimal(10005).sqrt()/4270934400
pi = pi**(-1)
return pi
# arctan
# http://www.craig-wood.com/nick/articles/pi-machin/
def arctan(x):
"""
Calculate arctan(1/x)
arctan(1/x) = 1/x - 1/3*x**3 + 1/5*x**5 - ... (x >= 1)
This calculates it in fixed point, using the value for one passed in
"""
x2 = x*x
x = Decimal(x)
total = Decimal(0)
sign = 1
for i in range(1, 512, 2):
#total += sign / (i * x)
total += sign / (i * x ** i)
sign = -sign
#x *= x2
#print(total)
return total
def pi_machin(n):
return 4*(4*arctan(5) - arctan(239))
def pi_gauss(one):
return 4*(12*arctan(18) + 8*arctan(57) - 5*arctan(239))
if __name__ == "__main__":
N = 1000
getcontext().prec = N
print ""
print "Atan"
start = time()
my_pi = pi_machin(N)
print "Pi = {}".format(str(my_pi))
print("Time", time()-start)
print "BBP"
start = time()
my_pi = bbp(N)
print "Pi = {}".format(str(my_pi))
print("Time", time()-start)
print "Bellard"
start = time()
my_pi = bellard(N)
print "Pi = {}".format(str(my_pi))
print("Time", time()-start)
print ""
print "Chudnovsky"
start = time()
my_pi = chudnovsky(N/14)
print "Pi = {}".format(str(my_pi))
print("Time", time()-start)
print ""
print "Chudnovsky2"
start = time()
my_pi = chudnovsky2(N/14)
print "Pi = {}".format(str(my_pi))
print("Time", time()-start)
Результаты запуска скрипта:
Формула Мачина: 2.01c
Формула Бэйли — Боруэйна — Плаффа: 1.42c
Формула Белларда: 1.82c
Формула Чудновского: 0.22c
Формула Чудновского (без факториала): 0.082c
Как можно видеть, даже с использованием факториала «в лоб» (что довольно долго), формула Чудновского быстрее предыдущих в 5-10 раз. Преобразование ее к виду без факториала (с использованием предыдущего значения) дает ускорение еще в несколько раз. В общем, победитель очевиден, но есть одно «но» — объем оперативной памяти. Если «идти на рекорд», и например считать миллиард знаков числа Пи, то критичным становится вопрос хранения данных в RAM. У iPhone всего лишь 1Гб памяти, причем для пользовательской программы доступно 512Мб. Если запросить примерно 600Мб, iOS просто закроет приложение. При подсчете миллиона знаков это еще не так критично (программа занимает в памяти не более 30Мб), но если брать больше, это станет критичным. И тут формула Чудновского будет в заметном проигрыше из-за сложности выполняемых операций, тут вполне могут пригодиться более простые алгоритмы.
Кстати о миллиарде знаков. Как показал запуск в симуляторе, при попытке создать число с миллиардом знаков, программа пытается выделить более 5Гб памяти, и при этом разумеется падает. По прикидкам, максимальное число, которое в принципе можно посчитать на iPhone, составляет около 200млн. знаков. На Android можно получить больше (кто бы сомневался:). Разумеется на вычисление уйдет не один день, но это уже другой вопрос.
Ниже приведен исходный код на Objective-C. Т.к. работа с библиотекой GMP несколько громоздка, код получился не очень красивым, но разобраться в принципе можно (да и на любом языке можно писать как на Фортране:).
#include "gmp.h"
#include "gmpxx.h"
- (void) calcPi {
/*
# Python source
pi = Decimal(13591409)
ak = Decimal(1)
k = 1
while k < n:
ak *= -Decimal((6*k-5)*(2*k-1)*(6*k-1))/Decimal(k*k*k*26680*640320*640320)
val = ak*(13591409 + 545140134*k)
pi += val
k += 1
#print "Iteration: {} of {}".format(k, n)
pi = pi * Decimal(10005).sqrt()/4270934400
pi = pi**(-1)
return pi
*/
unsigned long int bits = [self getBitsSize];
mpf_set_default_prec(bits);
NSDate *date1 = [NSDate date];
mpf_class pi = 13591409;
mpf_class ak = 1;
mpf_class v1, v2, v3, tmp1, d = 0, d1 = 0;
unsigned long int N = (unsigned long int)self.numDigits/14;
for(unsigned long int k=1; k<N; k++) {
// (6*k-5)*(2*k-1)*(6*k-1)
v1 = 6*k-5;
mpf_mul_ui(v2.get_mpf_t(), v1.get_mpf_t(), 2*k-1);
mpf_mul_ui(v1.get_mpf_t(), v2.get_mpf_t(), 6*k-1); // v1 = (6*k-5)*(2*k-1)*(6*k-1)
// k*k*k*26680*640320*640320
v2 = k;
mpf_mul_ui(v3.get_mpf_t(), v2.get_mpf_t(), k);
mpf_mul_ui(v2.get_mpf_t(), v3.get_mpf_t(), k);
mpf_mul_ui(tmp1.get_mpf_t(), v2.get_mpf_t(), 26680); // tmp <= k*26680
mpf_mul_ui(v2.get_mpf_t(), tmp1.get_mpf_t(), 640320);
mpf_mul_ui(tmp1.get_mpf_t(), v2.get_mpf_t(), 640320);
// v2 <= v1/tmp = (6*k-5)*(2*k-1)*(6*k-1)/(k*k*k*26680*640320*640320)
mpf_div(v2.get_mpf_t(), v1.get_mpf_t(), tmp1.get_mpf_t());
mpf_neg(v1.get_mpf_t(), v2.get_mpf_t()); // v1 = -v1
mpf_mul(tmp1.get_mpf_t(), ak.get_mpf_t(), v1.get_mpf_t()); // tmp <= ak*v1
mpf_set(ak.get_mpf_t(), tmp1.get_mpf_t()); // ak = ak*v1
v1 = 545140134;
mpf_mul_ui(v2.get_mpf_t(), v1.get_mpf_t(), k); // v2 = 545140134*k
mpf_add_ui(v1.get_mpf_t(), v2.get_mpf_t(), 13591409); // v1 = 545140134*k + 13591409
mpf_mul(tmp1.get_mpf_t(), v1.get_mpf_t(), ak.get_mpf_t()); // tmp1 = v1*ak
mpf_add(v1.get_mpf_t(), tmp1.get_mpf_t(), pi.get_mpf_t()); // v1 = tmp1 + pi
mpf_set(pi.get_mpf_t(), v1.get_mpf_t()); // pi = v1
if (k % 5 == 0) {
// Release CPU when app is inactive, otherwise app will be killed by iOS
if ([[UIApplication sharedApplication] applicationState] != UIApplicationStateActive)
[NSThread sleepForTimeInterval:3];
}
}
mpf_sqrt_ui(d1.get_mpf_t(), 10005); // d1 = sqrt(10005)
mpf_mul(d.get_mpf_t(), d1.get_mpf_t(), pi.get_mpf_t()); // d = d1*pi
mpf_div_ui(d1.get_mpf_t(), d.get_mpf_t(), 4270934400); // d1 = d/4270934400
mpf_ui_div(d.get_mpf_t(), 1, d1.get_mpf_t()); // d = 1/d1
double diff = [[NSDate date] timeIntervalSinceDate:date1];
//gmp_printf("pi: %.*Ff\n", self.numDigits, d.get_mpf_t()); // Not works for big numbers, only for debugging
[self valueSave:d.get_mpf_t() time:diff];
NSLog(@"Done-pi, time = %.2f", diff);
self.totalTime = diff;
}
- (void)valueSave:(mpf_t)val time:(double)time{
NSString *docsDirectory = [NSSearchPathForDirectoriesInDomains(NSDocumentDirectory, NSUserDomainMask, YES) objectAtIndex:0];
NSString *name = [NSString stringWithFormat:@"value-%llu.txt", self.numDigits];
NSString *path = [docsDirectory stringByAppendingPathComponent:name];
FILE *fp = fopen ([path UTF8String], "w+");
char buf[255];
sprintf(buf, "Time: %fs\n", time);
fwrite(buf , sizeof(char), strlen(buf), fp);
mpf_out_str(fp, 10, 0, val); // 10-основание системы счисления
fclose(fp);
NSLog(@"Saved in: %@", path);
}
- (unsigned long int)getBitsSize {
// Calculate the number of bits, required to store numDigits (empiric way)
return (unsigned long int)(2.5*self.numDigits/log(2));
}
Для тех кто захочет поэкспериментировать самостоятельно, здесь выложен исходный код проекта для XCode. Конечно, приведенный выше алгоритм не идеален, его например вполне можно распараллелить хотя бы на 2 потока. Или даже попробовать использовать Accelerate Framework.
Результаты
При запуске на iPhone вылезли несколько забавных проблем. Первая — программа ни за что не хотела работать в бэкграунде, процесс вычислений просто останавливался. На тестовом iPhone 5S стояла iOS8, не знаю изменился ли принцип многозадачности в iOS9, но для 8ки решение оказалось простым — запустить GPS и подписаться на события от location service. При этом iOS «считает» что нам нужно постоянно получать координаты юзера, и позволяет программе работать даже в свернутом состоянии.
Вторая проблема вылезла минутой позже после первой. Как оказалось, iOS достаточно «умна», и считает подозрительным процесс, жрущий в фоне 100% ресурсов процессора. Видимо iOS считает что программа «повисла», и «убивает» ее примерно через минуту такой работы. Пришлось внутрь цикла вставить sleep с таким расчетом, чтобы «скважность» загрузки CPU была где-то 50/50. После этого программа могла считать и в фоновом режиме, хотя конечно скорость стала вдвое ниже. В итоге iPhone был просто подключен к зарядному устройству и оставлен на ночь, программа не закрывалась.
И наконец, обещанный результат: на iPhone 5S миллион знаков числа Пи вычислялись 49296 секунд, или около 14 часов. Кстати, на симуляторе с Core i7 время расчета составляет 4200 секунд, т.е. примерно в 11 раз быстрее. Интересно прикинуть, сколько будет вычисляться 100млн знаков. Оставляю это в качестве домашнего задания тем, кто дочитал до сюда. Также было бы интересно увидеть результаты для более новых (чем 5S) моделей iPhone. Программа во время расчетов показывает примерное время выполнения, результат сохраняется в папку iTunes file sharing.
Правка
В комментах подсказали сравнить программу с реализациями в Google Play. Как оказалось, там используется алгоритм Arithmetic-Geometric Mean (AGM), который действительно в разы быстрее. С последней версией вычисление миллиона знаков на iPhone 5S заняло 68 секунд.
Описание алгоритма и реализация на Python есть здесь: http://www.johndcook.com/blog/2012/06/03/calculating-pi-with-agm-and-mpmath/. C/С++ код для GMP доступен здесь: https://rosettacode.org/wiki/Arithmetic-geometric_mean/Calculate_Pi.
Тем кто захочет проверить
Зачем это надо?
Что касается мирового рекорда (который для десктопа составляет 5трлн знаков, правда и десктоп был не рядовым), то вряд ли его удастся побить на смартфоне. Да и подобной таблицы рекордов для смартфонов вроде еще никто не делал. Однако дело конечно не в рекорде — как можно видеть, подобные расчеты представляют собой достаточно интересную инженерную задачу, где остаются открытыми вопросы оптимизации и памяти, и скорости вычислений, и многопоточности. В общем, есть где «пошевелить мозгами», что как раз и наиболее интересно в программировании.
Комментарии (32)
galaxy
11.09.2016 03:53+2И наконец, обещанный результат: на iPhone 5S миллион знаков числа Пи вычислялись 49296 секунд, или около 14 часов
Фиговенький результат.
Вот, например: http://numbers.computation.free.fr/Constants/PiProgram/pifast.html
This mode is the fastest when there are enough physical memory.
Timings sample on a Pentium 4 1.4 Ghz with 1024 Mo running on Windows
NT (notice that no particular compilation has been made to benefit from
Pentium 4 specific instructions) :
PI Computation : (timings with version 4.1)
1 Million decimal digits : 9.69 seconds
2 Million decimal digits : 22.78 seconds
4 Million decimal digits : 50.80 seconds
8 Million decimal digits : 116.38 seconds
16 Million decimal digits : 264.9 seconds
32 Million decimal digits : 583.25 seconds
64 Million decimal digits : 1327 seconds
128 Million decimal digits : 2974 seconds
На моем ноуте 10 млн. цифр — 23 секDmitrySpb79
11.09.2016 08:46+1Спасибо, интересно.
Но во-первых, вышеприведенный алгоритм был закодирован за полчаса, и вряд ли претендует на «the fastest windows program to compute pi» (у них там уже 4.3 версия).
Во-вторых, the source code of PiFast is not available — проверить на iPhone все равно не получится.
maks1mm
11.09.2016 11:58+1Может, тогда ради интереса попробуйте оптимизировать?
Скачал первую попавшеюся программку для расчета Пи на свой андроид, девайс старый, ему почти 4 года, Snapdragon 410 — миллион знаков посчитал за 13.34 секунды. А ведь iphone SE в разы шустрее моего кирпича.DmitrySpb79
11.09.2016 12:05Да, допускаю что я что-то пропустил :) Попробую конечно, результат в статье дополню по появлении новых результатов.
DmitrySpb79
11.09.2016 12:59Кстати, перепроверил код еще раз. Можно вынести вычисление 26680*640320*640320 за цикл, можно заменить 3 умножения на одну функцию степени. По прикидке, это даст выигрыш в 5% где-то. Можно запустить в 2 потока — получится допустим, не 13 часов а 6.
Но так чтобы 13 секунд на старом смартфоне — странно. Тут по ссылке выше писали что 10секунд на Pentium-4 считалось, который явно помощнее будет. Может у них просто заранее подсчитанный файл в памяти лежит? :)
Ну либо я не учитываю что-то, хз.Beyondtheclouds
11.09.2016 14:05>10секунд на Pentium-4 считалось, который явно помощнее будет.
Твои данные сильно устарели :)
http://browser.primatelabs.com/v4/cpu/264152
http://browser.primatelabs.com/ios-benchmarks
Разница в 4 раза насколько я понимаю, и не в пользу 4 пня )
DmitrySpb79
11.09.2016 15:05В общем нашел, там действительно используется другой алгоритм. Поправил результаты в тексте.
maks1mm
11.09.2016 18:51Что интересно, после генерации все число посмотреть невозможно, прога показывает только последние цифры.
А если захотеть посмотреть N-е число предупреждает что это будет очень долго.
Возможно какая-то хитрость там и есть.
Вот ссылка на гугл маркет link
Cкрин после расчетов под спойлером
Скрытый текст
galaxy
11.09.2016 18:39the fastest windows program to compute pi
Ну, это на 2003 год.
Там используется одно важное алгоритмическое решение: http://numbers.computation.free.fr/Constants/Algorithms/splitting.html
inakrin
11.09.2016 05:29+1Кстати вопрос. А где именно в Ведах есть значение числа Пи ну и вся прочая математика известная древним индийцам? Хотелось бы почитать оригинал переведенный на русский либо английский. Нагуглить ничего не получилось — вся поисковая выдача завалена философией адвайты и чем угодно но только не математикой.
Stecenko
11.09.2016 08:08В вики в истории числа Пи написано: «Ведийский текст «Шатапатха-брахмана» даёт pi как 339/108 ? 3,139»
Тексты этой книги на английском языке: www.sacred-texts.com/hin/sbr/index.htm.
sim31r
12.09.2016 03:41Не смог удержаться, посчитал все варианты рационального приближения в разумных пределах по поиску числа Pi делением двух простых чисел, как делали в древнем мире, по моему интересная задача:
ошибка; действие
4,7%; 9/3
3,34%; 13/4
1,8%; 16/5
0,8%; 19/6
0,04%; 22/7 — удобный вариант для столь малых чисел (даже лучше чем Чжан Хэн во II веке предложил 92/29 с ошибкой в 1%), первым предложил Архимед.
0,039%; 179/57
0,03%; 201/64
0,024%; 223/71
0,018%; 245/78
0,013%; 267/85
0,009%; 289/92
0,0056%; 311/99
0,0026%; 333/106 — почти как в том религиозном ведийском тексте, но точнее почти в 40 раз, там 0,086% ошибка, казалось бы очень близко, но немного не попали.
8,49136715180762E-6%; 355/113 — тоже удобный вариант, при больших последующих цифрах точность не растет существенно. В 480-х годах китайский математик Цзу Чунчжи продемонстрировал… Это значение оставалось самым точным приближением числа pi в течение последующих 900 лет.
И не удивительно, следующая итерация на порядок сложнее. Резкий рост сложности при небольшом росте точности:
8,47383188246871E-6%; 52163/16604
8,35915415110094E-6%; 52518/16717
Тут не интересно почти одинаковые ряды цифр без исторической ценности8,24601634587631E-6%; 52873/16830
8,13438766487423E-6%; 53228/16943
8,02423812605099E-6%; 53583/17056
7,91553851069651E-6; 53938/17169
7,80826037757015E-6; 54293/17282
7,70237603462907E-6; 54648/17395
7,597858482485E-6; 55003/17508
7,49468142854007E-6; 55358/17621
7,39281925871516E-6; 55713/17734
7,29224698090669E-6; 56068/17847
7,19294026739402E-6; 56423/17960
7,09487535588881E-6; 56778/18073
6,99802912021403E-6; 57133/18186
6,90237897135335E-6; 57488/18299
6,80790289985851E-6; 57843/18412
6,71457940517032E-6; 58198/18525
6,62238752389025E-6; 58553/18638
6,53130680150882E-6; 58908/18751
6,44131727826978E-6; 59263/18864
6,35239944676271E-6; 59618/18977
6,26453429433043E-6; 59973/19090
6,17770321825414E-6; 60328/19203
6,09188808229667E-6; 60683/19316
6,00707116015922E-6; 61038/19429
5,92323512134561E-6; 61393/19542
5,84036305943381E-6; 61748/19655
5,75843844966859E-6; 62103/19768
5,67744513482567E-6; 62458/19881
5,59736731107594E-6; 62813/19994
5,51818954212124E-6; 63168/20107
5,43989675919436E-6; 63523/20220
5,36247419038006E-6; 63878/20333
5,28590741715819E-6; 64233/20446
5,21018231786058E-6; 64588/20559
5,13528511007836E-6; 64943/20672
5,0612022658472E-6; 65298/20785
4,98792058232629E-6; 65653/20898
4,91542713939092E-6; 66008/21011
4,8437092854967E-6; 66363/21124
4,77275463767957E-6; 66718/21237
4,70255108155574E-6; 67073/21350
4,63308674305014E-6; 67428/21463
4,56435003080379E-6; 67783/21576
4,49632955135901E-6; 68138/21689
4,4290141657026E-6; 68493/21802
4,36239297513005E-6; 68848/21915
4,29645530710975E-6; 69203/22028
4,23119067287555E-6; 69558/22141
4,16658883810578E-6; 69913/22254
4,10263975224427E-6; 70268/22367
4,03933357677188E-6; 70623/22480
3,976660656935E-6; 70978/22593
3,91461153588123E-6; 71333/22706
3,85317695465947E-6; 71688/22819
3,79234782394828E-6; 72043/22932
3,73211523819166E-6; 72398/23045
3,67247046146331E-6; 72753/23158
3,61340492746656E-6; 73108/23271
3,55491026780599E-6; 73463/23384
3,49697819890105E-6; 73818/23497
3,43960069161564E-6; 74173/23610
3,38276978749271E-6; 74528/23723
3,32647772597646E-6; 74883/23836
3,27071687373333E-6; 75238/23949
3,2154797529236E-6; 75593/24062
3,16075901292983E-6; 75948/24175
3,10654744449258E-6; 76303/24288
3,05283799384627E-6; 76658/24401
2,99962369204018E-6; 77013/24514
2,94689773975319E-6; 77368/24627
2,89465342247904E-6; 77723/24740
2,84288420947691E-6; 78078/24853
2,79158361241342E-6; 78433/24966
2,74074532672059E-6; 78788/25079
2,69036310437372E-6; 79143/25192
2,64043085284191E-6; 79498/25305
2,59094256440911E-6; 79853/25418
2,54189234444568E-6; 80208/25531
2,49327439727263E-6; 80563/25644
2,44508305443319E-6; 80918/25757
2,39731270401382E-6; 81273/25870
2,34995786132321E-6; 81628/25983
2,30301311234906E-6; 81983/26096
2,25647318443711E-6; 82338/26209
2,21033284734052E-6; 82693/26322
2,16458696976308E-6; 83048/26435
2,1192305193592E-6; 83403/26548
2,0742585485981E-6; 83758/26661
2,02966619476384E-6; 84113/26774
1,9854486516837E-6; 84468/26887
1,94160124040716E-6; 84823/27000
1,89811931025535E-6; 85178/27113
1,85499832363578E-6; 85533/27226
1,81223378536343E-6; 85888/27339
1,76982132747545E-6; 86243/27452
1,72775658200904E-6; 86598/27565
1,6860353223594E-6; 86953/27678
1,64465335019335E-6; 87308/27791
1,60360652372093E-6; 87663/27904
1,5628908142386E-6; 88018/28017
1,52250222131442E-6; 88373/28130
1,48243680105968E-6; 88728/28243
1,44269072267208E-6; 89083/28356
1,40326015534932E-6; 89438/28469
1,36414138137554E-6; 89793/28582
1,32533069717068E-6; 90148/28695
1,28682448396948E-6; 90503/28808
1,24861917954991E-6; 90858/28921
1,21071124996156E-6; 91213/29034
1,1730972602046E-6; 91568/29147
1,13577380355084E-6; 91923/29260
1,09873750154369E-6; 92278/29373
1,06198508881297E-6; 92633/29486
1,02551328585272E-6; 92988/29599
9,89318897971778E-7; 93343/29712
9,53398772886396E-7; 93698/29825
9,17749814856038E-7; 94053/29938
8,82368942275979E-7; 94408/30051
8,47253172492096E-7; 94763/30164
8,12399508714484E-7; 95118/30277
7,77805053103839E-7; 95473/30390
7,4346690782087E-7; 95828/30503
7,09382231569494E-7; 96183/30616
6,75548239596832E-7; 96538/30729
6,4196216128582E-7; 96893/30842
6,08621310834192E-7; 97248/30955
5,75522988303898E-7; 97603/31068
5,42664550300092E-7; 97958/31181
5,10043424106933E-7; 98313/31294
4,7765702287279E-7; 98668/31407
4,45502844560836E-7; 99023/31520
4,13578387134253E-7; 99378/31633
3,81881205099427E-7; 99733/31746
3,50408867098552E-7; 100088/31859
3,19158998317026E-7; 100443/31972
2,88129238076054E-7; 100798/32085
2,57317296375846E-7; 101153/32198
2,26720854945019E-7; 101508/32311
1,96337680326993E-7; 101863/32424
1,66165553200993E-7; 102218/32537
1,36202268382054E-7; 102573/32650
1,06445663092611E-7; 102928/32763
7,68936310983031E-8; 103283/32876
4,75440378931792E-8; 103638/32989
1,83948337860874E-8; 103993/33102
1,05560450499157E-8; 104348/33215
3,89472739745897E-9; 208341/66317
9,27657882316268E-10%; 312689/99532
2,77418946985962E-10%; 833719/265381
5,12666416965132E-11%; 1146408/364913Stecenko
12.09.2016 06:14+1Вероятно, Вы хотели сказать «поиску числа Pi делением двух чисел, одно из которых простое».
Кстати, на Флибусте есть сочинения Архимеда в переводе на русский, в дежавю, где есть и «Измерение круга».
А здесь разъяснение метода, используемого Архимедом для вычисления Пи, вся цепочка рассуждений.
winnipeg
11.09.2016 08:08+4Стало интересно, можно ли вычислить Пи на iPhone
Вот действительно! Тривиальный вопрос, вопрос возникающий сам собой!:)
Если серьезно, у меня возникает вопрос: зачем? Так, просто провести время?)
Scratch
11.09.2016 08:57+1Есть же вроде алгоритмы, которым пофиг на память, они лупят себе цифры и лупят, не оглядываясь назад
https://en.wikipedia.org/wiki/Pi#Spigot_algorithms
Хоть квинтиллион знаков на своём айфоне считайтеDmitrySpb79
11.09.2016 09:02+1Да, есть алгоритм позволяющий получить любой знак числа Пи без вычисления предыдущих, но в 16-ричной системе счисления. Все равно в десятичную переводить пришлось бы.
mad_god
11.09.2016 10:02вычислил, перевёл, записал в файл, перешёл к следующему знаку?
DmitrySpb79
11.09.2016 10:17Пи в 16-ричной системе счисления — это фактически и есть формула Плаффа, приведенная в статье.
Но мне что-то не приходит в голову, как перевести новый 16-ричный знак в десятичный, не пересчитывая в десятичном виде все число.
Код формулы Плаффа тоже есть в скрипте на питоне под спойлером в статье, кто хочет может поэкспериментировать.
Labunsky
11.09.2016 15:00А зачем вообще переводить? Как будто вы потом будете смотреть на этот миллион знаков :)
claygod
12.09.2016 09:12Для имплементации алгоритма Бэйли—Боруэйна—Плаффа лучше использовать модифицированную версию (её вывел автор в своей работе The BBP Algorithm for Pi):
avost
11.09.2016 13:47+1Вас, вероятно, не затруднит ознакомить нас с алгоритмом познакового переведения дробных шестнадцатиричных чисел в десятичные? ;)
mr_tron
11.09.2016 14:48https://gist.github.com/getify/fadc109f487067660c38 например таким?
DmitrySpb79
11.09.2016 15:14Какой же там стрим? В коде видно:
dec = dec + overflow; var whole = Math.floor(dec);
И обычная глобальная переменная. Т.е. от необходимости хранить результат в памяти (и делить/умножать) мы не избавляемся.mr_tron
11.09.2016 16:20Там вообще два разных кода от двух разных авторов. Причем первый жалуется что у него глючит и не работает. А вот вторый пишет решение.
Parcelapp
11.09.2016 12:05По поводу iOS и как работают программы в фоновом режиме. Когда программа перестает быть активной, её выполнение приостанавливается. Это можно предотвратить, если в этот момент создать UIBackgroundTask и зарегистрировать его в системе. Но этого хватит всего на несколько минут, так как подразумевается завершение какой-то определенной задачи.
Не совсем понял, почему для этого теста нельзя было оставить программу активной на всё время.DmitrySpb79
11.09.2016 14:49Да, я так и делал, конечно. Просто расчет был на то, что если программа будет работать долго, имеет смысл оставить ее в фоне.
Kenya-West
Реквестирую расчеты смартфонов на Windows!