Расчет Pi с несколькими потоками (без ускорения - что делать)

Question

Я пытаюсь вычислить pi с произвольной точностью на Python, используя одну из формул Рамануджана: http://en.wikipedia.org/wiki/Approximations_of_%CF%80#20th_century. Это в основном требует много факториалов и высокоточного плавающего числа.

Я использую несколько потоков для деления вычисления бесконечной серии, предоставляя каждому потоку все элементы, которые имеют определенный модуль при делении на количество потоков. Итак, если у вас есть 3 потока, сумма должна быть разделена следующим образом: Тема 1 ---> 1, 4, 7 ... members Тема 2 ----> 2, 5, 8 ... Тема 3 - ---> 3, 6, 9 ...

Вот мой код до сих пор:

from decimal import * 
from math  import sqrt, ceil 
from time  import clock 
from threading import * 
import argparse 

memoizedFactorials = [] 
memoizedFactorials.append(1) 
memoizedFactorials.append(1) 

class Accumulator: 
    def __init__(self): 
     self._sum = Decimal(0) 

    def accumulate(self, decimal): 
     self._sum += decimal 

    def sum(self): 
     return self._sum 

def factorial(k): 
    if k < 2: return 1 
    elif len(memoizedFactorials) <= k: 
     product = memoizedFactorials[ - 1 ] #last element 
     for i in range (len(memoizedFactorials), k+1): 
      product *= i; 
      memoizedFactorials.append(product) 

    return memoizedFactorials[ k ] 

class Worker(Thread): 
    def __init__(self, startIndex, step, precision, accumulator): 
     Thread.__init__(self, name = ("Thread - {0}".format(startIndex))) 
     self._startIndex = startIndex 
     self._step = step 
     self._precision = precision 
     self._accumulator = accumulator 

    def run(self): 
     sum = Decimal(0) 
     result = Decimal(1) 
     zero = Decimal(0) 

     delta = Decimal(1)/(Decimal(10)**self._precision + 1) 
     #print "Delta - {0}".format(delta) 
     i = self._startIndex 
     while(result - zero > delta): 
      numerator = Decimal(factorial(4 * i)*(1103 + 26390 * i)) 
      denominator = Decimal((factorial(i)**4)*(396**(4*i))) 
      result = numerator/denominator 
      print "Thread - {2} --- Iteration - {0:3} --->{1:3}".format(i, result, self._startIndex) 
      sum += result 
      i += self._step 

     self._accumulator.accumulate(sum) 
     print 

def main(args): 
    numberOfDigits = args.numberOfDigits; 
    getcontext().prec = numberOfDigits + 8 
    zero = Decimal(1)/Decimal(10**(numberOfDigits + 1)) 

    start = clock() 
    accumulator = Accumulator() 

    threadsCount = args.numberOfThreads; 
    threadPool = [] 
    for i in range(0, threadsCount): 
     worker = Worker(i, threadsCount, numberOfDigits, accumulator) 
     worker.start() 
     threadPool.append(worker) 

    for worker in threadPool: 
     worker.join() 

    sum = accumulator.sum(); 

    rootOfTwo = Decimal(2).sqrt() 

    result = Decimal(9801)/(Decimal(2) * rootOfTwo * sum) 
    end = clock(); 

    delta = end - start; 

    print result; 
    print ("Took it {0} second to finish".format(delta)) 

    #testing the results 
    #realPiFile = open("pi.txt"); 
    #myPi = str(result) 
    #realPi = realPiFile.read(len(myPi) - 1) 

    #if (myPi[:-1] != realPi): 
    # print "Answer not correct!" 
    # print "My pi - {0}".format(myPi) 
    # print "Real pi - {0}".format(realPi) 

if __name__ == '__main__': 
    parser = argparse.ArgumentParser(description = 'Calculate Pi at with arbitrary precision') 
    parser.add_argument('-p',   dest = 'numberOfDigits', default=20, type = int, help ='Number of digits in pi ') 
    parser.add_argument('-t', '--tasks', dest = 'numberOfThreads', default=1, type = int, help ='Number of tasks(threads)') 
    parser.add_argument('-o',   dest = 'outputFileName', type = str,    help ='Connect to VCS testing servers') 
    parser.add_argument('-q', '--quet', dest = 'quetMode'  , action='store_true', help ='Run in quet mode') 

    args = parser.parse_args() 

    print args 
    main(args) 
    a = raw_input("Press any key to continue...") 

Что касается меня thati имеет очень небольшое или никакого ускорение во время при использовании нескольких потоков. Например 1000 знаков числа пи: 1 темы -> 0,68 секунды 2 Темы -> 0,74 секунды 4 Тем -> 0,75 секунды 10 нитей -> 0,96 секунд

Есть ли у вас какие-либо идеи о том, как для уменьшения времени. Я вижу в диспетчере задач, что при использовании четырех потоков оба моих ядра попадают на 100%. Однако время похоже одно и то же.

PS: Это домашнее задание, поэтому я не могу использовать другую формулу. PSS: Я использую Python 2.7

Спасибо :)

Answer 1

Тем не ускорить процесс из-за GIL (Global Интерпретировать Lock). Используйте для этого задания multiprocessing. Его использование очень похоже на потоки.

Answer 2

Python имеет GIL (Global Interpreter Lock), который предотвращает одновременное выполнение одного или нескольких потоков кода python, то есть вы не можете получить ускорение задач, связанных с CPU, с использованием нескольких потоков. Вы должны использовать несколько процессов.

Answer 3

Вместо того, чтобы переборщить свой путь через серию и все эти неприятные факториалы, вы обязательно узнаете о алгоритме двоичного разбиения.

http://numbers.computation.free.fr/Constants/Algorithms/splitting.html

Этот парень уже сделал для вас работу. Он имеет реализации питоных двоичной структуры расщепления, приложенную к формуле Чудновского
http://www.craig-wood.com/nick/articles/pi-chudnovsky/

Основное преимуществом такой конструкции является то, что он исключает необходимость подразделений, факториалы и любых вычисления с плавающей точкой при расчете серии. Затем вы выполняете одно окончательное сверхмассивное деление между числителем и знаменателем. На самом деле я понятия не имею, как многопоточно, но это начало.