Вычисление 1000000 знаков числа Пи. На iPhone

  • Tutorial
Математика — весьма интересная и занимательная наука, особое место в которой занимает вычисление числа Pi. История его вычисления занимает более 2х тысячелетий, а точность вычисления колеблется от 256/81 в древнем Египте и 339/108 в Ведах, до Джамшида ал-Каши, вычислившего 16 знаков в 15м веке. Чего стоит хотя бы история Вильяма Шенкса, который потратил 20 лет на вычисление 700 знаков числа Пи, но уже потом выяснилось, что во второй части расчетов он ошибся… Но текст в общем-то не об этом, а об алгоритмах. Стало интересно, можно ли вычислить Пи на iPhone? И если да, то с какой точностью?


Можно сказать сразу — миллион не предел. Можно и больше. Подробности и реализация под катом.

Реализация вычислений


Даже животному семейства 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трлн знаков, правда и десктоп был не рядовым), то вряд ли его удастся побить на смартфоне. Да и подобной таблицы рекордов для смартфонов вроде еще никто не делал. Однако дело конечно не в рекорде — как можно видеть, подобные расчеты представляют собой достаточно интересную инженерную задачу, где остаются открытыми вопросы оптимизации и памяти, и скорости вычислений, и многопоточности. В общем, есть где «пошевелить мозгами», что как раз и наиболее интересно в программировании.
Share post

Comments 32

    +3
    Реквестирую расчеты смартфонов на Windows!
      +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 сек
        +1
        Спасибо, интересно.

        Но во-первых, вышеприведенный алгоритм был закодирован за полчаса, и вряд ли претендует на «the fastest windows program to compute pi» (у них там уже 4.3 версия).
        Во-вторых, the source code of PiFast is not available — проверить на iPhone все равно не получится.
          +1
          Может, тогда ради интереса попробуйте оптимизировать?
          Скачал первую попавшеюся программку для расчета Пи на свой андроид, девайс старый, ему почти 4 года, Snapdragon 410 — миллион знаков посчитал за 13.34 секунды. А ведь iphone SE в разы шустрее моего кирпича.
            0
            Да, допускаю что я что-то пропустил :) Попробую конечно, результат в статье дополню по появлении новых результатов.
              0
              Кстати, перепроверил код еще раз. Можно вынести вычисление 26680*640320*640320 за цикл, можно заменить 3 умножения на одну функцию степени. По прикидке, это даст выигрыш в 5% где-то. Можно запустить в 2 потока — получится допустим, не 13 часов а 6.

              Но так чтобы 13 секунд на старом смартфоне — странно. Тут по ссылке выше писали что 10секунд на Pentium-4 считалось, который явно помощнее будет. Может у них просто заранее подсчитанный файл в памяти лежит? :)

              Ну либо я не учитываю что-то, хз.
                0
                >10секунд на Pentium-4 считалось, который явно помощнее будет.
                Твои данные сильно устарели :)

                http://browser.primatelabs.com/v4/cpu/264152
                http://browser.primatelabs.com/ios-benchmarks
                Разница в 4 раза насколько я понимаю, и не в пользу 4 пня )
                  0
                  В общем нашел, там действительно используется другой алгоритм. Поправил результаты в тексте.
                    0
                    Что интересно, после генерации все число посмотреть невозможно, прога показывает только последние цифры.
                    А если захотеть посмотреть N-е число предупреждает что это будет очень долго.
                    Возможно какая-то хитрость там и есть.
                    Вот ссылка на гугл маркет link
                    Cкрин после расчетов под спойлером
                    Скрытый текст
                    image

                    И на этот раз даже еще быстрее посчитало :)
                  0
                  the fastest windows program to compute pi

                  Ну, это на 2003 год.

                  Там используется одно важное алгоритмическое решение: http://numbers.computation.free.fr/Constants/Algorithms/splitting.html

                +1
                Кстати вопрос. А где именно в Ведах есть значение числа Пи ну и вся прочая математика известная древним индийцам? Хотелось бы почитать оригинал переведенный на русский либо английский. Нагуглить ничего не получилось — вся поисковая выдача завалена философией адвайты и чем угодно но только не математикой.
                  0
                  В вики в истории числа Пи написано: «Ведийский текст «Шатапатха-брахмана» даёт pi как 339/108 ≈ 3,139»
                  Тексты этой книги на английском языке: www.sacred-texts.com/hin/sbr/index.htm.
                    0
                    Не смог удержаться, посчитал все варианты рационального приближения в разумных пределах по поиску числа 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/364913


                    3,6375309526024E-11%; 3126535/995207
                      +1
                      Вероятно, Вы хотели сказать «поиску числа Pi делением двух чисел, одно из которых простое».

                      Кстати, на Флибусте есть сочинения Архимеда в переводе на русский, в дежавю, где есть и «Измерение круга».
                      А здесь разъяснение метода, используемого Архимедом для вычисления Пи, вся цепочка рассуждений.
                  0
                  Я не читал Веды в оригинале при подготовке этой статьи, sorry :)
                  +4
                  Стало интересно, можно ли вычислить Пи на iPhone

                  Вот действительно! Тривиальный вопрос, вопрос возникающий сам собой!:)
                  Если серьезно, у меня возникает вопрос: зачем? Так, просто провести время?)
                    0
                    Раздел «Зачем это надо?» написан прямо в конце статьи :)
                    +1
                    Есть же вроде алгоритмы, которым пофиг на память, они лупят себе цифры и лупят, не оглядываясь назад
                    https://en.wikipedia.org/wiki/Pi#Spigot_algorithms

                    Хоть квинтиллион знаков на своём айфоне считайте
                      +1
                      Да, есть алгоритм позволяющий получить любой знак числа Пи без вычисления предыдущих, но в 16-ричной системе счисления. Все равно в десятичную переводить пришлось бы.
                        0
                        вычислил, перевёл, записал в файл, перешёл к следующему знаку?
                          0
                          Пи в 16-ричной системе счисления — это фактически и есть формула Плаффа, приведенная в статье.
                          image

                          Но мне что-то не приходит в голову, как перевести новый 16-ричный знак в десятичный, не пересчитывая в десятичном виде все число.

                          Код формулы Плаффа тоже есть в скрипте на питоне под спойлером в статье, кто хочет может поэкспериментировать.
                            0
                            А зачем вообще переводить? Как будто вы потом будете смотреть на этот миллион знаков :)
                              0
                              Можно вычислить 5 шестнадцатеричных знаков и перевести в 8 десятичных.
                                0

                                Нет. 5 шестнадцатиричных разрядов кодируют 16^5 различных значений, а 8 десятичных — 10^8, то есть так просто не получится.

                                0
                                Для имплементации алгоритма Бэйли—Боруэйна—Плаффа лучше использовать модифицированную версию (её вывел автор в своей работе The BBP Algorithm for Pi):

                                image
                                +1
                                Вас, вероятно, не затруднит ознакомить нас с алгоритмом познакового переведения дробных шестнадцатиричных чисел в десятичные? ;)
                                  0
                                  https://gist.github.com/getify/fadc109f487067660c38 например таким?
                                    0
                                    Какой же там стрим? В коде видно:
                                        dec = dec + overflow; 
                                        var whole = Math.floor(dec);
                                    


                                    И обычная глобальная переменная. Т.е. от необходимости хранить результат в памяти (и делить/умножать) мы не избавляемся.
                                      0
                                      Там вообще два разных кода от двух разных авторов. Причем первый жалуется что у него глючит и не работает. А вот вторый пишет решение.
                            0
                            По поводу iOS и как работают программы в фоновом режиме. Когда программа перестает быть активной, её выполнение приостанавливается. Это можно предотвратить, если в этот момент создать UIBackgroundTask и зарегистрировать его в системе. Но этого хватит всего на несколько минут, так как подразумевается завершение какой-то определенной задачи.

                            Не совсем понял, почему для этого теста нельзя было оставить программу активной на всё время.
                              0
                              Да, я так и делал, конечно. Просто расчет был на то, что если программа будет работать долго, имеет смысл оставить ее в фоне.

                            Only users with full accounts can post comments. Log in, please.