ก้าวแรก HPC #07: เตรียมเสบียงเลี้ยงตัว สู่โลกแห่งการประมวลผลแบบขนาน

by Supoj Choachaicharoenkul · Published February 5, 2015 · Updated November 28, 2014

เกริ่นนำ

ผมเริ่มเขียนบทความเรื่อง Apache Spark ปรากฏว่ามันเริ่มบวมใหญ่ เลยตัดสินใจแยกเนื้อหาที่ไม่เข้าพวกที่ต้องเกริ่นนำเป็นพื้นฐานออกมาเป็นบทความอีกบทความหนึ่ง กลายเป็นสะพานเชื่อมจากโลกการประมวลผลแบบเดี่ยวมาสู่การประมวลผลแบบขนานได้ ระหว่างการเขียนบทความนี้ก็บวมใหญ่อีก ผมเลยตัดเนื้อหาในส่วนที่ซับซ้อนไปไว้ในบทความชุดใหม่ “ก้าวสอง” ทั้งนี้เพื่อให้บทความชุดก้าวแรกนี้ยังคงง่ายสบายๆ นั่นเอง ดังนั้นบทความนี้จึงเหลือเท่าที่เห็น ไม่ง่ายและไม่ยากจนเกินไปนัก

ในบทความนี้ผมขอเน้นการวิเคราะห์โปรแกรมที่เราเขียนกันผ่านมา พิจารณาดูว่าโปรแกรมส่วนไหนควรปรับให้เป็นการประมวลผลแบบขนานและมีข้อควรระวังอะไรบ้าง เรามาเริ่มกันเลยครับ

**หมายเหตุ ในบทความนี้ผมใช้คำว่า “ตัวประมวลผล” แทนคำว่าคอร์ เพราะความหมายมันกว้างกว่า แต่ถ้าท่านคุ้นเคยกับกับว่าคอร์ก็ให้ทราบว่าเป็นเรื่องเดียวกัน

Dr. Gene Amdahl ผู้นิยามขอบเขตการประมวลผลแบบขนาน

ธรรมชาติการประมวลผลแบบขนานนั้น ในชั่วอายุของการทำงานของโปรแกรมนั้นไม่ใช่ว่าจะสามารถประมวลผลแบบขนานได้ตลอดเวลา บางเวลาโดยเฉพาะอย่างยิ่งตอนเริ่มและการสิ้นสุดการทำงานนั้นจะเป็นการประมวลผลแบบเดี่ยว เพื่อให้เห็นภาพผมเลยวาดให้ดูดังนี้

จากภาพจะเห็นได้ชัดเจนครับ การเริ่มทำงานนั้น จะเริ่มที่ตัวประมวลผลเดี่ยว จะนั้นเมื่อก็จะเปลี่ยนไปเป็นการทำงานแบบขนานในบางเวลา สลับกับการทำงานแบบเดี่ยวไปเรื่อยๆ จนจบการทำงานที่ตัวประมวลผลเดี่ยว เวลาที่ใช้ในการทำงานของตัวประมวลผลเดี่ยวนั้นคงที่ครับไม่เปลี่ยนแปลง แต่การประมวลผลในส่วนของขนานนั้น เวลาที่ใช้จะแปรผันจำนวนตัวประมวลผลแบบขนานที่เพิ่มเข้ามาในระบบ โดยทางทฤษฎีแล้วเรายิ่งเพิ่มหน่วยประมวลผลเข้าสู่ระบบการทำงานยิ่งเร็วขึ้น ดังภาพครับ

จากภาพเราจะเห็นว่าในส่วนที่เป็นสีชมพูด้านซ้ายและขวาทำงานด้วยเวลาคงที่ครับ ผิดกับสีน้ำเงินที่ยิ่งมีตัวประมวลผลมากยิ่งใช้เวลาลดลง เพื่อความสะดวกในการวิเคราะห์ ผมจึงเปลี่ยนจากการมองมิติเวลาจากค่าตัวเลขมาเป็นเปอร์เซ็นต์เปรียบเทียบ การทำเช่นนี้ต้องคิดที่ระบบทั้งหมดเป็นระบบที่ใช้ตัวประมวลผลเดี่ยว ยกตัวอย่างเช่น การใช้ตัวประมวลผลของโปรแกรมหนึ่ง 80% เป็นแบบตัวประมวลผลเดี่ยว อีก 20% สามารถใช้ตัวประมวลผลแบบขนานได้ ดังภาพ

เพื่อให้คำนวณง่าย ผมให้เป็น 5ถ้าเรากำหนดตัวแปร P เป็นอัตราเวลาที่สามารถประมวลผลแบบขนานได้ ในที่นี้คือ 50% หรือคะแนนเต็ม 1 ก็ได้ 0.5 นั่นเอง ส่วนเวลาที่ต้องประมวลผลแบบเดี่ยวนั้นก็ไม่จำเป็นต้องสร้างตัวแปรใหม่ให้วุ่นวายก็คือส่วนที่เหลือทั้งหมด มีค่าเท่ากับ (1 – P) นั่นเอง ในอีกมุมมองหนึ่ง เวลาทั้งหมดที่ใช้ในการประมวลผลรวมทั้งตัวประมวลเดี่ยวและขนานเป็น 1 หน่วย ถ้าเราลดเวลาในการทำงานเหลือครึ่งหนึ่ง นั่นคือเหลือ 0.5 คำถามคือระบบนี้เร็วขึ้นกี่เท่า ตอบได้ทันทีเลยใช่ไหมครับ ก็เร็วขึ้นสองเท่าอย่างแน่นอน ดังนั้น การแปลงจาก 0.5 ให้กลายเป็น 2 ได้นั้น ก็คือการเอา ไปหารด้วยหนึ่งครับ 1/1 ได้ 1 และ 1/0.5 ได้ 2 นั่นเอง ดังนั้นเราสามารถตั้งสมการอย่างได้ว่า

$S=\frac{1}{(1-P)+P}$

S คือความเร็วที่เร็วขึ้นหน่วยเป็นจำนวนเท่า เช่นถ้า 2 ก็คือเร็วขึ้นเป็น 2 เท่านั้นเอง สมการนี้ถ้ายุบรูปแล้วจะเห็นว่ากลายเป็น 1/1 ก็คือเร็วเท่าเดิมตลอดเวลา ไม่ต้องแปลกใจครับ ก็สำหรับตัวประมวลผลเดี่ยวไงครับ ไม่ว่าแยกส่วนการประมวลผลออกเป็นแบบเดี่ยวแบบขนาน แต่ความสามารถของตัวประมวลผลมีเพียงหน่วยเดียว มันก็ไม่เร็วขึ้นหรือช้าลงครับ ถือว่าเป็นฐานเวลานั้นเอง แต่ถ้าเรามีตัวประมวลผลแบบขนาน N ตัว เราจะปรับโปรแกรมตรงไหนครับ แน่นอนครับ เราต้องลดค่า P ลง โดยการนำมันไปหาร N นั่นเอง ส่วน (1 – P) นั้นมันก็คงเดิมเปลี่ยนไม่ได้ ผลลัพธ์ได้ดังนี้ครับ

$S(N)=\frac{1}{(1-P)+\frac{P}{N}}$

สมการนี้เองครับคิดค้นโดย Gene Amdahl ผู้เพิ่งฉลองครบรอบอายุ 92 ปี เมื่ออาทิตย์ที่แล้ว (วันหวยออก พ.ย. 57) รู้จักกันดีในชื่อว่า “กฏของแอมดาล” (Amdahl’s law) ซึ่งกำเนิดขึ้นจากบทความในปี 1967 เรื่อง Validity of the single processor approach to achieving large scale computing capabilities การเรียนเรื่องการประมวลผลแบบขนานต้องเรียนกฏนี้เปรียบเหมือนกับเป็น Hello, World ครับ กฏนี้บอกอะไรให้เรารู้ครับ เรามาลองวิเคราะห์เล่นๆ กัน สมมติตามตัวอย่างข้างบนเลยครับ โปรแกรมของเราสามารถประมวลผลโดยใช้ตัวประมวลผลเดี่ยวใช้เวลา 1 วัน โปรแกรมนี้มีส่วนเวลาที่สามารถประมวลผลแบบขนานได้ครึ่งหนึ่งและอีกครึ่งต้องใช้ตัวประมวลผลเดี่ยว ถามว่า ถ้าผมมีโอกาสใช้เครื่องเทียนเหอ-2 ที่เป็น Supercomputer ที่เร็วที่สุดในโลก ณ วันที่ผมเขียนบทความนี้ เป็นเครื่องที่มีหน่วยประมวลผลหลายล้านตัว โปรแกรมของผมจะใช้เวลาเหลือเท่าไหร่ เพื่อหาคำตอบผมก็เลยแทนค่าลงไปในสมการได้ดังนี้ครับ

$S({\infty})=\frac{1}{(1-0.5)+\frac{0.5}{\infty }}$

ผมจำไม่ได้แล้วว่าเทียนเหอ-2 ของจีนนั้นมีตัวประมวลผลกี่ตัว ผมว่าเยอะเลยแทนค่าเป็นอนันต์ไปเลย เมื่ออนันต์ใช้เป็นตัวหาร มันก็เลยฉุดให้พจน์ P/N เป็น 0 หมายความว่าเวลาที่ใช้ในส่วนของการประมวลผลแบบขนานเป็น 0 หมายความว่าเร็วจนไม่กินเวลาเลยนั่นเอง แต่พจน์ (1-P) อย่างไรก็ไม่มีใครไปแต่ต้องมันได้ มันจึงยังคงอยู่และทำให้ได้ผลลัพธ์ 1/(0.5) ซึ่งก็คือ 2 เท่านั่นเอง น่าตกใจไหมครับ โปรแกรมที่ครึ่งหนึ่งทำงานแบบขนานได้ อีกครึ่งหนึ่งต้องเป็นแบบเดี่ยวนั้น ต่อให้ใช้เครื่องที่เร็วที่สุดในโลกก็สามารถลดการทำงานจาก 1 วันเหลือได้เพียงแค่ครึ่งวันเท่านั้น ผมถึงบอกไงว่า อัลกอริทึมนั่นสำคัญกว่า Hardware เราต้องเพิ่มค่า P ในโปรแกรมของเราให้ได้ ค่า P ยิ่งดี การทำงานยิ่งเร็ว

ต่อไปครับ ถ้าผมสามารถตัดส่วนของการทำงานตัวประมวลผลเดี่ยวให้กลายเป็นศูนย์ (ในโลกความเป็นจริงคงเป็นไปไม่ได้) เหลือเพียงส่วนการประมวลผลแบบขนาน 1 / (P/N) ทำให้อยู่ในรูปอย่างง่ายโดยการพลิกกลับจะได้ N/P และ P เป็น 1 ดังนั้นจำนวนเท่าที่ได้ขึ้นอยู่กับ N เช่น N = 5 ก็จะได้ความเร็วเป็น 5 เท่า ตามที่ฝันอยากให้เป็น แต่มันเร็วจริงหรือ ลองคิดในมุมนี้ดูครับ สมมติว่าเรามีงานชิ้นหนึ่งใช้เวลาทำงาน 100 วันบนตัวประมวลผลเดี่ยว ถ้าเราเพิ่มตัวประมวลผลอีกตัวจะทำให้วันลดลงครึ่งหนึ่ง เหลือเพียง 50 วัน ซึ่งเราก็พอใจ แต่มาถึงวันหนึ่งเมื่อเราอยากให้มันเร็วขึ้นอีกเท่าหนึ่งจากเดิม 50 วัน ให้เหลือ 25 วัน เราเพิ่มหน่วยประมวลผลเพียงตัวเดียวไม่ได้แล้วครับ ต้องเพิ่มอีกสองตัว จากสองต้องเป็นสี่ ทุกๆ เท่าที่ได้มา ต้องเพิ่มหน่วยประมวลผลอีกเป็นเท่าตัวเช่นเดียวกัน ด้วยตรรกะนี้ ถ้าปัจจุบัน เราใช้หน่วยประมวลผล 1,000 ตัว ทำงานเสร็จใช้เวลา 1 วัน ถ้าอยากให้เหลือครึ่งวัน ต้องเพิ่มอีกหน่วยประมวลผลอีกเท่าหนึ่งคือ 1,000 ตัวครับ เริ่มมองเห็นพาราด๊อกซ์ตัวนี้หรือยังครับ

ค่าที่ได้จากกฏของแอมดาลกับในโลกของความเป็นจริงมันต่างกันนะครับ เป็นไปได้ยากมากที่เมื่อเราจับเวลาทำงานแล้วผลลัพธ์ใกล้เคียงกับค่าที่ได้จากสูตร ทั้งนี้เพราะในการประมวลผลแบบขนานนั้นต้องเสียเวลาพอสมควร ตั้งแต่การติดต่อเริ่มต้น กันแลกเปลี่ยนข้อมูลต่างๆ เป็นต้น ดังนั้นกฏของแอมดาลนี้จึงใช้สำหรับนิยามผลลัพธ์ในกรณีอุดมคติที่ดีที่สุดเท่านั้น ซึ่งก็ทำให้เรารู้ว่าขอบเขตประสิทธิภาพสูงสุดนั้นมันอยู่ตรงไหน

กฏของอู๋

ในบทความต่อๆ ไปเราจะเรียนรู้ถึง framework ในการประมวลผลแบบขนานหลายตัว ซึ่งผมอยากจะวัดประสิทธิภาพว่าวิธีไหนเร็วกว่ากัน ซึ่งความเร็วนั้นแปรผันตามจำนวนหน่วยประมวลผลอีกต่างหาก กฏของแอมดาลไม่สามารถตอบโจทย์นี้ได้ ผมเลยคิดสมการเพื่อประเมินประสิทธิภาพขึ้นมาเอง (อาจซ้ำเพราะมีคนเคยคิดมาก่อนแล้ว แต่ด้วยความอ่อนด้อยของผมเองทำให้ผมไม่รู้จัก) ผมตั้งชื่อมันว่า กฏของอู๋ (ไม่ต้องถามผมนะครับว่าอู๋คืออะไร ผมไม่บอกท่านหรอก)

กำหนดให้

$T_{1}$ คือเวลาที่ใช้ในการประมวลผลทั้งหมดเมื่อใช้ตัวประมวลผลเดี่ยว
$T_{N}$ คือเวลาที่ใช้การประมวลผลทั้งหมดเมื่อใช้งานตัวประมวลผล N ตัว

ทั้งสองค่าได้มาจากการจับเวลาจริงทั้งคู่ครับ เรานิยากฏของอู๋นิยามได้โดย

$\frac{N(T_{1}-T_{N})}{T_{1}(N-1)}$

ที่มาที่ไปดูได้จากกระดานดำเลยครับ

ดูที่มาของตารางก่อนครับ ตามกฏของแอมดาลแล้ว จากเวลา $T_{1}$ ถ้าเราเพิ่มหน่วยประมวลผล N ตัวเข้าไป เวลาที่ดีที่สุดที่ลดได้จะเหลือ $\frac{T_{1}}{N}$ ถ้าเมื่อจับเวลาจริงแล้วได้ตามนี้ถือว่า 100% ผมจึงกำหนดให้เป็น 1 กรณีที่แย่มาก คือใส่ตัวประมวลผลไป N ตัวแต่เมื่อจับเวลาแล้วได้เวลาเท่ากับตัวประมวลผลตัวเดียว แบบนี้ผมกำหนดให้ได้ 0% แต่ถ้าเกินนี้ก็ติดลบแล้วครับ ซึ่งหมายความว่าแย่สุดๆ อย่าใช้เลยครับตัวประมวลหลายตัว เพราะทำเวลาได้แย่กว่าตัวประมวลผลเดี่ยวเสียอีก ข้อมูลนี้วาดเป็นกราฟได้ตามบนกระดานดำครับ

$T_{N}$ คือค่าจริงที่เราจับเวลาเมื่อใช้ตัวประมวลผลหลายตัว ซึ่งเป็นจุดใดจุดหนึ่งบนแกน X ที่อยู่ตั้งแต่ $\frac{T_{1}}{N}$ ขึ้นไป สิ่งที่เราต้องการก็คือเราต้องหาค่าที่ตัดกับแกน Y ตามความสัมพันธ์แบบเส้นตรงตามเส้นสีฟ้านั่นเอง ผมเลือกใช้สมการ Interpolation ดังสมการสีชมพู แทนค่าตรงๆ ก็จะได้สมการเส้นสีฟ้าครับ และเมื่อจัดรูปใหม่แล้วจะเหลือ

$\frac{N(T_{1}-T_{N})}{T_{1}(N-1)}$

นี่แหละครับกฎของอู๋ ถ้าใครใล่ตามที่มาที่ผมอธิบายก็คงเข้าใจว่ากฏนี้คำนวณหาค่าอะไร แต่ถ้ายังไม่ทราบผมอธิบายอย่างนี้ครับ กฏข้อนี้เอาไว้วัดศักยภาพในการประมวลผลแบบขนานของทั้ง Framework และโปรแกรมที่เราเขียนเองครับ เมื่อใส่ค่าสามค่าตามพารามิเตอร์เสร็จเรียบร้อยแล้ว สมมติว่า Framework A ได้ค่า 0.8 ส่วน Framework B นั้นได้ค่า 0.7 อู๋นั้นทำให้เราใช้ฐานเดียวกันในการเปรียบเทียบ แม้ว่าจำนวนหน่วยประมวลผลจะไม่เท่ากันก็ตาม จากตัวอย่างนั้นบอกได้อย่างชัดเจนว่า Framework A ที่มีค่าอู๋สูงกว่านั้น มีศักยภาพในการประมวลผลแบบขนานสูงกว่านั่นเอง

กลับมาที่อัลกอริทึมการหา Bernoulli Number ของ Dr. Harvey

จากทฤษฎีมาสู่การปฏิบัติบ้าง ผมอยากหาค่า P ของโปรแกรม Bernoulli Number ที่ใช้อัลกอริทึมของ Dr. Harvey ซึ่งเป็นที่ทราบกันว่าอัลกอริทึมของ Dr. Harvey นั้นจุดเด่นก็คือการการกระจายงานออกไปให้แก่ตัวประมวลผลทุกตัวเท่าที่มีได้ ว่าแต่ว่าส่วนไหนของโปรแกรมหละที่สามารถกระจายออกได้ ลองดูส่วนของโปรแกรมข้างล่างครับ

#include <iostream>
#include <vector>
#include <cmath>
#include <gmpxx.h>
#include <tuple>
#include <stack>
#include <utility>

using namespace std;

class PrimeTable
{
public:
    PrimeTable(const long &size) : _size {size}, _table (size, true) {
        _table[0] = _table[1] = false;
        const long limit = (long)sqrt(size);
        for (long i=2; i<=limit; i++) {
            if (_table[i] == false) continue;
            for (long r=i+i; r<=size; r+=i) _table[r] = false;
        }
    }

    long nextPrime(long pos) {
        for (long i=pos+1; i<=_size; i++) {
            if (_table[i] == true) return i;
        }
        return -1;
    }
private:
    long _size;
    std::vector<bool> _table;
};

auto computeDk(const int &k, PrimeTable& primeTable) -> mpz_class
{
    long p {2};
    mpz_class dk {1};
    while (p != -1) {
        if (k % (p-1) == 0) dk *= p;
        p = primeTable.nextPrime(p);
    }
    return std::move(dk);
}

auto norm(mpz_class b, mpz_class p) -> mpz_class
{
    while (true) {
        if (b < 0) b += p;
        else if (b > p) b -= p;
        else break;
    }
    return b;
}

auto computePowerMod(const mpz_class &a, const long &k, const mpz_class &m) -> mpz_class
{
    int index = log2(k);
    mpz_class powmod = 1, powa = a, pow2 = 1;

    for (int i=0; i<=index; i++) {
        if ( (k & pow2) != 0) powmod *= powa;
        powa = (powa * powa) % m;
        pow2 <<= 1;
    }
    return norm(powmod % m, m);
}

auto computeInvertMod(const mpz_class &n, mpz_class p) -> mpz_class
{
    stack<tuple<mpz_class, mpz_class, mpz_class>> v;
    mpz_class a = p;
    mpz_class b = n;
    if (n > p) {
        a = n;
        b = p;
    }
    mpz_class d = a / b;
    mpz_class r = a % b;

    while (r > 1) {
        v.push(make_tuple(a, b, -d));
        a = b;
        b = r;
        d = a / b;
        r = a % b;
    }
    mpz_class m1 = 1, m2 = -d;
    mpz_class aa = a, bb = b;

    while (!v.empty()) {
        auto t = v.top();
        v.pop();
        a = get<0>(t);
        b = get<1>(t);
        d = get<2>(t);
        m1 += (m2 * d);
        bb = a;
        swap(m1, m2);
        swap(aa, bb);
    }
    mpz_class rr = (n == aa)? m1 : m2;
    return norm(rr, p);
}

auto computeOrderEp(const long &a, const long &p) -> long
{
    for (long k=1; k<p; k++) {
        if (computePowerMod(a, k, p) == 1) return k;
    }
    throw "computeOrderEp error";
}

auto computePrimitiveRoot(const long &p) -> long
{
    if (p == 2) return 1;
    for (int g=2; g<p; g++) {
        if (computeOrderEp(g, p) == (p - 1)) return g;
    }
    throw "computePrimitiveRoot error";
}

auto computeBkModP(const long &p, const long &k) -> mpz_class
{
    if (k == 0) return 1;
    if (k == 1) return (p == 2)? -1 : (p-1)/2;
    if (k &  1) return 0;
    if (p <= 3) return -1;

    long m = k % (p-1);
    if (m == 0) return -1;

    mpz_class g = computePrimitiveRoot(p);
    mpz_class r = computePowerMod(g, k-1, p);
    mpz_class u = (g + ((g % 2 == 1)? 0 : p) - 1) / 2;
    mpz_class S = 0, X = 1, Y = r;


    mpz_class hp = (p-1)/2, q, h, t;
    for (long i=1; i<=hp; i++) {
        q = norm( (g*X)/p, p);
        h = norm( (q-u)%p, p);
        t = norm( (h*Y)%p, p);
        S = norm( (S-t)%p, p);
        X = norm( (g*X)%p, p);
        Y = norm( (r*Y)%p, p);
    }
    mpz_class ans = computePowerMod(g, k, p);

    ans = computeInvertMod(p+1-ans, p);

    ans = norm( (S * ans) % p, p);
    ans = norm( (2 * ans) % p, p);
    ans = norm( (k * ans) % p, p);

    return ans;
}

auto congruent(const mpz_class &a, const mpz_class &b, const mpz_class &m) -> mpz_class
{
    if (a == 1 && b == 1) return mpz_class {1};
    mpz_class inv = computeInvertMod(a, m);
    return (b * inv) % m;
}

auto oldcongruent(const mpz_class &a, const mpz_class &b, const mpz_class &m) -> mpz_class
{
    mpz_class g;
    mpz_gcd(g.get_mpz_t(), a.get_mpz_t(), m.get_mpz_t());
    if (b % g != 0) throw "congruent error";
    mpz_class a_ = a / g;
    mpz_class b_ = b / g;
    mpz_class m_ = m / g;

    while (true) {
        if (b_ % a_ == 0) break;
        b_ = b_ + m_;
    }
    b_ = b_ / a_;
    return b_;
}

auto computeCRT(vector<tuple<mpz_class, long>> &residue) -> mpz_class
{
    mpz_class mul_m = 1;
    for (auto top : residue) {
        mul_m *= get<1>(top);
    }

    mpz_class z = 0, M, X, b, m;
    for (auto top : residue) {
        b = get<0>(top);
        m = get<1>(top);
        M = mul_m / m;
        X = congruent(M, 1, m);
        z += M * X * b;
    }
    while (z > 0) {
        z -= mul_m;
    }
    return z + mul_m;
}

auto B(long k) -> mpq_class
{
    mpq_class bern_base[] {mpq_class {1, 1}, mpq_class {1, 2}, mpq_class {1, 6} };
    if (k < 3) return bern_base[k];

    if (k & 1) return mpq_class {0, 1};
    long Y = long(ceil((k+0.5) * log2(k)));
    if (Y < 37) Y = 37;
    PrimeTable primeTable(Y);
    mpz_class dk = computeDk(k, primeTable);
    long beta = long(ceil( (k+0.5) * log2(k) - 4.094 * k + 2.470 + log2(dk.get_d())));
    long p = 3;
    mpz_class M_ {1};
    mpz_class twoPowerBetaPlusOne;
    mpz_ui_pow_ui(twoPowerBetaPlusOne.get_mpz_t(), 2, beta+1);

    while (M_ < twoPowerBetaPlusOne) {
        p = primeTable.nextPrime(p);
        if (k % (p-1) != 0) {
            M_ *= p;
        }
    }

    long X = p;
    mpz_class M {1};
    p = 2;
    vector <tuple<mpz_class, long>> rp;

    while (p <= X) {
        if (k % (p-1) != 0) {
            rp.push_back(make_tuple(computeBkModP(p, k), p));
            M *= p;
        }
        p = primeTable.nextPrime(p);
    }

    mpz_class R = computeCRT(rp);
    mpz_class N_ = norm((dk * R) % M, M);
    mpz_class nk = (k % 4 == 2)? N_ : N_ - M;
    return mpq_class {nk, dk};
}

auto main(int argc, char *argv[]) -> int
{
    if (argc != 2) {
        cout << "usage: " << argv[0] << " m" << endl;
        return 0;
    }
    cout << "B(" << argv[1] << ") = " << B(atoi(argv[1])) << endl;
    return 0;
}

226

227

228

229

230

231

232

233

234

235

236

237

long X = p;

mpz_class M {1};

p = 2;

vector <tuple<mpz_class, long>> rp;

while (p <= X) {

if (k % (p-1) != 0) {

rp.push_back(make_tuple(computeBkModP(p, k), p));

M *= p;

}

p = primeTable.nextPrime(p);

}

ผมเปลี่ยนมาใช้ C++ บ้าง เพราะในบทความที่ผ่านมาเน้นแต่ Python เปลี่ยนเป็น C+ บ้างจะได้มีทางเลือกครับ ส่วนของโปรแกรมที่เห็นนี้อยู่ในฟังก์ชัน B() ซึ่งเป็นฟังก์ชันหลักในการคำนวณนั่นเอง ผมตัดมาจากบทความก่อนหน้า HPCThai/introHPC/06/bern_mod_v2.cpp อัลกอริทึมนี้โดยรวมอาจจะซับซ้อน แต่ส่วนที่ตัดออกมาให้ท่านดูนั้น เข้าใจไม่ยากลองไล่ตามดู ลองพิจารณาการวนรอบจากส่วนของโปรแกรมข้างต้นดู แต่ละรอบจะได้จำนวนเฉพาะใหม่ๆ (ค่า p) ไล่ขึ้นมาตั้งแต่ 2, 3, 5, 7, 11, … แต่ก็ไม่ใช่ค่าจำนวนเฉพาะทุกตัวสามารถนำเอาไปใช้งานได้ ต้องผ่านเงื่อนไข k หารด้วย (p – 1) ต้องไม่ลงตัวเท่านั้น จากนั้นจึงนำค่า p ไปคำนวณค่า computeBkModP(p, k) คำนวณเสร็จ ก็เก็บผลลัพธ์ลงใน vector

สิ่งที่เห็นชัดก็คือการเรียกใช้ฟังก์ชัน computeBkModP(p, k) นั้น ค่า k คือค่าโจทย์ตัวเลข Bernoulli ที่เราต้องการหา (กรณีนี้คือ 1,000) การหา computeBkModP(2, 1000) และ computeBkModP(3, 1000) หรือ ค่า p ใดๆ นั้นสามารถหาค่าได้พร้อมกันเพราะอิสระต่อกัน ดังนั้นจึงเหมาะอย่างยิ่งที่นำมาประมวลผลแบบขนาน ส่วนของโปรแกรมนี้ยังไม่ดีครับ เพราะค่า p นั้นคำนวณใหม่ทุกครั้งเมื่อเรียก computeBkModP(p, k) การหาค่า p นั้นเป็นส่วนของการประมวลผลเดี่ยวครับ ผมจึงปรับเอาการหาค่า p รวบยอดที่เดียวก่อน แล้วเอาค่า p ทั้งหมดที่ใช้งานบรรจุลงบน Queue จากนั้นใช้ Queue เป็นตัวแจกงาน สร้างเป็นการวนรอบแจกงาน ดังนี้ครับ

#include <iostream>
#include <vector>
#include <cmath>
#include <gmpxx.h>
#include <tuple>
#include <stack>
#include <utility>
#include <deque>
#include <chrono>

using namespace std;

class PrimeTable
{
public:
    PrimeTable(const long &size) : _size {size}, _table (size, true) {
        _table[0] = _table[1] = false;
        const long limit = (long)sqrt(size);
        for (long i=2; i<=limit; i++) {
            if (_table[i] == false) continue;
            for (long r=i+i; r<=size; r+=i) _table[r] = false;
        }
    }

    long nextPrime(long pos) {
        for (long i=pos+1; i<=_size; i++) {
            if (_table[i] == true) return i;
        }
        return -1;
    }
private:
    long _size;
    std::vector<bool> _table;
};

auto computeDk(const int &k, PrimeTable& primeTable) -> mpz_class
{
    long p {2};
    mpz_class dk {1};
    while (p != -1) {
        if (k % (p-1) == 0) dk *= p;
        p = primeTable.nextPrime(p);
    }
    return std::move(dk);
}

auto norm(mpz_class b, mpz_class p) -> mpz_class
{
    while (true) {
        if (b < 0) b += p;
        else if (b > p) b -= p;
        else break;
    }
    return b;
}

auto computePowerMod(const mpz_class &a, const long &k, const mpz_class &m) -> mpz_class
{
    int index = log2(k);
    mpz_class powmod = 1, powa = a, pow2 = 1;

    for (int i=0; i<=index; i++) {
        if ( (k & pow2) != 0) powmod *= powa;
        powa = (powa * powa) % m;
        pow2 <<= 1;
    }
    return norm(powmod % m, m);
}

auto computeInvertMod(const mpz_class &n, mpz_class p) -> mpz_class
{
    stack<tuple<mpz_class, mpz_class, mpz_class>> v;
    mpz_class a = p;
    mpz_class b = n;
    if (n > p) {
        a = n;
        b = p;
    }
    mpz_class d = a / b;
    mpz_class r = a % b;

    while (r > 1) {
        v.push(make_tuple(a, b, -d));
        a = b;
        b = r;
        d = a / b;
        r = a % b;
    }
    mpz_class m1 = 1, m2 = -d;
    mpz_class aa = a, bb = b;

    while (!v.empty()) {
        auto t = v.top();
        v.pop();
        a = get<0>(t);
        b = get<1>(t);
        d = get<2>(t);
        m1 += (m2 * d);
        bb = a;
        swap(m1, m2);
        swap(aa, bb);
    }
    mpz_class rr = (n == aa)? m1 : m2;
    return norm(rr, p);
}

auto computeOrderEp(const long &a, const long &p) -> long
{
    for (long k=1; k<p; k++) {
        if (computePowerMod(a, k, p) == 1) return k;
    }
    throw "computeOrderEp error";
}

auto computePrimitiveRoot(const long &p) -> long
{
    if (p == 2) return 1;
    for (int g=2; g<p; g++) {
        if (computeOrderEp(g, p) == (p - 1)) return g;
    }
    throw "computePrimitiveRoot error";
}

auto computeBkModP(const long &p, const long &k) -> mpz_class
{
    if (k == 0) return 1;
    if (k == 1) return (p == 2)? -1 : (p-1)/2;
    if (k &  1) return 0;
    if (p <= 3) return -1;

    long m = k % (p-1);
    if (m == 0) return -1;

    mpz_class g = computePrimitiveRoot(p);
    mpz_class r = computePowerMod(g, k-1, p);
    mpz_class u = (g + ((g % 2 == 1)? 0 : p) - 1) / 2;
    mpz_class S = 0, X = 1, Y = r;


    mpz_class hp = (p-1)/2, q, h, t;
    for (long i=1; i<=hp; i++) {
        q = norm( (g*X)/p, p);
        h = norm( (q-u)%p, p);
        t = norm( (h*Y)%p, p);
        S = norm( (S-t)%p, p);
        X = norm( (g*X)%p, p);
        Y = norm( (r*Y)%p, p);
    }
    mpz_class ans = computePowerMod(g, k, p);

    ans = computeInvertMod(p+1-ans, p);

    ans = norm( (S * ans) % p, p);
    ans = norm( (2 * ans) % p, p);
    ans = norm( (k * ans) % p, p);

    return ans;
}

auto congruent(const mpz_class &a, const mpz_class &b, const mpz_class &m) -> mpz_class
{
    if (a == 1 && b == 1) return mpz_class {1};
    mpz_class inv = computeInvertMod(a, m);
    return (b * inv) % m;
}

auto computeCRT(vector<tuple<mpz_class, long>> &residue) -> mpz_class
{
    mpz_class mul_m = 1;
    for (auto top : residue) {
        mul_m *= get<1>(top);
    }

    mpz_class z = 0, M, X, b, m;
    for (auto top : residue) {
        b = get<0>(top);
        m = get<1>(top);
        M = mul_m / m;
        X = congruent(M, 1, m);
        z += M * X * b;
    }
    while (z > 0) {
        z -= mul_m;
    }
    return z + mul_m;
}

using crt_t = tuple<mpz_class, long>;
using primeList_t = deque<long>;

auto distribute(long k, primeList_t primeList) -> vector<crt_t>
{
    vector<crt_t> rp;
    auto p_stime = chrono::high_resolution_clock::now();
    while (!primeList.empty()) {
        long pp = primeList.front();
        primeList.pop_front();
        crt_t tt = make_tuple(computeBkModP(pp,k), pp);
        rp.push_back(tt);
    }
    auto p_etime = chrono::high_resolution_clock::now();
    cout << "Parallel Time used: " << chrono::duration_cast<chrono::milliseconds>(p_etime - p_stime).count() << " msecs" << endl;
    return rp;
}

auto B(long k) -> mpq_class
{
    mpq_class bern_base[] {mpq_class {1, 1}, mpq_class {1, 2}, mpq_class {1, 6} };
    if (k < 3) return bern_base[k];

    if (k & 1) return mpq_class {0, 1};
    long Y = long(ceil((k+0.5) * log2(k)));
    if (Y < 37) Y = 37;
    PrimeTable primeTable(Y);
    mpz_class dk = computeDk(k, primeTable);
    long beta = long(ceil( (k+0.5) * log2(k) - 4.094 * k + 2.470 + log2(dk.get_d())));
    long p = 3;
    mpz_class M_ {1};
    mpz_class twoPowerBetaPlusOne;
    mpz_ui_pow_ui(twoPowerBetaPlusOne.get_mpz_t(), 2, beta+1);

    while (M_ < twoPowerBetaPlusOne) {
        p = primeTable.nextPrime(p);
        if (k % (p-1) != 0) {
            M_ *= p;
        }
    }

    long X = p;
    mpz_class M {1};
    p = 2;

    primeList_t primeList;

    while (p <= X) {
        if (k % (p-1) != 0) {
            primeList.push_back(p);
            M *= p;
        }
        p = primeTable.nextPrime(p);
    }
    auto rp = distribute(k, primeList);

    mpz_class R = computeCRT(rp);
    mpz_class N_ = norm((dk * R) % M, M);
    mpz_class nk = (k % 4 == 2)? N_ : N_ - M;
    return mpq_class {nk, dk};
}

auto main(int argc, char *argv[]) -> int
{
    if (argc != 2) {
        cout << "usage: " << argv[0] << " m" << endl;
        return 0;
    }
    auto t_stime = chrono::high_resolution_clock::now();
    cout << "B(" << argv[1] << ") = " << B(atoi(argv[1])) << endl;
    auto t_etime = chrono::high_resolution_clock::now();
    cout << "Total Time used: " << chrono::duration_cast<chrono::milliseconds>(t_etime - t_stime).count() << " msecs" << endl;
    return 0;
}

229

230

231

232

233

234

235

236

237

238

239

240

241

242

long X = p;

mpz_class M {1};

p = 2;

primeList_t primeList;

while (p <= X) {

if (k % (p-1) != 0) {

primeList.push_back(p);

M *= p;

}

p = primeTable.nextPrime(p);

}

auto rp = distribute(k, primeList);

จะสังเกตว่าผมสร้างฟังก์ชัน distribute() ขึ้นมา เพื่อคำนวณค่า computeBkModP(p, k) โดยเฉพาะ ในอนาคตเมื่อเราเรียนรู้การเขียนโปรแกรมแบบขนาน เราจะแก้แค่ฟังก์ชันนี้เพียงฟังก์ชันเดียวเท่านั้นครับ เนื้อหาของฟังก์ชัน distribute() มีรายละเอียดดังนี้ครับ

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="utf-8">
  <link rel="dns-prefetch" href="https://github.githubassets.com">
  <link rel="dns-prefetch" href="https://avatars0.githubusercontent.com">
  <link rel="dns-prefetch" href="https://avatars1.githubusercontent.com">
  <link rel="dns-prefetch" href="https://avatars2.githubusercontent.com">
  <link rel="dns-prefetch" href="https://avatars3.githubusercontent.com">
  <link rel="dns-prefetch" href="https://github-cloud.s3.amazonaws.com">
  <link rel="dns-prefetch" href="https://user-images.githubusercontent.com/">



  <link crossorigin="anonymous" media="all" integrity="sha512-veKG2ootplNGLwNEW5It4+lJXwpdOVR1Ry4MBDNvdgL6OgBkiAXaZAZnIKkw6sIygnfGqQhR5q7UdS1llqd6/g==" rel="stylesheet" href="https://github.githubassets.com/assets/frameworks-bde286da8a2da653462f03445b922de3.css" />
  <link crossorigin="anonymous" media="all" integrity="sha512-SIdH/u1H0WymCGxSKvv9kCVqCpgpL7GuBc5dVtA1UApgTky3oIA6YLFIzjYiN7fjVk/vZcu/QX5sobbu5BCkmg==" rel="stylesheet" href="https://github.githubassets.com/assets/site-488747feed47d16ca6086c522afbfd90.css" />
    <link crossorigin="anonymous" media="all" integrity="sha512-oskjA1HEwZq5HoCKRZWoUhAoBLeFfX5lCdbSsUB2Bkemb1XNH7rXMMrxJ+YTQMunfXVXY1eRDeEyL0527syBBw==" rel="stylesheet" href="https://github.githubassets.com/assets/github-a2c9230351c4c19ab91e808a4595a852.css" />
    
    
    
    


  <meta name="viewport" content="width=device-width">
  
  <title>HPCThai/bern_amdahl.cpp at master · hpc-thai/HPCThai · GitHub</title>
    <meta name="description" content="http://www.hpc-thai.com  source code. Contribute to hpc-thai/HPCThai development by creating an account on GitHub.">
    <link rel="search" type="application/opensearchdescription+xml" href="/opensearch.xml" title="GitHub">
  <link rel="fluid-icon" href="https://github.com/fluidicon.png" title="GitHub">
  <meta property="fb:app_id" content="1401488693436528">

    <meta name="twitter:image:src" content="https://avatars3.githubusercontent.com/u/9413197?s=400&v=4" /><meta name="twitter:site" content="@github" /><meta name="twitter:card" content="summary" /><meta name="twitter:title" content="hpc-thai/HPCThai" /><meta name="twitter:description" content="http://www.hpc-thai.com  source code. Contribute to hpc-thai/HPCThai development by creating an account on GitHub." />
    <meta property="og:image" content="https://avatars3.githubusercontent.com/u/9413197?s=400&v=4" /><meta property="og:site_name" content="GitHub" /><meta property="og:type" content="object" /><meta property="og:title" content="hpc-thai/HPCThai" /><meta property="og:url" content="https://github.com/hpc-thai/HPCThai" /><meta property="og:description" content="http://www.hpc-thai.com  source code. Contribute to hpc-thai/HPCThai development by creating an account on GitHub." />

  <link rel="assets" href="https://github.githubassets.com/">
  

  <meta name="request-id" content="CC18:1ABD:DD6AF:138417:5ED989BD" data-pjax-transient="true"/><meta name="html-safe-nonce" content="54ff992057c586034396d5ffcbb98a70b87088eb" data-pjax-transient="true"/><meta name="visitor-payload" content="eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJDQzE4OjFBQkQ6REQ2QUY6MTM4NDE3OjVFRDk4OUJEIiwidmlzaXRvcl9pZCI6Ijc4NDkxODI0NjQ1MTg0OTA1NTciLCJyZWdpb25fZWRnZSI6ImFwLXNvdXRoZWFzdC0xIiwicmVnaW9uX3JlbmRlciI6ImFwLXNvdXRoZWFzdC0xIn0=" data-pjax-transient="true"/><meta name="visitor-hmac" content="a54616c12d51da35d94f8a625f2153de8836d67ff99c62b63c92b388939a3345" data-pjax-transient="true"/>



  <meta name="github-keyboard-shortcuts" content="repository,source-code" data-pjax-transient="true" />

  

  <meta name="selected-link" value="repo_source" data-pjax-transient>

    <meta name="google-site-verification" content="c1kuD-K2HIVF635lypcsWPoD4kilo5-jA_wBFyT4uMY">
  <meta name="google-site-verification" content="KT5gs8h0wvaagLKAVWq8bbeNwnZZK1r1XQysX3xurLU">
  <meta name="google-site-verification" content="ZzhVyEFwb7w3e0-uOTltm8Jsck2F5StVihD0exw2fsA">
  <meta name="google-site-verification" content="GXs5KoUUkNCoaAZn7wPN-t01Pywp9M3sEjnt_3_ZWPc">

<meta name="octolytics-host" content="collector.githubapp.com" /><meta name="octolytics-app-id" content="github" /><meta name="octolytics-event-url" content="https://collector.githubapp.com/github-external/browser_event" /><meta name="octolytics-dimension-ga_id" content="" class="js-octo-ga-id" />
<meta name="analytics-location" content="/<user-name>/<repo-name>/blob/show" data-pjax-transient="true" />


<meta name="optimizely-sdk-key" content="cowimJNste4j7QnBNCjaw" />

    <meta name="google-analytics" content="UA-3769691-2">


<meta class="js-ga-set" name="dimension1" content="Logged Out">



  

      <meta name="hostname" content="github.com">
    <meta name="user-login" content="">


      <meta name="expected-hostname" content="github.com">


    <meta name="enabled-features" content="MARKETPLACE_PENDING_INSTALLATIONS,JS_CHUNKING">

  <meta http-equiv="x-pjax-version" content="e25bbb9b6f43228a9f18e7b5bb953df2">
  

      <link href="https://github.com/hpc-thai/HPCThai/commits/master.atom" rel="alternate" title="Recent Commits to HPCThai:master" type="application/atom+xml">

  <meta name="go-import" content="github.com/hpc-thai/HPCThai git https://github.com/hpc-thai/HPCThai.git">

  <meta name="octolytics-dimension-user_id" content="9413197" /><meta name="octolytics-dimension-user_login" content="hpc-thai" /><meta name="octolytics-dimension-repository_id" content="26068979" /><meta name="octolytics-dimension-repository_nwo" content="hpc-thai/HPCThai" /><meta name="octolytics-dimension-repository_public" content="true" /><meta name="octolytics-dimension-repository_is_fork" content="false" /><meta name="octolytics-dimension-repository_network_root_id" content="26068979" /><meta name="octolytics-dimension-repository_network_root_nwo" content="hpc-thai/HPCThai" /><meta name="octolytics-dimension-repository_explore_github_marketplace_ci_cta_shown" content="false" />


    <link rel="canonical" href="https://github.com/hpc-thai/HPCThai/blob/master/introHPC/07/bern_amdahl.cpp" data-pjax-transient>


  <meta name="browser-stats-url" content="https://api.github.com/_private/browser/stats">

  <meta name="browser-errors-url" content="https://api.github.com/_private/browser/errors">

  <link rel="mask-icon" href="https://github.githubassets.com/pinned-octocat.svg" color="#000000">
  <link rel="alternate icon" class="js-site-favicon" type="image/png" href="https://github.githubassets.com/favicons/favicon.png">
  <link rel="icon" class="js-site-favicon" type="image/svg+xml" href="https://github.githubassets.com/favicons/favicon.svg">

<meta name="theme-color" content="#1e2327">


  <link rel="manifest" href="/manifest.json" crossOrigin="use-credentials">

  </head>

  <body class="logged-out env-production page-responsive page-blob">
    

    <div class="position-relative js-header-wrapper ">
      <a href="#start-of-content" class="px-2 py-4 bg-blue text-white show-on-focus js-skip-to-content">Skip to content</a>
      <span class="Progress progress-pjax-loader position-fixed width-full js-pjax-loader-bar">
        <span class="progress-pjax-loader-bar top-0 left-0" style="width: 0%;"></span>
      </span>

      
      



          <header class="Header-old header-logged-out js-details-container Details position-relative f4 py-2" role="banner">
  <div class="container-lg d-lg-flex flex-items-center p-responsive">
    <div class="d-flex flex-justify-between flex-items-center">
        <a class="mr-4" href="https://github.com/" aria-label="Homepage" data-ga-click="(Logged out) Header, go to homepage, icon:logo-wordmark">
          <svg height="32" class="octicon octicon-mark-github text-white" viewBox="0 0 16 16" version="1.1" width="32" aria-hidden="true"><path fill-rule="evenodd" d="M8 0C3.58 0 0 3.58 0 8c0 3.54 2.29 6.53 5.47 7.59.4.07.55-.17.55-.38 0-.19-.01-.82-.01-1.49-2.01.37-2.53-.49-2.69-.94-.09-.23-.48-.94-.82-1.13-.28-.15-.68-.52-.01-.53.63-.01 1.08.58 1.23.82.72 1.21 1.87.87 2.33.66.07-.52.28-.87.51-1.07-1.78-.2-3.64-.89-3.64-3.95 0-.87.31-1.59.82-2.15-.08-.2-.36-1.02.08-2.12 0 0 .67-.21 2.2.82.64-.18 1.32-.27 2-.27.68 0 1.36.09 2 .27 1.53-1.04 2.2-.82 2.2-.82.44 1.1.16 1.92.08 2.12.51.56.82 1.27.82 2.15 0 3.07-1.87 3.75-3.65 3.95.29.25.54.73.54 1.48 0 1.07-.01 1.93-.01 2.2 0 .21.15.46.55.38A8.013 8.013 0 0016 8c0-4.42-3.58-8-8-8z"></path></svg>
        </a>

          <div class="d-lg-none css-truncate css-truncate-target width-fit p-2">
            
                <svg class="octicon octicon-repo" viewBox="0 0 12 16" version="1.1" width="12" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M4 9H3V8h1v1zm0-3H3v1h1V6zm0-2H3v1h1V4zm0-2H3v1h1V2zm8-1v12c0 .55-.45 1-1 1H6v2l-1.5-1.5L3 16v-2H1c-.55 0-1-.45-1-1V1c0-.55.45-1 1-1h10c.55 0 1 .45 1 1zm-1 10H1v2h2v-1h3v1h5v-2zm0-10H2v9h9V1z"></path></svg>
    <a class="Header-link" href="/hpc-thai">hpc-thai</a>
    /
    <a class="Header-link" href="/hpc-thai/HPCThai">HPCThai</a>


          </div>

        <div class="d-flex flex-items-center">
              <a href="/join?ref_cta=Sign+up&ref_loc=header+logged+out&ref_page=%2F%3Cuser-name%3E%2F%3Crepo-name%3E%2Fblob%2Fshow&source=header-repo"
                class="d-inline-block d-lg-none f5 text-white no-underline border border-gray-dark rounded-2 px-2 py-1 mr-3 mr-sm-5"
                data-hydro-click="{"event_type":"authentication.click","payload":{"location_in_page":"site header","repository_id":null,"auth_type":"SIGN_UP","originating_url":"https://github.com/hpc-thai/HPCThai/blob/master/introHPC/07/bern_amdahl.cpp","user_id":null}}" data-hydro-click-hmac="2f35b655b7a864979ea8bd002955f04bb0155aad3b6cb2e38a682e777b3c00cc"
                data-ga-click="Sign up, click to sign up for account, ref_page:/<user-name>/<repo-name>/blob/show;ref_cta:Sign up;ref_loc:header logged out">
                Sign up
              </a>

          <button class="btn-link d-lg-none mt-1 js-details-target" type="button" aria-label="Toggle navigation" aria-expanded="false">
            <svg height="24" class="octicon octicon-three-bars text-white" viewBox="0 0 12 16" version="1.1" width="18" aria-hidden="true"><path fill-rule="evenodd" d="M11.41 9H.59C0 9 0 8.59 0 8c0-.59 0-1 .59-1H11.4c.59 0 .59.41.59 1 0 .59 0 1-.59 1h.01zm0-4H.59C0 5 0 4.59 0 4c0-.59 0-1 .59-1H11.4c.59 0 .59.41.59 1 0 .59 0 1-.59 1h.01zM.59 11H11.4c.59 0 .59.41.59 1 0 .59 0 1-.59 1H.59C0 13 0 12.59 0 12c0-.59 0-1 .59-1z"></path></svg>
          </button>
        </div>
    </div>

    <div class="HeaderMenu HeaderMenu--logged-out position-fixed top-0 right-0 bottom-0 height-fit position-lg-relative d-lg-flex flex-justify-between flex-items-center flex-auto">
      <div class="d-flex d-lg-none flex-justify-end border-bottom bg-gray-light p-3">
        <button class="btn-link js-details-target" type="button" aria-label="Toggle navigation" aria-expanded="false">
          <svg height="24" class="octicon octicon-x text-gray" viewBox="0 0 12 16" version="1.1" width="18" aria-hidden="true"><path fill-rule="evenodd" d="M7.48 8l3.75 3.75-1.48 1.48L6 9.48l-3.75 3.75-1.48-1.48L4.52 8 .77 4.25l1.48-1.48L6 6.52l3.75-3.75 1.48 1.48L7.48 8z"></path></svg>
        </button>
      </div>

        <nav class="mt-0 px-3 px-lg-0 mb-5 mb-lg-0" aria-label="Global">
          <ul class="d-lg-flex list-style-none">
              <li class="d-block d-lg-flex flex-lg-nowrap flex-lg-items-center border-bottom border-lg-bottom-0 mr-0 mr-lg-3 edge-item-fix position-relative flex-wrap flex-justify-between d-flex flex-items-center ">
                <details class="HeaderMenu-details details-overlay details-reset width-full">
                  <summary class="HeaderMenu-summary HeaderMenu-link px-0 py-3 border-0 no-wrap d-block d-lg-inline-block">
                    Why GitHub?
                    <svg x="0px" y="0px" viewBox="0 0 14 8" xml:space="preserve" fill="none" class="icon-chevon-down-mktg position-absolute position-lg-relative">
                      <path d="M1,1l6.2,6L13,1"></path>
                    </svg>
                  </summary>
                  <div class="dropdown-menu flex-auto rounded-1 bg-white px-0 mt-0 pb-4 p-lg-4 position-relative position-lg-absolute left-0 left-lg-n4">
                    <a href="/features" class="py-2 lh-condensed-ultra d-block link-gray-dark no-underline h5 Bump-link--hover" data-ga-click="(Logged out) Header, go to Features">Features <span class="Bump-link-symbol float-right text-normal text-gray-light">→</span></a>
                    <ul class="list-style-none f5 pb-3">
                      <li class="edge-item-fix"><a href="/features/code-review/" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Code review">Code review</a></li>
                      <li class="edge-item-fix"><a href="/features/project-management/" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Project management">Project management</a></li>
                      <li class="edge-item-fix"><a href="/features/integrations" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Integrations">Integrations</a></li>
                      <li class="edge-item-fix"><a href="/features/actions" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Actions">Actions</a></li>
                      <li class="edge-item-fix"><a href="/features/packages" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to GitHub Packages">Packages</a></li>
                      <li class="edge-item-fix"><a href="/features/security" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Security">Security</a></li>
                      <li class="edge-item-fix"><a href="/features#team-management" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Team management">Team management</a></li>
                      <li class="edge-item-fix"><a href="/features#hosting" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Code hosting">Hosting</a></li>
                    </ul>

                    <ul class="list-style-none mb-0 border-lg-top pt-lg-3">
                      <li class="edge-item-fix"><a href="/customer-stories" class="py-2 lh-condensed-ultra d-block no-underline link-gray-dark no-underline h5 Bump-link--hover" data-ga-click="(Logged out) Header, go to Customer stories">Customer stories <span class="Bump-link-symbol float-right text-normal text-gray-light">→</span></a></li>
                      <li class="edge-item-fix"><a href="/security" class="py-2 lh-condensed-ultra d-block no-underline link-gray-dark no-underline h5 Bump-link--hover" data-ga-click="(Logged out) Header, go to Security">Security <span class="Bump-link-symbol float-right text-normal text-gray-light">→</span></a></li>
                    </ul>
                  </div>
                </details>
              </li>
                <li class="border-bottom border-lg-bottom-0 mr-0 mr-lg-3">
                  <a href="/team" class="HeaderMenu-link no-underline py-3 d-block d-lg-inline-block" data-ga-click="(Logged out) Header, go to Team">Team</a>
                </li>
              <li class="border-bottom border-lg-bottom-0 mr-0 mr-lg-3">
                <a href="/enterprise" class="HeaderMenu-link no-underline py-3 d-block d-lg-inline-block" data-ga-click="(Logged out) Header, go to Enterprise">Enterprise</a>
              </li>

              <li class="d-block d-lg-flex flex-lg-nowrap flex-lg-items-center border-bottom border-lg-bottom-0 mr-0 mr-lg-3 edge-item-fix position-relative flex-wrap flex-justify-between d-flex flex-items-center ">
                <details class="HeaderMenu-details details-overlay details-reset width-full">
                  <summary class="HeaderMenu-summary HeaderMenu-link px-0 py-3 border-0 no-wrap d-block d-lg-inline-block">
                    Explore
                    <svg x="0px" y="0px" viewBox="0 0 14 8" xml:space="preserve" fill="none" class="icon-chevon-down-mktg position-absolute position-lg-relative">
                      <path d="M1,1l6.2,6L13,1"></path>
                    </svg>
                  </summary>

                  <div class="dropdown-menu flex-auto rounded-1 bg-white px-0 pt-2 pb-0 mt-0 pb-4 p-lg-4 position-relative position-lg-absolute left-0 left-lg-n4">
                    <ul class="list-style-none mb-3">
                      <li class="edge-item-fix"><a href="/explore" class="py-2 lh-condensed-ultra d-block link-gray-dark no-underline h5 Bump-link--hover" data-ga-click="(Logged out) Header, go to Explore">Explore GitHub <span class="Bump-link-symbol float-right text-normal text-gray-light">→</span></a></li>
                    </ul>

                    <h4 class="text-gray-light text-normal text-mono f5 mb-2 border-lg-top pt-lg-3">Learn & contribute</h4>
                    <ul class="list-style-none mb-3">
                      <li class="edge-item-fix"><a href="/topics" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Topics">Topics</a></li>
                        <li class="edge-item-fix"><a href="/collections" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Collections">Collections</a></li>
                      <li class="edge-item-fix"><a href="/trending" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Trending">Trending</a></li>
                      <li class="edge-item-fix"><a href="https://lab.github.com/" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Learning lab">Learning Lab</a></li>
                      <li class="edge-item-fix"><a href="https://opensource.guide" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Open source guides">Open source guides</a></li>
                    </ul>

                    <h4 class="text-gray-light text-normal text-mono f5 mb-2 border-lg-top pt-lg-3">Connect with others</h4>
                    <ul class="list-style-none mb-0">
                      <li class="edge-item-fix"><a href="https://github.com/events" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Events">Events</a></li>
                      <li class="edge-item-fix"><a href="https://github.community" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Community forum">Community forum</a></li>
                      <li class="edge-item-fix"><a href="https://education.github.com" class="py-2 pb-0 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to GitHub Education">GitHub Education</a></li>
                    </ul>
                  </div>
                </details>
              </li>

              <li class="border-bottom border-lg-bottom-0 mr-0 mr-lg-3">
                <a href="/marketplace" class="HeaderMenu-link no-underline py-3 d-block d-lg-inline-block" data-ga-click="(Logged out) Header, go to Marketplace">Marketplace</a>
              </li>

              <li class="d-block d-lg-flex flex-lg-nowrap flex-lg-items-center border-bottom border-lg-bottom-0 mr-0 mr-lg-3 edge-item-fix position-relative flex-wrap flex-justify-between d-flex flex-items-center ">
                <details class="HeaderMenu-details details-overlay details-reset width-full">
                  <summary class="HeaderMenu-summary HeaderMenu-link px-0 py-3 border-0 no-wrap d-block d-lg-inline-block">
                    Pricing
                    <svg x="0px" y="0px" viewBox="0 0 14 8" xml:space="preserve" fill="none" class="icon-chevon-down-mktg position-absolute position-lg-relative">
                       <path d="M1,1l6.2,6L13,1"></path>
                    </svg>
                  </summary>

                  <div class="dropdown-menu flex-auto rounded-1 bg-white px-0 pt-2 pb-4 mt-0 p-lg-4 position-relative position-lg-absolute left-0 left-lg-n4">
                    <a href="/pricing" class="pb-2 lh-condensed-ultra d-block link-gray-dark no-underline h5 Bump-link--hover" data-ga-click="(Logged out) Header, go to Pricing">Plans <span class="Bump-link-symbol float-right text-normal text-gray-light">→</span></a>

                    <ul class="list-style-none mb-3">
                      <li class="edge-item-fix"><a href="/pricing#feature-comparison" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Compare plans">Compare plans</a></li>
                      <li class="edge-item-fix"><a href="https://enterprise.github.com/contact" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Contact Sales">Contact Sales</a></li>
                    </ul>

                    <ul class="list-style-none mb-0 border-lg-top pt-lg-3">
                      <li class="edge-item-fix"><a href="/nonprofit" class="py-2 lh-condensed-ultra d-block no-underline link-gray-dark no-underline h5 Bump-link--hover" data-ga-click="(Logged out) Header, go to Nonprofits">Nonprofit <span class="Bump-link-symbol float-right text-normal text-gray-light">→</span></a></li>
                      <li class="edge-item-fix"><a href="https://education.github.com" class="py-2 pb-0 lh-condensed-ultra d-block no-underline link-gray-dark no-underline h5 Bump-link--hover"  data-ga-click="(Logged out) Header, go to Education">Education <span class="Bump-link-symbol float-right text-normal text-gray-light">→</span></a></li>
                    </ul>
                  </div>
                </details>
              </li>
          </ul>
        </nav>

      <div class="d-lg-flex flex-items-center px-3 px-lg-0 text-center text-lg-left">
          <div class="d-lg-flex mb-3 mb-lg-0">
            <div class="header-search flex-self-stretch flex-lg-self-auto mr-0 mr-lg-3 mb-3 mb-lg-0 scoped-search site-scoped-search js-site-search position-relative js-jump-to"
  role="combobox"
  aria-owns="jump-to-results"
  aria-label="Search or jump to"
  aria-haspopup="listbox"
  aria-expanded="false"
>
  <div class="position-relative">
    <!-- '"` --><!-- </textarea></xmp> --></option></form><form class="js-site-search-form" role="search" aria-label="Site" data-scope-type="Repository" data-scope-id="26068979" data-scoped-search-url="/hpc-thai/HPCThai/search" data-unscoped-search-url="/search" action="/hpc-thai/HPCThai/search" accept-charset="UTF-8" method="get">
      <label class="form-control input-sm header-search-wrapper p-0 header-search-wrapper-jump-to position-relative d-flex flex-justify-between flex-items-center js-chromeless-input-container">
        <input type="text"
          class="form-control input-sm header-search-input jump-to-field js-jump-to-field js-site-search-focus js-site-search-field is-clearable"
          data-hotkey="s,/"
          name="q"
          value=""
          placeholder="Search"
          data-unscoped-placeholder="Search GitHub"
          data-scoped-placeholder="Search"
          autocapitalize="off"
          aria-autocomplete="list"
          aria-controls="jump-to-results"
          aria-label="Search"
          data-jump-to-suggestions-path="/_graphql/GetSuggestedNavigationDestinations"
          spellcheck="false"
          autocomplete="off"
          >
          <input type="hidden" data-csrf="true" class="js-data-jump-to-suggestions-path-csrf" value="vY5KVp3PujL1mez3kIcBtgKGG4YP31nUSYvc8dlv0kEY2g4sZjVEgVm3kbDsd0Wi1/+K+gtvleaaYseKVacQGg==" />
          <input type="hidden" class="js-site-search-type-field" name="type" >
            <img src="https://github.githubassets.com/images/search-key-slash.svg" alt="" class="mr-2 header-search-key-slash">

            <div class="Box position-absolute overflow-hidden d-none jump-to-suggestions js-jump-to-suggestions-container">
              
<ul class="d-none js-jump-to-suggestions-template-container">
  

<li class="d-flex flex-justify-start flex-items-center p-0 f5 navigation-item js-navigation-item js-jump-to-suggestion" role="option">
  <a tabindex="-1" class="no-underline d-flex flex-auto flex-items-center jump-to-suggestions-path js-jump-to-suggestion-path js-navigation-open p-2" href="">
    <div class="jump-to-octicon js-jump-to-octicon flex-shrink-0 mr-2 text-center d-none">
      <svg height="16" width="16" class="octicon octicon-repo flex-shrink-0 js-jump-to-octicon-repo d-none" title="Repository" aria-label="Repository" viewBox="0 0 12 16" version="1.1" role="img"><path fill-rule="evenodd" d="M4 9H3V8h1v1zm0-3H3v1h1V6zm0-2H3v1h1V4zm0-2H3v1h1V2zm8-1v12c0 .55-.45 1-1 1H6v2l-1.5-1.5L3 16v-2H1c-.55 0-1-.45-1-1V1c0-.55.45-1 1-1h10c.55 0 1 .45 1 1zm-1 10H1v2h2v-1h3v1h5v-2zm0-10H2v9h9V1z"></path></svg>
      <svg height="16" width="16" class="octicon octicon-project flex-shrink-0 js-jump-to-octicon-project d-none" title="Project" aria-label="Project" viewBox="0 0 15 16" version="1.1" role="img"><path fill-rule="evenodd" d="M10 12h3V2h-3v10zm-4-2h3V2H6v8zm-4 4h3V2H2v12zm-1 1h13V1H1v14zM14 0H1a1 1 0 00-1 1v14a1 1 0 001 1h13a1 1 0 001-1V1a1 1 0 00-1-1z"></path></svg>
      <svg height="16" width="16" class="octicon octicon-search flex-shrink-0 js-jump-to-octicon-search d-none" title="Search" aria-label="Search" viewBox="0 0 16 16" version="1.1" role="img"><path fill-rule="evenodd" d="M15.7 13.3l-3.81-3.83A5.93 5.93 0 0013 6c0-3.31-2.69-6-6-6S1 2.69 1 6s2.69 6 6 6c1.3 0 2.48-.41 3.47-1.11l3.83 3.81c.19.2.45.3.7.3.25 0 .52-.09.7-.3a.996.996 0 000-1.41v.01zM7 10.7c-2.59 0-4.7-2.11-4.7-4.7 0-2.59 2.11-4.7 4.7-4.7 2.59 0 4.7 2.11 4.7 4.7 0 2.59-2.11 4.7-4.7 4.7z"></path></svg>
    </div>

    <img class="avatar mr-2 flex-shrink-0 js-jump-to-suggestion-avatar d-none" alt="" aria-label="Team" src="" width="28" height="28">

    <div class="jump-to-suggestion-name js-jump-to-suggestion-name flex-auto overflow-hidden text-left no-wrap css-truncate css-truncate-target">
    </div>

    <div class="border rounded-1 flex-shrink-0 bg-gray px-1 text-gray-light ml-1 f6 d-none js-jump-to-badge-search">
      <span class="js-jump-to-badge-search-text-default d-none" aria-label="in this repository">
        In this repository
      </span>
      <span class="js-jump-to-badge-search-text-global d-none" aria-label="in all of GitHub">
        All GitHub
      </span>
      <span aria-hidden="true" class="d-inline-block ml-1 v-align-middle">↵</span>
    </div>

    <div aria-hidden="true" class="border rounded-1 flex-shrink-0 bg-gray px-1 text-gray-light ml-1 f6 d-none d-on-nav-focus js-jump-to-badge-jump">
      Jump to
      <span class="d-inline-block ml-1 v-align-middle">↵</span>
    </div>
  </a>
</li>

</ul>

<ul class="d-none js-jump-to-no-results-template-container">
  <li class="d-flex flex-justify-center flex-items-center f5 d-none js-jump-to-suggestion p-2">
    <span class="text-gray">No suggested jump to results</span>
  </li>
</ul>

<ul id="jump-to-results" role="listbox" class="p-0 m-0 js-navigation-container jump-to-suggestions-results-container js-jump-to-suggestions-results-container">
  

<li class="d-flex flex-justify-start flex-items-center p-0 f5 navigation-item js-navigation-item js-jump-to-scoped-search d-none" role="option">
  <a tabindex="-1" class="no-underline d-flex flex-auto flex-items-center jump-to-suggestions-path js-jump-to-suggestion-path js-navigation-open p-2" href="">
    <div class="jump-to-octicon js-jump-to-octicon flex-shrink-0 mr-2 text-center d-none">
      <svg height="16" width="16" class="octicon octicon-repo flex-shrink-0 js-jump-to-octicon-repo d-none" title="Repository" aria-label="Repository" viewBox="0 0 12 16" version="1.1" role="img"><path fill-rule="evenodd" d="M4 9H3V8h1v1zm0-3H3v1h1V6zm0-2H3v1h1V4zm0-2H3v1h1V2zm8-1v12c0 .55-.45 1-1 1H6v2l-1.5-1.5L3 16v-2H1c-.55 0-1-.45-1-1V1c0-.55.45-1 1-1h10c.55 0 1 .45 1 1zm-1 10H1v2h2v-1h3v1h5v-2zm0-10H2v9h9V1z"></path></svg>
      <svg height="16" width="16" class="octicon octicon-project flex-shrink-0 js-jump-to-octicon-project d-none" title="Project" aria-label="Project" viewBox="0 0 15 16" version="1.1" role="img"><path fill-rule="evenodd" d="M10 12h3V2h-3v10zm-4-2h3V2H6v8zm-4 4h3V2H2v12zm-1 1h13V1H1v14zM14 0H1a1 1 0 00-1 1v14a1 1 0 001 1h13a1 1 0 001-1V1a1 1 0 00-1-1z"></path></svg>
      <svg height="16" width="16" class="octicon octicon-search flex-shrink-0 js-jump-to-octicon-search d-none" title="Search" aria-label="Search" viewBox="0 0 16 16" version="1.1" role="img"><path fill-rule="evenodd" d="M15.7 13.3l-3.81-3.83A5.93 5.93 0 0013 6c0-3.31-2.69-6-6-6S1 2.69 1 6s2.69 6 6 6c1.3 0 2.48-.41 3.47-1.11l3.83 3.81c.19.2.45.3.7.3.25 0 .52-.09.7-.3a.996.996 0 000-1.41v.01zM7 10.7c-2.59 0-4.7-2.11-4.7-4.7 0-2.59 2.11-4.7 4.7-4.7 2.59 0 4.7 2.11 4.7 4.7 0 2.59-2.11 4.7-4.7 4.7z"></path></svg>
    </div>

    <img class="avatar mr-2 flex-shrink-0 js-jump-to-suggestion-avatar d-none" alt="" aria-label="Team" src="" width="28" height="28">

    <div class="jump-to-suggestion-name js-jump-to-suggestion-name flex-auto overflow-hidden text-left no-wrap css-truncate css-truncate-target">
    </div>

    <div class="border rounded-1 flex-shrink-0 bg-gray px-1 text-gray-light ml-1 f6 d-none js-jump-to-badge-search">
      <span class="js-jump-to-badge-search-text-default d-none" aria-label="in this repository">
        In this repository
      </span>
      <span class="js-jump-to-badge-search-text-global d-none" aria-label="in all of GitHub">
        All GitHub
      </span>
      <span aria-hidden="true" class="d-inline-block ml-1 v-align-middle">↵</span>
    </div>

    <div aria-hidden="true" class="border rounded-1 flex-shrink-0 bg-gray px-1 text-gray-light ml-1 f6 d-none d-on-nav-focus js-jump-to-badge-jump">
      Jump to
      <span class="d-inline-block ml-1 v-align-middle">↵</span>
    </div>
  </a>
</li>

  

<li class="d-flex flex-justify-start flex-items-center p-0 f5 navigation-item js-navigation-item js-jump-to-global-search d-none" role="option">
  <a tabindex="-1" class="no-underline d-flex flex-auto flex-items-center jump-to-suggestions-path js-jump-to-suggestion-path js-navigation-open p-2" href="">
    <div class="jump-to-octicon js-jump-to-octicon flex-shrink-0 mr-2 text-center d-none">
      <svg height="16" width="16" class="octicon octicon-repo flex-shrink-0 js-jump-to-octicon-repo d-none" title="Repository" aria-label="Repository" viewBox="0 0 12 16" version="1.1" role="img"><path fill-rule="evenodd" d="M4 9H3V8h1v1zm0-3H3v1h1V6zm0-2H3v1h1V4zm0-2H3v1h1V2zm8-1v12c0 .55-.45 1-1 1H6v2l-1.5-1.5L3 16v-2H1c-.55 0-1-.45-1-1V1c0-.55.45-1 1-1h10c.55 0 1 .45 1 1zm-1 10H1v2h2v-1h3v1h5v-2zm0-10H2v9h9V1z"></path></svg>
      <svg height="16" width="16" class="octicon octicon-project flex-shrink-0 js-jump-to-octicon-project d-none" title="Project" aria-label="Project" viewBox="0 0 15 16" version="1.1" role="img"><path fill-rule="evenodd" d="M10 12h3V2h-3v10zm-4-2h3V2H6v8zm-4 4h3V2H2v12zm-1 1h13V1H1v14zM14 0H1a1 1 0 00-1 1v14a1 1 0 001 1h13a1 1 0 001-1V1a1 1 0 00-1-1z"></path></svg>
      <svg height="16" width="16" class="octicon octicon-search flex-shrink-0 js-jump-to-octicon-search d-none" title="Search" aria-label="Search" viewBox="0 0 16 16" version="1.1" role="img"><path fill-rule="evenodd" d="M15.7 13.3l-3.81-3.83A5.93 5.93 0 0013 6c0-3.31-2.69-6-6-6S1 2.69 1 6s2.69 6 6 6c1.3 0 2.48-.41 3.47-1.11l3.83 3.81c.19.2.45.3.7.3.25 0 .52-.09.7-.3a.996.996 0 000-1.41v.01zM7 10.7c-2.59 0-4.7-2.11-4.7-4.7 0-2.59 2.11-4.7 4.7-4.7 2.59 0 4.7 2.11 4.7 4.7 0 2.59-2.11 4.7-4.7 4.7z"></path></svg>
    </div>

    <img class="avatar mr-2 flex-shrink-0 js-jump-to-suggestion-avatar d-none" alt="" aria-label="Team" src="" width="28" height="28">

    <div class="jump-to-suggestion-name js-jump-to-suggestion-name flex-auto overflow-hidden text-left no-wrap css-truncate css-truncate-target">
    </div>

    <div class="border rounded-1 flex-shrink-0 bg-gray px-1 text-gray-light ml-1 f6 d-none js-jump-to-badge-search">
      <span class="js-jump-to-badge-search-text-default d-none" aria-label="in this repository">
        In this repository
      </span>
      <span class="js-jump-to-badge-search-text-global d-none" aria-label="in all of GitHub">
        All GitHub
      </span>
      <span aria-hidden="true" class="d-inline-block ml-1 v-align-middle">↵</span>
    </div>

    <div aria-hidden="true" class="border rounded-1 flex-shrink-0 bg-gray px-1 text-gray-light ml-1 f6 d-none d-on-nav-focus js-jump-to-badge-jump">
      Jump to
      <span class="d-inline-block ml-1 v-align-middle">↵</span>
    </div>
  </a>
</li>


</ul>

            </div>
      </label>
</form>  </div>
</div>

          </div>

        <a href="/login?return_to=%2Fhpc-thai%2FHPCThai%2Fblob%2Fmaster%2FintroHPC%2F07%2Fbern_amdahl.cpp"
          class="HeaderMenu-link no-underline mr-3"
          data-hydro-click="{"event_type":"authentication.click","payload":{"location_in_page":"site header menu","repository_id":null,"auth_type":"SIGN_UP","originating_url":"https://github.com/hpc-thai/HPCThai/blob/master/introHPC/07/bern_amdahl.cpp","user_id":null}}" data-hydro-click-hmac="0b02164d1d8c86ee5dd2178fd3148474fa6aa818bdfd4d42142ee82c6320249e"
          data-ga-click="(Logged out) Header, clicked Sign in, text:sign-in">
          Sign in
        </a>
            <a href="/join?ref_cta=Sign+up&ref_loc=header+logged+out&ref_page=%2F%3Cuser-name%3E%2F%3Crepo-name%3E%2Fblob%2Fshow&source=header-repo&source_repo=hpc-thai%2FHPCThai"
              class="HeaderMenu-link d-inline-block no-underline border border-gray-dark rounded-1 px-2 py-1"
              data-hydro-click="{"event_type":"authentication.click","payload":{"location_in_page":"site header menu","repository_id":null,"auth_type":"SIGN_UP","originating_url":"https://github.com/hpc-thai/HPCThai/blob/master/introHPC/07/bern_amdahl.cpp","user_id":null}}" data-hydro-click-hmac="0b02164d1d8c86ee5dd2178fd3148474fa6aa818bdfd4d42142ee82c6320249e"
              data-ga-click="Sign up, click to sign up for account, ref_page:/<user-name>/<repo-name>/blob/show;ref_cta:Sign up;ref_loc:header logged out">
              Sign up
            </a>
      </div>
    </div>
  </div>
</header>

    </div>

  <div id="start-of-content" class="show-on-focus"></div>




    <div id="js-flash-container">


  <template class="js-flash-template">
    <div class="flash flash-full  js-flash-template-container">
  <div class="container-lg px-2" >
    <button class="flash-close js-flash-close" type="button" aria-label="Dismiss this message">
      <svg class="octicon octicon-x" viewBox="0 0 12 16" version="1.1" width="12" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M7.48 8l3.75 3.75-1.48 1.48L6 9.48l-3.75 3.75-1.48-1.48L4.52 8 .77 4.25l1.48-1.48L6 6.52l3.75-3.75 1.48 1.48L7.48 8z"></path></svg>
    </button>
    
      <div class="js-flash-template-message"></div>

  </div>
</div>
  </template>
</div>


      

  <include-fragment class="js-notification-shelf-include-fragment" data-base-src="https://github.com/notifications/beta/shelf"></include-fragment>




  <div class="application-main " data-commit-hovercards-enabled>
        <div itemscope itemtype="http://schema.org/SoftwareSourceCode" class="">
    <main  >
      

  












  <div class="pagehead repohead hx_repohead readability-menu bg-gray-light pb-0 pt-0 pt-lg-3">

    <div class="d-flex container-lg mb-4 p-responsive d-none d-lg-flex">

      <div class="flex-auto min-width-0 width-fit mr-3">
        <h1 class="public  d-flex flex-wrap flex-items-center break-word float-none ">
  <span class="flex-self-stretch" style="margin-top: -2px;">
      <svg class="octicon octicon-repo" viewBox="0 0 12 16" version="1.1" width="12" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M4 9H3V8h1v1zm0-3H3v1h1V6zm0-2H3v1h1V4zm0-2H3v1h1V2zm8-1v12c0 .55-.45 1-1 1H6v2l-1.5-1.5L3 16v-2H1c-.55 0-1-.45-1-1V1c0-.55.45-1 1-1h10c.55 0 1 .45 1 1zm-1 10H1v2h2v-1h3v1h5v-2zm0-10H2v9h9V1z"></path></svg>
  </span>
  <span class="author ml-2 flex-self-stretch" itemprop="author">
    <a class="url fn" rel="author" data-hovercard-type="user" data-hovercard-url="/users/hpc-thai/hovercard" data-octo-click="hovercard-link-click" data-octo-dimensions="link_type:self" href="/hpc-thai">hpc-thai</a>
  </span>
  <span class="path-divider flex-self-stretch">/</span>
  <strong itemprop="name" class="mr-2 flex-self-stretch">
    <a data-pjax="#js-repo-pjax-container" href="/hpc-thai/HPCThai">HPCThai</a>
  </strong>
  
</h1>


      </div>

      <ul class="pagehead-actions flex-shrink-0 " >




  <li>
    
  <a class="tooltipped tooltipped-s btn btn-sm btn-with-count" aria-label="You must be signed in to watch a repository" rel="nofollow" data-hydro-click="{"event_type":"authentication.click","payload":{"location_in_page":"notification subscription menu watch","repository_id":null,"auth_type":"LOG_IN","originating_url":"https://github.com/hpc-thai/HPCThai/blob/master/introHPC/07/bern_amdahl.cpp","user_id":null}}" data-hydro-click-hmac="4f97bc637b483f10fbb8d853d333d241a8750275674151c5c0d3e788bc6bc2c6" href="/login?return_to=%2Fhpc-thai%2FHPCThai">
    <svg class="octicon octicon-eye" viewBox="0 0 16 16" version="1.1" width="16" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M8.06 2C3 2 0 8 0 8s3 6 8.06 6C13 14 16 8 16 8s-3-6-7.94-6zM8 12c-2.2 0-4-1.78-4-4 0-2.2 1.8-4 4-4 2.22 0 4 1.8 4 4 0 2.22-1.78 4-4 4zm2-4c0 1.11-.89 2-2 2-1.11 0-2-.89-2-2 0-1.11.89-2 2-2 1.11 0 2 .89 2 2z"></path></svg>
    Watch
</a>    <a class="social-count" href="/hpc-thai/HPCThai/watchers"
       aria-label="1 user is watching this repository">
      1
    </a>

  </li>

  <li>
        <a class="btn btn-sm btn-with-count  tooltipped tooltipped-s" aria-label="You must be signed in to star a repository" rel="nofollow" data-hydro-click="{"event_type":"authentication.click","payload":{"location_in_page":"star button","repository_id":26068979,"auth_type":"LOG_IN","originating_url":"https://github.com/hpc-thai/HPCThai/blob/master/introHPC/07/bern_amdahl.cpp","user_id":null}}" data-hydro-click-hmac="fe15af0f2f535022641e1c7afae7a778ac311d5a2849fc4262aa2d1ea292cc51" href="/login?return_to=%2Fhpc-thai%2FHPCThai">
      <svg height="16" class="octicon octicon-star v-align-text-bottom" vertical_align="text_bottom" viewBox="0 0 14 16" version="1.1" width="14" aria-hidden="true"><path fill-rule="evenodd" d="M14 6l-4.9-.64L7 1 4.9 5.36 0 6l3.6 3.26L2.67 14 7 11.67 11.33 14l-.93-4.74L14 6z"></path></svg>

      Star
</a>
    <a class="social-count js-social-count" href="/hpc-thai/HPCThai/stargazers"
      aria-label="0 users starred this repository">
      0
    </a>

  </li>

  <li>
      <a class="btn btn-sm btn-with-count tooltipped tooltipped-s" aria-label="You must be signed in to fork a repository" rel="nofollow" data-hydro-click="{"event_type":"authentication.click","payload":{"location_in_page":"repo details fork button","repository_id":26068979,"auth_type":"LOG_IN","originating_url":"https://github.com/hpc-thai/HPCThai/blob/master/introHPC/07/bern_amdahl.cpp","user_id":null}}" data-hydro-click-hmac="d319cc55532d347ffb75cdf395973c181eef068ca3d0d14a0e7ad00c1be96d09" href="/login?return_to=%2Fhpc-thai%2FHPCThai">
        <svg class="octicon octicon-repo-forked" viewBox="0 0 10 16" version="1.1" width="10" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M8 1a1.993 1.993 0 00-1 3.72V6L5 8 3 6V4.72A1.993 1.993 0 002 1a1.993 1.993 0 00-1 3.72V6.5l3 3v1.78A1.993 1.993 0 005 15a1.993 1.993 0 001-3.72V9.5l3-3V4.72A1.993 1.993 0 008 1zM2 4.2C1.34 4.2.8 3.65.8 3c0-.65.55-1.2 1.2-1.2.65 0 1.2.55 1.2 1.2 0 .65-.55 1.2-1.2 1.2zm3 10c-.66 0-1.2-.55-1.2-1.2 0-.65.55-1.2 1.2-1.2.65 0 1.2.55 1.2 1.2 0 .65-.55 1.2-1.2 1.2zm3-10c-.66 0-1.2-.55-1.2-1.2 0-.65.55-1.2 1.2-1.2.65 0 1.2.55 1.2 1.2 0 .65-.55 1.2-1.2 1.2z"></path></svg>
        Fork
</a>
    <a href="/hpc-thai/HPCThai/network/members" class="social-count"
       aria-label="0 users forked this repository">
      0
    </a>
  </li>
</ul>

    </div>
      <nav class="js-repo-nav js-sidenav-container-pjax clearfix hx_reponav reponav p-responsive d-none d-lg-block container-lg"
     itemscope
     itemtype="http://schema.org/BreadcrumbList"
    aria-label="Repository"
     data-pjax="#js-repo-pjax-container">
  <ul class="list-style-none">
    <li  itemscope itemtype="http://schema.org/ListItem" itemprop="itemListElement">
      <a class="js-selected-navigation-item selected reponav-item" itemprop="url" data-hotkey="g c" aria-current="page" data-selected-links="repo_source repo_downloads repo_commits repo_releases repo_tags repo_branches repo_packages repo_deployments /hpc-thai/HPCThai" href="/hpc-thai/HPCThai">
        <div class="d-inline"><svg class="octicon octicon-code" viewBox="0 0 14 16" version="1.1" width="14" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M9.5 3L8 4.5 11.5 8 8 11.5 9.5 13 14 8 9.5 3zm-5 0L0 8l4.5 5L6 11.5 2.5 8 6 4.5 4.5 3z"></path></svg></div>
        <span itemprop="name">Code</span>
        <meta itemprop="position" content="1">
</a>    </li>

      <li  itemscope itemtype="http://schema.org/ListItem" itemprop="itemListElement">
        <a itemprop="url" data-hotkey="g i" class="js-selected-navigation-item reponav-item" data-selected-links="repo_issues repo_labels repo_milestones /hpc-thai/HPCThai/issues" href="/hpc-thai/HPCThai/issues">
          <div class="d-inline"><svg class="octicon octicon-issue-opened" viewBox="0 0 14 16" version="1.1" width="14" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M7 2.3c3.14 0 5.7 2.56 5.7 5.7s-2.56 5.7-5.7 5.7A5.71 5.71 0 011.3 8c0-3.14 2.56-5.7 5.7-5.7zM7 1C3.14 1 0 4.14 0 8s3.14 7 7 7 7-3.14 7-7-3.14-7-7-7zm1 3H6v5h2V4zm0 6H6v2h2v-2z"></path></svg></div>
          <span itemprop="name">Issues</span>
          <span class="Counter">0</span>
          <meta itemprop="position" content="2">
</a>      </li>

    <li  itemscope itemtype="http://schema.org/ListItem" itemprop="itemListElement">
      <a data-hotkey="g p" data-skip-pjax="true" itemprop="url" class="js-selected-navigation-item reponav-item" data-selected-links="repo_pulls checks /hpc-thai/HPCThai/pulls" href="/hpc-thai/HPCThai/pulls">
        <div class="d-inline"><svg class="octicon octicon-git-pull-request" viewBox="0 0 12 16" version="1.1" width="12" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M11 11.28V5c-.03-.78-.34-1.47-.94-2.06C9.46 2.35 8.78 2.03 8 2H7V0L4 3l3 3V4h1c.27.02.48.11.69.31.21.2.3.42.31.69v6.28A1.993 1.993 0 0010 15a1.993 1.993 0 001-3.72zm-1 2.92c-.66 0-1.2-.55-1.2-1.2 0-.65.55-1.2 1.2-1.2.65 0 1.2.55 1.2 1.2 0 .65-.55 1.2-1.2 1.2zM4 3c0-1.11-.89-2-2-2a1.993 1.993 0 00-1 3.72v6.56A1.993 1.993 0 002 15a1.993 1.993 0 001-3.72V4.72c.59-.34 1-.98 1-1.72zm-.8 10c0 .66-.55 1.2-1.2 1.2-.65 0-1.2-.55-1.2-1.2 0-.65.55-1.2 1.2-1.2.65 0 1.2.55 1.2 1.2zM2 4.2C1.34 4.2.8 3.65.8 3c0-.65.55-1.2 1.2-1.2.65 0 1.2.55 1.2 1.2 0 .65-.55 1.2-1.2 1.2z"></path></svg></div>
        <span itemprop="name">Pull requests</span>
        <span class="Counter">0</span>
        <meta itemprop="position" content="4">
</a>    </li>


      <li itemscope itemtype="http://schema.org/ListItem" itemprop="itemListElement" class="position-relative float-left ">
        <a data-hotkey="g w" data-skip-pjax="true" class="js-selected-navigation-item reponav-item" data-selected-links="repo_actions /hpc-thai/HPCThai/actions" href="/hpc-thai/HPCThai/actions">
          <div class="d-inline"><svg class="octicon octicon-play" viewBox="0 0 14 16" version="1.1" width="14" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M14 8A7 7 0 110 8a7 7 0 0114 0zm-8.223 3.482l4.599-3.066a.5.5 0 000-.832L5.777 4.518A.5.5 0 005 4.934v6.132a.5.5 0 00.777.416z"></path></svg></div>
          Actions
</a>
      </li>

      <li >
        <a data-hotkey="g b" class="js-selected-navigation-item reponav-item" data-selected-links="repo_projects new_repo_project repo_project /hpc-thai/HPCThai/projects" href="/hpc-thai/HPCThai/projects">
          <div class="d-inline"><svg class="octicon octicon-project" viewBox="0 0 15 16" version="1.1" width="15" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M10 12h3V2h-3v10zm-4-2h3V2H6v8zm-4 4h3V2H2v12zm-1 1h13V1H1v14zM14 0H1a1 1 0 00-1 1v14a1 1 0 001 1h13a1 1 0 001-1V1a1 1 0 00-1-1z"></path></svg></div>
          Projects
          <span class="Counter">0</span>
</a>      </li>


      <li >
        <a data-skip-pjax="true" class="js-selected-navigation-item reponav-item" data-selected-links="security overview alerts policy token_scanning code_scanning /hpc-thai/HPCThai/security" href="/hpc-thai/HPCThai/security">
          <div class="d-inline"><svg class="octicon octicon-shield" viewBox="0 0 14 16" version="1.1" width="14" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M0 2l7-2 7 2v6.02C14 12.69 8.69 16 7 16c-1.69 0-7-3.31-7-7.98V2zm1 .75L7 1l6 1.75v5.268C13 12.104 8.449 15 7 15c-1.449 0-6-2.896-6-6.982V2.75zm1 .75L7 2v12c-1.207 0-5-2.482-5-5.985V3.5z"></path></svg></div>
          Security
              <span class="Counter js-security-tab-count" data-url="/hpc-thai/HPCThai/security/overall-count" hidden></span>
</a>      </li>

      <li >
        <a class="js-selected-navigation-item reponav-item" data-selected-links="repo_graphs repo_contributors dependency_graph dependabot_updates pulse people /hpc-thai/HPCThai/pulse" href="/hpc-thai/HPCThai/pulse">
          <div class="d-inline"><svg class="octicon octicon-graph" viewBox="0 0 16 16" version="1.1" width="16" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M16 14v1H0V0h1v14h15zM5 13H3V8h2v5zm4 0H7V3h2v10zm4 0h-2V6h2v7z"></path></svg></div>
          Insights
</a>      </li>


  </ul>
</nav>

  <div class="reponav-wrapper reponav-small d-lg-none">
  <nav class="reponav js-reponav text-center no-wrap"
       itemscope
       itemtype="http://schema.org/BreadcrumbList">

    <span itemscope itemtype="http://schema.org/ListItem" itemprop="itemListElement">
      <a class="js-selected-navigation-item selected reponav-item" itemprop="url" aria-current="page" data-selected-links="repo_source repo_downloads repo_commits repo_releases repo_tags repo_branches repo_packages repo_deployments /hpc-thai/HPCThai" href="/hpc-thai/HPCThai">
        <span itemprop="name">Code</span>
        <meta itemprop="position" content="1">
</a>    </span>

      <span itemscope itemtype="http://schema.org/ListItem" itemprop="itemListElement">
        <a itemprop="url" class="js-selected-navigation-item reponav-item" data-selected-links="repo_issues repo_labels repo_milestones /hpc-thai/HPCThai/issues" href="/hpc-thai/HPCThai/issues">
          <span itemprop="name">Issues</span>
          <span class="Counter">0</span>
          <meta itemprop="position" content="2">
</a>      </span>

    <span itemscope itemtype="http://schema.org/ListItem" itemprop="itemListElement">
      <a itemprop="url" class="js-selected-navigation-item reponav-item" data-selected-links="repo_pulls checks /hpc-thai/HPCThai/pulls" href="/hpc-thai/HPCThai/pulls">
        <span itemprop="name">Pull requests</span>
        <span class="Counter">0</span>
        <meta itemprop="position" content="4">
</a>    </span>


      <span itemscope itemtype="http://schema.org/ListItem" itemprop="itemListElement">
        <a itemprop="url" class="js-selected-navigation-item reponav-item" data-selected-links="repo_projects new_repo_project repo_project /hpc-thai/HPCThai/projects" href="/hpc-thai/HPCThai/projects">
          <span itemprop="name">Projects</span>
          <span class="Counter">0</span>
          <meta itemprop="position" content="5">
</a>      </span>

      <span itemscope itemtype="http://schema.org/ListItem" itemprop="itemListElement">
        <a itemprop="url" class="js-selected-navigation-item reponav-item" data-selected-links="repo_actions /hpc-thai/HPCThai/actions" href="/hpc-thai/HPCThai/actions">
          <span itemprop="name">Actions</span>
          <meta itemprop="position" content="6">
</a>      </span>


      <a itemprop="url" class="js-selected-navigation-item reponav-item" data-selected-links="security overview alerts policy token_scanning code_scanning /hpc-thai/HPCThai/security" href="/hpc-thai/HPCThai/security">
        <span itemprop="name">Security</span>
            <span class="Counter js-security-deferred-tab-count" hidden></span>
        <meta itemprop="position" content="8">
</a>
      <a class="js-selected-navigation-item reponav-item" data-selected-links="pulse /hpc-thai/HPCThai/pulse" href="/hpc-thai/HPCThai/pulse">
        Pulse
</a>

  </nav>
</div>


  </div>

  

  <include-fragment class="js-notification-shelf-include-fragment" data-base-src="https://github.com/notifications/beta/shelf"></include-fragment>


<div class="container-lg clearfix new-discussion-timeline  p-responsive">
  <div class="repository-content ">

    
    

  


    <a class="d-none js-permalink-shortcut" data-hotkey="y" href="/hpc-thai/HPCThai/blob/e1ffffd730a5072b7277c9a7bd39374479653786/introHPC/07/bern_amdahl.cpp">Permalink</a>

    <!-- blob contrib key: blob_contributors:v22:a5f23e9c054f5a388002d8d0f0bf2763 -->
      <signup-prompt-controller class="signup-prompt-bg rounded-1" data-prompt="signup" hidden>
    <div class="signup-prompt p-4 text-center mb-4 rounded-1">
      <div class="position-relative">
        <button
          type="button"
          class="position-absolute top-0 right-0 btn-link link-gray"
          data-action="click:signup-prompt-controller#dismiss"
          data-ga-click="(Logged out) Sign up prompt, clicked Dismiss, text:dismiss"
        >
          Dismiss
        </button>
        <h3 class="pt-2">Join GitHub today</h3>
        <p class="col-6 mx-auto">GitHub is home to over 50 million developers working together to host and review code, manage projects, and build software together.</p>
        <a class="btn btn-primary" data-ga-click="(Logged out) Sign up prompt, clicked Sign up, text:sign-up" data-hydro-click="{"event_type":"authentication.click","payload":{"location_in_page":"files signup prompt","repository_id":null,"auth_type":"SIGN_UP","originating_url":"https://github.com/hpc-thai/HPCThai/blob/master/introHPC/07/bern_amdahl.cpp","user_id":null}}" data-hydro-click-hmac="400671828eed25e741a60a54830f778385cee57fa330c9305342bfe129abbf3a" href="/join?source=prompt-blob-show&source_repo=hpc-thai%2FHPCThai">Sign up</a>
      </div>
    </div>
  </signup-prompt-controller>


    <div class="d-flex flex-items-start flex-shrink-0 flex-column flex-md-row pb-3">
      <span class="d-flex flex-justify-between width-full width-md-auto">
        
<details class="details-reset details-overlay branch-select-menu " id="branch-select-menu">
  <summary class="btn css-truncate btn-sm"
           data-hotkey="w"
           title="Switch branches or tags">
    <i>Branch:</i>
    <span class="css-truncate-target" data-menu-button>master</span>
    <span class="dropdown-caret"></span>
  </summary>

  <details-menu class="SelectMenu SelectMenu--hasFilter" src="/hpc-thai/HPCThai/refs/master/introHPC/07/bern_amdahl.cpp?source_action=show&source_controller=blob" preload>
    <div class="SelectMenu-modal">
      <include-fragment class="SelectMenu-loading" aria-label="Menu is loading">
        <svg class="octicon octicon-octoface anim-pulse" height="32" viewBox="0 0 16 16" version="1.1" width="32" aria-hidden="true"><path fill-rule="evenodd" d="M14.7 5.34c.13-.32.55-1.59-.13-3.31 0 0-1.05-.33-3.44 1.3-1-.28-2.07-.32-3.13-.32s-2.13.04-3.13.32c-2.39-1.64-3.44-1.3-3.44-1.3-.68 1.72-.26 2.99-.13 3.31C.49 6.21 0 7.33 0 8.69 0 13.84 3.33 15 7.98 15S16 13.84 16 8.69c0-1.36-.49-2.48-1.3-3.35zM8 14.02c-3.3 0-5.98-.15-5.98-3.35 0-.76.38-1.48 1.02-2.07 1.07-.98 2.9-.46 4.96-.46 2.07 0 3.88-.52 4.96.46.65.59 1.02 1.3 1.02 2.07 0 3.19-2.68 3.35-5.98 3.35zM5.49 9.01c-.66 0-1.2.8-1.2 1.78s.54 1.79 1.2 1.79c.66 0 1.2-.8 1.2-1.79s-.54-1.78-1.2-1.78zm5.02 0c-.66 0-1.2.79-1.2 1.78s.54 1.79 1.2 1.79c.66 0 1.2-.8 1.2-1.79s-.53-1.78-1.2-1.78z"></path></svg>
      </include-fragment>
    </div>
  </details-menu>
</details>

        <div class="BtnGroup flex-shrink-0 d-md-none">
          <a href="/hpc-thai/HPCThai/find/master"
                class="js-pjax-capture-input btn btn-sm BtnGroup-item"
                data-pjax
                data-hotkey="t">
            Find file
          </a>
          <clipboard-copy value="introHPC/07/bern_amdahl.cpp" class="btn btn-sm BtnGroup-item">
            Copy path
          </clipboard-copy>
        </div>
      </span>
      <h2 id="blob-path" class="breadcrumb flex-auto min-width-0 text-normal flex-md-self-center ml-md-2 mr-md-3 my-2 my-md-0">
        <span class="js-repo-root text-bold"><span class="js-path-segment d-inline-block wb-break-all"><a data-pjax="true" href="/hpc-thai/HPCThai"><span>HPCThai</span></a></span></span><span class="separator">/</span><span class="js-path-segment d-inline-block wb-break-all"><a data-pjax="true" href="/hpc-thai/HPCThai/tree/master/introHPC"><span>introHPC</span></a></span><span class="separator">/</span><span class="js-path-segment d-inline-block wb-break-all"><a data-pjax="true" href="/hpc-thai/HPCThai/tree/master/introHPC/07"><span>07</span></a></span><span class="separator">/</span><strong class="final-path">bern_amdahl.cpp</strong>
      </h2>

      <div class="BtnGroup flex-shrink-0 d-none d-md-inline-block">
        <a href="/hpc-thai/HPCThai/find/master"
              class="js-pjax-capture-input btn btn-sm BtnGroup-item"
              data-pjax
              data-hotkey="t">
          Find file
        </a>
        <clipboard-copy value="introHPC/07/bern_amdahl.cpp" class="btn btn-sm BtnGroup-item">
          Copy path
        </clipboard-copy>
      </div>
    </div>



    <include-fragment src="/hpc-thai/HPCThai/contributors/master/introHPC/07/bern_amdahl.cpp" class="Box Box--condensed commit-loader">
      <div class="Box-body bg-blue-light f6">
        Fetching contributors…
      </div>

      <div class="Box-body d-flex flex-items-center" >
        <img alt="" class="loader-loading mr-2" src="https://github.githubassets.com/images/spinners/octocat-spinner-32-EAF2F5.gif" width="16" height="16" />
        <span class="text-red h6 loader-error">Cannot retrieve contributors at this time</span>
      </div>
</include-fragment>





    <div class="Box mt-3 position-relative
      ">
      
<div class="Box-header py-2 d-flex flex-column flex-shrink-0 flex-md-row flex-md-items-center">
  <div class="text-mono f6 flex-auto pr-3 flex-order-2 flex-md-order-1 mt-2 mt-md-0">

      261 lines (228 sloc)
      <span class="file-info-divider"></span>
    6.26 KB
  </div>

  <div class="d-flex py-1 py-md-0 flex-auto flex-order-1 flex-md-order-2 flex-sm-grow-0 flex-justify-between">

    <div class="BtnGroup">
      <a id="raw-url" class="btn btn-sm BtnGroup-item" href="/hpc-thai/HPCThai/raw/master/introHPC/07/bern_amdahl.cpp">Raw</a>
        <a class="btn btn-sm js-update-url-with-hash BtnGroup-item" data-hotkey="b" href="/hpc-thai/HPCThai/blame/master/introHPC/07/bern_amdahl.cpp">Blame</a>
      <a rel="nofollow" class="btn btn-sm BtnGroup-item" href="/hpc-thai/HPCThai/commits/master/introHPC/07/bern_amdahl.cpp">History</a>
    </div>


    <div>
          <a class="btn-octicon tooltipped tooltipped-nw js-remove-unless-platform"
             data-platforms="windows,mac"
             href="https://desktop.github.com"
             aria-label="Open this file in GitHub Desktop"
             data-ga-click="Repository, open with desktop">
              <svg class="octicon octicon-device-desktop" viewBox="0 0 16 16" version="1.1" width="16" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M15 2H1c-.55 0-1 .45-1 1v9c0 .55.45 1 1 1h5.34c-.25.61-.86 1.39-2.34 2h8c-1.48-.61-2.09-1.39-2.34-2H15c.55 0 1-.45 1-1V3c0-.55-.45-1-1-1zm0 9H1V3h14v8z"></path></svg>
          </a>

          <button type="button" class="btn-octicon disabled tooltipped tooltipped-nw"
            aria-label="You must be signed in to make or propose changes">
            <svg class="octicon octicon-pencil" viewBox="0 0 14 16" version="1.1" width="14" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M0 12v3h3l8-8-3-3-8 8zm3 2H1v-2h1v1h1v1zm10.3-9.3L12 6 9 3l1.3-1.3a.996.996 0 011.41 0l1.59 1.59c.39.39.39 1.02 0 1.41z"></path></svg>
          </button>
          <button type="button" class="btn-octicon btn-octicon-danger disabled tooltipped tooltipped-nw"
            aria-label="You must be signed in to make or propose changes">
            <svg class="octicon octicon-trashcan" viewBox="0 0 12 16" version="1.1" width="12" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M11 2H9c0-.55-.45-1-1-1H5c-.55 0-1 .45-1 1H2c-.55 0-1 .45-1 1v1c0 .55.45 1 1 1v9c0 .55.45 1 1 1h7c.55 0 1-.45 1-1V5c.55 0 1-.45 1-1V3c0-.55-.45-1-1-1zm-1 12H3V5h1v8h1V5h1v8h1V5h1v8h1V5h1v9zm1-10H2V3h9v1z"></path></svg>
          </button>
    </div>
  </div>
</div>



      

  <div itemprop="text" class="Box-body p-0 blob-wrapper data type-c ">
      
<table class="highlight tab-size js-file-line-container" data-tab-size="8" data-paste-markdown-skip>
      <tr>
        <td id="L1" class="blob-num js-line-number" data-line-number="1"></td>
        <td id="LC1" class="blob-code blob-code-inner js-file-line">#<span class="pl-k">include</span> <span class="pl-s"><span class="pl-pds"><</span>iostream<span class="pl-pds">></span></span></td>
      </tr>
      <tr>
        <td id="L2" class="blob-num js-line-number" data-line-number="2"></td>
        <td id="LC2" class="blob-code blob-code-inner js-file-line">#<span class="pl-k">include</span> <span class="pl-s"><span class="pl-pds"><</span>vector<span class="pl-pds">></span></span></td>
      </tr>
      <tr>
        <td id="L3" class="blob-num js-line-number" data-line-number="3"></td>
        <td id="LC3" class="blob-code blob-code-inner js-file-line">#<span class="pl-k">include</span> <span class="pl-s"><span class="pl-pds"><</span>cmath<span class="pl-pds">></span></span></td>
      </tr>
      <tr>
        <td id="L4" class="blob-num js-line-number" data-line-number="4"></td>
        <td id="LC4" class="blob-code blob-code-inner js-file-line">#<span class="pl-k">include</span> <span class="pl-s"><span class="pl-pds"><</span>gmpxx.h<span class="pl-pds">></span></span></td>
      </tr>
      <tr>
        <td id="L5" class="blob-num js-line-number" data-line-number="5"></td>
        <td id="LC5" class="blob-code blob-code-inner js-file-line">#<span class="pl-k">include</span> <span class="pl-s"><span class="pl-pds"><</span>tuple<span class="pl-pds">></span></span></td>
      </tr>
      <tr>
        <td id="L6" class="blob-num js-line-number" data-line-number="6"></td>
        <td id="LC6" class="blob-code blob-code-inner js-file-line">#<span class="pl-k">include</span> <span class="pl-s"><span class="pl-pds"><</span>stack<span class="pl-pds">></span></span></td>
      </tr>
      <tr>
        <td id="L7" class="blob-num js-line-number" data-line-number="7"></td>
        <td id="LC7" class="blob-code blob-code-inner js-file-line">#<span class="pl-k">include</span> <span class="pl-s"><span class="pl-pds"><</span>utility<span class="pl-pds">></span></span></td>
      </tr>
      <tr>
        <td id="L8" class="blob-num js-line-number" data-line-number="8"></td>
        <td id="LC8" class="blob-code blob-code-inner js-file-line">#<span class="pl-k">include</span> <span class="pl-s"><span class="pl-pds"><</span>deque<span class="pl-pds">></span></span></td>
      </tr>
      <tr>
        <td id="L9" class="blob-num js-line-number" data-line-number="9"></td>
        <td id="LC9" class="blob-code blob-code-inner js-file-line">#<span class="pl-k">include</span> <span class="pl-s"><span class="pl-pds"><</span>chrono<span class="pl-pds">></span></span></td>
      </tr>
      <tr>
        <td id="L10" class="blob-num js-line-number" data-line-number="10"></td>
        <td id="LC10" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L11" class="blob-num js-line-number" data-line-number="11"></td>
        <td id="LC11" class="blob-code blob-code-inner js-file-line"><span class="pl-k">using</span> <span class="pl-k">namespace</span> <span class="pl-en">std</span><span class="pl-k">;</span></td>
      </tr>
      <tr>
        <td id="L12" class="blob-num js-line-number" data-line-number="12"></td>
        <td id="LC12" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L13" class="blob-num js-line-number" data-line-number="13"></td>
        <td id="LC13" class="blob-code blob-code-inner js-file-line"><span class="pl-k">class</span> <span class="pl-en">PrimeTable</span></td>
      </tr>
      <tr>
        <td id="L14" class="blob-num js-line-number" data-line-number="14"></td>
        <td id="LC14" class="blob-code blob-code-inner js-file-line">{</td>
      </tr>
      <tr>
        <td id="L15" class="blob-num js-line-number" data-line-number="15"></td>
        <td id="LC15" class="blob-code blob-code-inner js-file-line"><span class="pl-k">public:</span></td>
      </tr>
      <tr>
        <td id="L16" class="blob-num js-line-number" data-line-number="16"></td>
        <td id="LC16" class="blob-code blob-code-inner js-file-line">    <span class="pl-en">PrimeTable</span>(<span class="pl-k">const</span> <span class="pl-k">long</span> &size) : _size {size}, _table (size, <span class="pl-c1">true</span>) {</td>
      </tr>
      <tr>
        <td id="L17" class="blob-num js-line-number" data-line-number="17"></td>
        <td id="LC17" class="blob-code blob-code-inner js-file-line">        _table[<span class="pl-c1">0</span>] = _table[<span class="pl-c1">1</span>] = <span class="pl-c1">false</span>;</td>
      </tr>
      <tr>
        <td id="L18" class="blob-num js-line-number" data-line-number="18"></td>
        <td id="LC18" class="blob-code blob-code-inner js-file-line">        <span class="pl-k">const</span> <span class="pl-k">long</span> limit = (<span class="pl-k">long</span>)<span class="pl-c1">sqrt</span>(size);</td>
      </tr>
      <tr>
        <td id="L19" class="blob-num js-line-number" data-line-number="19"></td>
        <td id="LC19" class="blob-code blob-code-inner js-file-line">        <span class="pl-k">for</span> (<span class="pl-k">long</span> i=<span class="pl-c1">2</span>; i<=limit; i++) {</td>
      </tr>
      <tr>
        <td id="L20" class="blob-num js-line-number" data-line-number="20"></td>
        <td id="LC20" class="blob-code blob-code-inner js-file-line">            <span class="pl-k">if</span> (_table[i] == <span class="pl-c1">false</span>) <span class="pl-k">continue</span>;</td>
      </tr>
      <tr>
        <td id="L21" class="blob-num js-line-number" data-line-number="21"></td>
        <td id="LC21" class="blob-code blob-code-inner js-file-line">            <span class="pl-k">for</span> (<span class="pl-k">long</span> r=i+i; r<=size; r+=i) _table[r] = <span class="pl-c1">false</span>;</td>
      </tr>
      <tr>
        <td id="L22" class="blob-num js-line-number" data-line-number="22"></td>
        <td id="LC22" class="blob-code blob-code-inner js-file-line">        }</td>
      </tr>
      <tr>
        <td id="L23" class="blob-num js-line-number" data-line-number="23"></td>
        <td id="LC23" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L24" class="blob-num js-line-number" data-line-number="24"></td>
        <td id="LC24" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L25" class="blob-num js-line-number" data-line-number="25"></td>
        <td id="LC25" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">long</span> <span class="pl-en">nextPrime</span>(<span class="pl-k">long</span> pos) {</td>
      </tr>
      <tr>
        <td id="L26" class="blob-num js-line-number" data-line-number="26"></td>
        <td id="LC26" class="blob-code blob-code-inner js-file-line">        <span class="pl-k">for</span> (<span class="pl-k">long</span> i=pos+<span class="pl-c1">1</span>; i<=_size; i++) {</td>
      </tr>
      <tr>
        <td id="L27" class="blob-num js-line-number" data-line-number="27"></td>
        <td id="LC27" class="blob-code blob-code-inner js-file-line">            <span class="pl-k">if</span> (_table[i] == <span class="pl-c1">true</span>) <span class="pl-k">return</span> i;</td>
      </tr>
      <tr>
        <td id="L28" class="blob-num js-line-number" data-line-number="28"></td>
        <td id="LC28" class="blob-code blob-code-inner js-file-line">        }</td>
      </tr>
      <tr>
        <td id="L29" class="blob-num js-line-number" data-line-number="29"></td>
        <td id="LC29" class="blob-code blob-code-inner js-file-line">        <span class="pl-k">return</span> -<span class="pl-c1">1</span>;</td>
      </tr>
      <tr>
        <td id="L30" class="blob-num js-line-number" data-line-number="30"></td>
        <td id="LC30" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L31" class="blob-num js-line-number" data-line-number="31"></td>
        <td id="LC31" class="blob-code blob-code-inner js-file-line"><span class="pl-k">private:</span></td>
      </tr>
      <tr>
        <td id="L32" class="blob-num js-line-number" data-line-number="32"></td>
        <td id="LC32" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">long</span> _size;</td>
      </tr>
      <tr>
        <td id="L33" class="blob-num js-line-number" data-line-number="33"></td>
        <td id="LC33" class="blob-code blob-code-inner js-file-line">    std::vector<<span class="pl-k">bool</span>> _table;</td>
      </tr>
      <tr>
        <td id="L34" class="blob-num js-line-number" data-line-number="34"></td>
        <td id="LC34" class="blob-code blob-code-inner js-file-line">};</td>
      </tr>
      <tr>
        <td id="L35" class="blob-num js-line-number" data-line-number="35"></td>
        <td id="LC35" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L36" class="blob-num js-line-number" data-line-number="36"></td>
        <td id="LC36" class="blob-code blob-code-inner js-file-line"><span class="pl-k">auto</span> <span class="pl-en">computeDk</span>(<span class="pl-k">const</span> <span class="pl-k">int</span> &k, PrimeTable& primeTable) -> mpz_class</td>
      </tr>
      <tr>
        <td id="L37" class="blob-num js-line-number" data-line-number="37"></td>
        <td id="LC37" class="blob-code blob-code-inner js-file-line">{</td>
      </tr>
      <tr>
        <td id="L38" class="blob-num js-line-number" data-line-number="38"></td>
        <td id="LC38" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">long</span> p {<span class="pl-c1">2</span>};</td>
      </tr>
      <tr>
        <td id="L39" class="blob-num js-line-number" data-line-number="39"></td>
        <td id="LC39" class="blob-code blob-code-inner js-file-line">    mpz_class dk {<span class="pl-c1">1</span>};</td>
      </tr>
      <tr>
        <td id="L40" class="blob-num js-line-number" data-line-number="40"></td>
        <td id="LC40" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">while</span> (p != -<span class="pl-c1">1</span>) {</td>
      </tr>
      <tr>
        <td id="L41" class="blob-num js-line-number" data-line-number="41"></td>
        <td id="LC41" class="blob-code blob-code-inner js-file-line">        <span class="pl-k">if</span> (k % (p-<span class="pl-c1">1</span>) == <span class="pl-c1">0</span>) dk *= p;</td>
      </tr>
      <tr>
        <td id="L42" class="blob-num js-line-number" data-line-number="42"></td>
        <td id="LC42" class="blob-code blob-code-inner js-file-line">        p = primeTable.<span class="pl-c1">nextPrime</span>(p);</td>
      </tr>
      <tr>
        <td id="L43" class="blob-num js-line-number" data-line-number="43"></td>
        <td id="LC43" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L44" class="blob-num js-line-number" data-line-number="44"></td>
        <td id="LC44" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">return</span> <span class="pl-c1">std::move</span>(dk);</td>
      </tr>
      <tr>
        <td id="L45" class="blob-num js-line-number" data-line-number="45"></td>
        <td id="LC45" class="blob-code blob-code-inner js-file-line">}</td>
      </tr>
      <tr>
        <td id="L46" class="blob-num js-line-number" data-line-number="46"></td>
        <td id="LC46" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L47" class="blob-num js-line-number" data-line-number="47"></td>
        <td id="LC47" class="blob-code blob-code-inner js-file-line"><span class="pl-k">auto</span> <span class="pl-en">norm</span>(mpz_class b, mpz_class p) -> mpz_class</td>
      </tr>
      <tr>
        <td id="L48" class="blob-num js-line-number" data-line-number="48"></td>
        <td id="LC48" class="blob-code blob-code-inner js-file-line">{</td>
      </tr>
      <tr>
        <td id="L49" class="blob-num js-line-number" data-line-number="49"></td>
        <td id="LC49" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">while</span> (<span class="pl-c1">true</span>) {</td>
      </tr>
      <tr>
        <td id="L50" class="blob-num js-line-number" data-line-number="50"></td>
        <td id="LC50" class="blob-code blob-code-inner js-file-line">        <span class="pl-k">if</span> (b < <span class="pl-c1">0</span>) b += p;</td>
      </tr>
      <tr>
        <td id="L51" class="blob-num js-line-number" data-line-number="51"></td>
        <td id="LC51" class="blob-code blob-code-inner js-file-line">        <span class="pl-k">else</span> <span class="pl-k">if</span> (b > p) b -= p;</td>
      </tr>
      <tr>
        <td id="L52" class="blob-num js-line-number" data-line-number="52"></td>
        <td id="LC52" class="blob-code blob-code-inner js-file-line">        <span class="pl-k">else</span> <span class="pl-k">break</span>;</td>
      </tr>
      <tr>
        <td id="L53" class="blob-num js-line-number" data-line-number="53"></td>
        <td id="LC53" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L54" class="blob-num js-line-number" data-line-number="54"></td>
        <td id="LC54" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">return</span> b;</td>
      </tr>
      <tr>
        <td id="L55" class="blob-num js-line-number" data-line-number="55"></td>
        <td id="LC55" class="blob-code blob-code-inner js-file-line">}</td>
      </tr>
      <tr>
        <td id="L56" class="blob-num js-line-number" data-line-number="56"></td>
        <td id="LC56" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L57" class="blob-num js-line-number" data-line-number="57"></td>
        <td id="LC57" class="blob-code blob-code-inner js-file-line"><span class="pl-k">auto</span> <span class="pl-en">computePowerMod</span>(<span class="pl-k">const</span> mpz_class &a, <span class="pl-k">const</span> <span class="pl-k">long</span> &k, <span class="pl-k">const</span> mpz_class &m) -> mpz_class</td>
      </tr>
      <tr>
        <td id="L58" class="blob-num js-line-number" data-line-number="58"></td>
        <td id="LC58" class="blob-code blob-code-inner js-file-line">{</td>
      </tr>
      <tr>
        <td id="L59" class="blob-num js-line-number" data-line-number="59"></td>
        <td id="LC59" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">int</span> <span class="pl-c1">index</span> = <span class="pl-c1">log2</span>(k);</td>
      </tr>
      <tr>
        <td id="L60" class="blob-num js-line-number" data-line-number="60"></td>
        <td id="LC60" class="blob-code blob-code-inner js-file-line">    mpz_class powmod = <span class="pl-c1">1</span>, powa = a, pow2 = <span class="pl-c1">1</span>;</td>
      </tr>
      <tr>
        <td id="L61" class="blob-num js-line-number" data-line-number="61"></td>
        <td id="LC61" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L62" class="blob-num js-line-number" data-line-number="62"></td>
        <td id="LC62" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">for</span> (<span class="pl-k">int</span> i=<span class="pl-c1">0</span>; i<=<span class="pl-c1">index</span>; i++) {</td>
      </tr>
      <tr>
        <td id="L63" class="blob-num js-line-number" data-line-number="63"></td>
        <td id="LC63" class="blob-code blob-code-inner js-file-line">        <span class="pl-k">if</span> ( (k & pow2) != <span class="pl-c1">0</span>) powmod *= powa;</td>
      </tr>
      <tr>
        <td id="L64" class="blob-num js-line-number" data-line-number="64"></td>
        <td id="LC64" class="blob-code blob-code-inner js-file-line">        powa = (powa * powa) % m;</td>
      </tr>
      <tr>
        <td id="L65" class="blob-num js-line-number" data-line-number="65"></td>
        <td id="LC65" class="blob-code blob-code-inner js-file-line">        pow2 <<= <span class="pl-c1">1</span>;</td>
      </tr>
      <tr>
        <td id="L66" class="blob-num js-line-number" data-line-number="66"></td>
        <td id="LC66" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L67" class="blob-num js-line-number" data-line-number="67"></td>
        <td id="LC67" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">return</span> <span class="pl-c1">norm</span>(powmod % m, m);</td>
      </tr>
      <tr>
        <td id="L68" class="blob-num js-line-number" data-line-number="68"></td>
        <td id="LC68" class="blob-code blob-code-inner js-file-line">}</td>
      </tr>
      <tr>
        <td id="L69" class="blob-num js-line-number" data-line-number="69"></td>
        <td id="LC69" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L70" class="blob-num js-line-number" data-line-number="70"></td>
        <td id="LC70" class="blob-code blob-code-inner js-file-line"><span class="pl-k">auto</span> <span class="pl-en">computeInvertMod</span>(<span class="pl-k">const</span> mpz_class &n, mpz_class p) -> mpz_class</td>
      </tr>
      <tr>
        <td id="L71" class="blob-num js-line-number" data-line-number="71"></td>
        <td id="LC71" class="blob-code blob-code-inner js-file-line">{</td>
      </tr>
      <tr>
        <td id="L72" class="blob-num js-line-number" data-line-number="72"></td>
        <td id="LC72" class="blob-code blob-code-inner js-file-line">    stack<tuple<mpz_class, mpz_class, mpz_class>> v;</td>
      </tr>
      <tr>
        <td id="L73" class="blob-num js-line-number" data-line-number="73"></td>
        <td id="LC73" class="blob-code blob-code-inner js-file-line">    mpz_class a = p;</td>
      </tr>
      <tr>
        <td id="L74" class="blob-num js-line-number" data-line-number="74"></td>
        <td id="LC74" class="blob-code blob-code-inner js-file-line">    mpz_class b = n;</td>
      </tr>
      <tr>
        <td id="L75" class="blob-num js-line-number" data-line-number="75"></td>
        <td id="LC75" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">if</span> (n > p) {</td>
      </tr>
      <tr>
        <td id="L76" class="blob-num js-line-number" data-line-number="76"></td>
        <td id="LC76" class="blob-code blob-code-inner js-file-line">        a = n;</td>
      </tr>
      <tr>
        <td id="L77" class="blob-num js-line-number" data-line-number="77"></td>
        <td id="LC77" class="blob-code blob-code-inner js-file-line">        b = p;</td>
      </tr>
      <tr>
        <td id="L78" class="blob-num js-line-number" data-line-number="78"></td>
        <td id="LC78" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L79" class="blob-num js-line-number" data-line-number="79"></td>
        <td id="LC79" class="blob-code blob-code-inner js-file-line">    mpz_class d = a / b;</td>
      </tr>
      <tr>
        <td id="L80" class="blob-num js-line-number" data-line-number="80"></td>
        <td id="LC80" class="blob-code blob-code-inner js-file-line">    mpz_class r = a % b;</td>
      </tr>
      <tr>
        <td id="L81" class="blob-num js-line-number" data-line-number="81"></td>
        <td id="LC81" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L82" class="blob-num js-line-number" data-line-number="82"></td>
        <td id="LC82" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">while</span> (r > <span class="pl-c1">1</span>) {</td>
      </tr>
      <tr>
        <td id="L83" class="blob-num js-line-number" data-line-number="83"></td>
        <td id="LC83" class="blob-code blob-code-inner js-file-line">        v.<span class="pl-c1">push</span>(<span class="pl-c1">make_tuple</span>(a, b, -d));</td>
      </tr>
      <tr>
        <td id="L84" class="blob-num js-line-number" data-line-number="84"></td>
        <td id="LC84" class="blob-code blob-code-inner js-file-line">        a = b;</td>
      </tr>
      <tr>
        <td id="L85" class="blob-num js-line-number" data-line-number="85"></td>
        <td id="LC85" class="blob-code blob-code-inner js-file-line">        b = r;</td>
      </tr>
      <tr>
        <td id="L86" class="blob-num js-line-number" data-line-number="86"></td>
        <td id="LC86" class="blob-code blob-code-inner js-file-line">        d = a / b;</td>
      </tr>
      <tr>
        <td id="L87" class="blob-num js-line-number" data-line-number="87"></td>
        <td id="LC87" class="blob-code blob-code-inner js-file-line">        r = a % b;</td>
      </tr>
      <tr>
        <td id="L88" class="blob-num js-line-number" data-line-number="88"></td>
        <td id="LC88" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L89" class="blob-num js-line-number" data-line-number="89"></td>
        <td id="LC89" class="blob-code blob-code-inner js-file-line">    mpz_class m1 = <span class="pl-c1">1</span>, m2 = -d;</td>
      </tr>
      <tr>
        <td id="L90" class="blob-num js-line-number" data-line-number="90"></td>
        <td id="LC90" class="blob-code blob-code-inner js-file-line">    mpz_class aa = a, bb = b;</td>
      </tr>
      <tr>
        <td id="L91" class="blob-num js-line-number" data-line-number="91"></td>
        <td id="LC91" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L92" class="blob-num js-line-number" data-line-number="92"></td>
        <td id="LC92" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">while</span> (!v.<span class="pl-c1">empty</span>()) {</td>
      </tr>
      <tr>
        <td id="L93" class="blob-num js-line-number" data-line-number="93"></td>
        <td id="LC93" class="blob-code blob-code-inner js-file-line">        <span class="pl-k">auto</span> t = v.<span class="pl-c1">top</span>();</td>
      </tr>
      <tr>
        <td id="L94" class="blob-num js-line-number" data-line-number="94"></td>
        <td id="LC94" class="blob-code blob-code-inner js-file-line">        v.<span class="pl-c1">pop</span>();</td>
      </tr>
      <tr>
        <td id="L95" class="blob-num js-line-number" data-line-number="95"></td>
        <td id="LC95" class="blob-code blob-code-inner js-file-line">        a = get<<span class="pl-c1">0</span>>(t);</td>
      </tr>
      <tr>
        <td id="L96" class="blob-num js-line-number" data-line-number="96"></td>
        <td id="LC96" class="blob-code blob-code-inner js-file-line">        b = get<<span class="pl-c1">1</span>>(t);</td>
      </tr>
      <tr>
        <td id="L97" class="blob-num js-line-number" data-line-number="97"></td>
        <td id="LC97" class="blob-code blob-code-inner js-file-line">        d = get<<span class="pl-c1">2</span>>(t);</td>
      </tr>
      <tr>
        <td id="L98" class="blob-num js-line-number" data-line-number="98"></td>
        <td id="LC98" class="blob-code blob-code-inner js-file-line">        m1 += (m2 * d);</td>
      </tr>
      <tr>
        <td id="L99" class="blob-num js-line-number" data-line-number="99"></td>
        <td id="LC99" class="blob-code blob-code-inner js-file-line">        bb = a;</td>
      </tr>
      <tr>
        <td id="L100" class="blob-num js-line-number" data-line-number="100"></td>
        <td id="LC100" class="blob-code blob-code-inner js-file-line">        <span class="pl-c1">swap</span>(m1, m2);</td>
      </tr>
      <tr>
        <td id="L101" class="blob-num js-line-number" data-line-number="101"></td>
        <td id="LC101" class="blob-code blob-code-inner js-file-line">        <span class="pl-c1">swap</span>(aa, bb);</td>
      </tr>
      <tr>
        <td id="L102" class="blob-num js-line-number" data-line-number="102"></td>
        <td id="LC102" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L103" class="blob-num js-line-number" data-line-number="103"></td>
        <td id="LC103" class="blob-code blob-code-inner js-file-line">    mpz_class rr = (n == aa)? m1 : m2;</td>
      </tr>
      <tr>
        <td id="L104" class="blob-num js-line-number" data-line-number="104"></td>
        <td id="LC104" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">return</span> <span class="pl-c1">norm</span>(rr, p);</td>
      </tr>
      <tr>
        <td id="L105" class="blob-num js-line-number" data-line-number="105"></td>
        <td id="LC105" class="blob-code blob-code-inner js-file-line">}</td>
      </tr>
      <tr>
        <td id="L106" class="blob-num js-line-number" data-line-number="106"></td>
        <td id="LC106" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L107" class="blob-num js-line-number" data-line-number="107"></td>
        <td id="LC107" class="blob-code blob-code-inner js-file-line"><span class="pl-k">auto</span> <span class="pl-en">computeOrderEp</span>(<span class="pl-k">const</span> <span class="pl-k">long</span> &a, <span class="pl-k">const</span> <span class="pl-k">long</span> &p) -> long</td>
      </tr>
      <tr>
        <td id="L108" class="blob-num js-line-number" data-line-number="108"></td>
        <td id="LC108" class="blob-code blob-code-inner js-file-line">{</td>
      </tr>
      <tr>
        <td id="L109" class="blob-num js-line-number" data-line-number="109"></td>
        <td id="LC109" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">for</span> (<span class="pl-k">long</span> k=<span class="pl-c1">1</span>; k<p; k++) {</td>
      </tr>
      <tr>
        <td id="L110" class="blob-num js-line-number" data-line-number="110"></td>
        <td id="LC110" class="blob-code blob-code-inner js-file-line">        <span class="pl-k">if</span> (<span class="pl-c1">computePowerMod</span>(a, k, p) == <span class="pl-c1">1</span>) <span class="pl-k">return</span> k;</td>
      </tr>
      <tr>
        <td id="L111" class="blob-num js-line-number" data-line-number="111"></td>
        <td id="LC111" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L112" class="blob-num js-line-number" data-line-number="112"></td>
        <td id="LC112" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">throw</span> <span class="pl-s"><span class="pl-pds">"</span>computeOrderEp error<span class="pl-pds">"</span></span>;</td>
      </tr>
      <tr>
        <td id="L113" class="blob-num js-line-number" data-line-number="113"></td>
        <td id="LC113" class="blob-code blob-code-inner js-file-line">}</td>
      </tr>
      <tr>
        <td id="L114" class="blob-num js-line-number" data-line-number="114"></td>
        <td id="LC114" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L115" class="blob-num js-line-number" data-line-number="115"></td>
        <td id="LC115" class="blob-code blob-code-inner js-file-line"><span class="pl-k">auto</span> <span class="pl-en">computePrimitiveRoot</span>(<span class="pl-k">const</span> <span class="pl-k">long</span> &p) -> long</td>
      </tr>
      <tr>
        <td id="L116" class="blob-num js-line-number" data-line-number="116"></td>
        <td id="LC116" class="blob-code blob-code-inner js-file-line">{</td>
      </tr>
      <tr>
        <td id="L117" class="blob-num js-line-number" data-line-number="117"></td>
        <td id="LC117" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">if</span> (p == <span class="pl-c1">2</span>) <span class="pl-k">return</span> <span class="pl-c1">1</span>;</td>
      </tr>
      <tr>
        <td id="L118" class="blob-num js-line-number" data-line-number="118"></td>
        <td id="LC118" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">for</span> (<span class="pl-k">int</span> g=<span class="pl-c1">2</span>; g<p; g++) {</td>
      </tr>
      <tr>
        <td id="L119" class="blob-num js-line-number" data-line-number="119"></td>
        <td id="LC119" class="blob-code blob-code-inner js-file-line">        <span class="pl-k">if</span> (<span class="pl-c1">computeOrderEp</span>(g, p) == (p - <span class="pl-c1">1</span>)) <span class="pl-k">return</span> g;</td>
      </tr>
      <tr>
        <td id="L120" class="blob-num js-line-number" data-line-number="120"></td>
        <td id="LC120" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L121" class="blob-num js-line-number" data-line-number="121"></td>
        <td id="LC121" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">throw</span> <span class="pl-s"><span class="pl-pds">"</span>computePrimitiveRoot error<span class="pl-pds">"</span></span>;</td>
      </tr>
      <tr>
        <td id="L122" class="blob-num js-line-number" data-line-number="122"></td>
        <td id="LC122" class="blob-code blob-code-inner js-file-line">}</td>
      </tr>
      <tr>
        <td id="L123" class="blob-num js-line-number" data-line-number="123"></td>
        <td id="LC123" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L124" class="blob-num js-line-number" data-line-number="124"></td>
        <td id="LC124" class="blob-code blob-code-inner js-file-line"><span class="pl-k">auto</span> <span class="pl-en">computeBkModP</span>(<span class="pl-k">const</span> <span class="pl-k">long</span> &p, <span class="pl-k">const</span> <span class="pl-k">long</span> &k) -> mpz_class</td>
      </tr>
      <tr>
        <td id="L125" class="blob-num js-line-number" data-line-number="125"></td>
        <td id="LC125" class="blob-code blob-code-inner js-file-line">{</td>
      </tr>
      <tr>
        <td id="L126" class="blob-num js-line-number" data-line-number="126"></td>
        <td id="LC126" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">if</span> (k == <span class="pl-c1">0</span>) <span class="pl-k">return</span> <span class="pl-c1">1</span>;</td>
      </tr>
      <tr>
        <td id="L127" class="blob-num js-line-number" data-line-number="127"></td>
        <td id="LC127" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">if</span> (k == <span class="pl-c1">1</span>) <span class="pl-k">return</span> (p == <span class="pl-c1">2</span>)? -<span class="pl-c1">1</span> : (p-<span class="pl-c1">1</span>)/<span class="pl-c1">2</span>;</td>
      </tr>
      <tr>
        <td id="L128" class="blob-num js-line-number" data-line-number="128"></td>
        <td id="LC128" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">if</span> (k &  <span class="pl-c1">1</span>) <span class="pl-k">return</span> <span class="pl-c1">0</span>;</td>
      </tr>
      <tr>
        <td id="L129" class="blob-num js-line-number" data-line-number="129"></td>
        <td id="LC129" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">if</span> (p <= <span class="pl-c1">3</span>) <span class="pl-k">return</span> -<span class="pl-c1">1</span>;</td>
      </tr>
      <tr>
        <td id="L130" class="blob-num js-line-number" data-line-number="130"></td>
        <td id="LC130" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L131" class="blob-num js-line-number" data-line-number="131"></td>
        <td id="LC131" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">long</span> m = k % (p-<span class="pl-c1">1</span>);</td>
      </tr>
      <tr>
        <td id="L132" class="blob-num js-line-number" data-line-number="132"></td>
        <td id="LC132" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">if</span> (m == <span class="pl-c1">0</span>) <span class="pl-k">return</span> -<span class="pl-c1">1</span>;</td>
      </tr>
      <tr>
        <td id="L133" class="blob-num js-line-number" data-line-number="133"></td>
        <td id="LC133" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L134" class="blob-num js-line-number" data-line-number="134"></td>
        <td id="LC134" class="blob-code blob-code-inner js-file-line">    mpz_class g = <span class="pl-c1">computePrimitiveRoot</span>(p);</td>
      </tr>
      <tr>
        <td id="L135" class="blob-num js-line-number" data-line-number="135"></td>
        <td id="LC135" class="blob-code blob-code-inner js-file-line">    mpz_class r = <span class="pl-c1">computePowerMod</span>(g, k-<span class="pl-c1">1</span>, p);</td>
      </tr>
      <tr>
        <td id="L136" class="blob-num js-line-number" data-line-number="136"></td>
        <td id="LC136" class="blob-code blob-code-inner js-file-line">    mpz_class u = (g + ((g % <span class="pl-c1">2</span> == <span class="pl-c1">1</span>)? <span class="pl-c1">0</span> : p) - <span class="pl-c1">1</span>) / <span class="pl-c1">2</span>;</td>
      </tr>
      <tr>
        <td id="L137" class="blob-num js-line-number" data-line-number="137"></td>
        <td id="LC137" class="blob-code blob-code-inner js-file-line">    mpz_class S = <span class="pl-c1">0</span>, X = <span class="pl-c1">1</span>, Y = r;</td>
      </tr>
      <tr>
        <td id="L138" class="blob-num js-line-number" data-line-number="138"></td>
        <td id="LC138" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L139" class="blob-num js-line-number" data-line-number="139"></td>
        <td id="LC139" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L140" class="blob-num js-line-number" data-line-number="140"></td>
        <td id="LC140" class="blob-code blob-code-inner js-file-line">    mpz_class hp = (p-<span class="pl-c1">1</span>)/<span class="pl-c1">2</span>, q, h, t;</td>
      </tr>
      <tr>
        <td id="L141" class="blob-num js-line-number" data-line-number="141"></td>
        <td id="LC141" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">for</span> (<span class="pl-k">long</span> i=<span class="pl-c1">1</span>; i<=hp; i++) {</td>
      </tr>
      <tr>
        <td id="L142" class="blob-num js-line-number" data-line-number="142"></td>
        <td id="LC142" class="blob-code blob-code-inner js-file-line">        q = <span class="pl-c1">norm</span>( (g*X)/p, p);</td>
      </tr>
      <tr>
        <td id="L143" class="blob-num js-line-number" data-line-number="143"></td>
        <td id="LC143" class="blob-code blob-code-inner js-file-line">        h = <span class="pl-c1">norm</span>( (q-u)%p, p);</td>
      </tr>
      <tr>
        <td id="L144" class="blob-num js-line-number" data-line-number="144"></td>
        <td id="LC144" class="blob-code blob-code-inner js-file-line">        t = <span class="pl-c1">norm</span>( (h*Y)%p, p);</td>
      </tr>
      <tr>
        <td id="L145" class="blob-num js-line-number" data-line-number="145"></td>
        <td id="LC145" class="blob-code blob-code-inner js-file-line">        S = <span class="pl-c1">norm</span>( (S-t)%p, p);</td>
      </tr>
      <tr>
        <td id="L146" class="blob-num js-line-number" data-line-number="146"></td>
        <td id="LC146" class="blob-code blob-code-inner js-file-line">        X = <span class="pl-c1">norm</span>( (g*X)%p, p);</td>
      </tr>
      <tr>
        <td id="L147" class="blob-num js-line-number" data-line-number="147"></td>
        <td id="LC147" class="blob-code blob-code-inner js-file-line">        Y = <span class="pl-c1">norm</span>( (r*Y)%p, p);</td>
      </tr>
      <tr>
        <td id="L148" class="blob-num js-line-number" data-line-number="148"></td>
        <td id="LC148" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L149" class="blob-num js-line-number" data-line-number="149"></td>
        <td id="LC149" class="blob-code blob-code-inner js-file-line">    mpz_class ans = <span class="pl-c1">computePowerMod</span>(g, k, p);</td>
      </tr>
      <tr>
        <td id="L150" class="blob-num js-line-number" data-line-number="150"></td>
        <td id="LC150" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L151" class="blob-num js-line-number" data-line-number="151"></td>
        <td id="LC151" class="blob-code blob-code-inner js-file-line">    ans = <span class="pl-c1">computeInvertMod</span>(p+<span class="pl-c1">1</span>-ans, p);</td>
      </tr>
      <tr>
        <td id="L152" class="blob-num js-line-number" data-line-number="152"></td>
        <td id="LC152" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L153" class="blob-num js-line-number" data-line-number="153"></td>
        <td id="LC153" class="blob-code blob-code-inner js-file-line">    ans = <span class="pl-c1">norm</span>( (S * ans) % p, p);</td>
      </tr>
      <tr>
        <td id="L154" class="blob-num js-line-number" data-line-number="154"></td>
        <td id="LC154" class="blob-code blob-code-inner js-file-line">    ans = <span class="pl-c1">norm</span>( (<span class="pl-c1">2</span> * ans) % p, p);</td>
      </tr>
      <tr>
        <td id="L155" class="blob-num js-line-number" data-line-number="155"></td>
        <td id="LC155" class="blob-code blob-code-inner js-file-line">    ans = <span class="pl-c1">norm</span>( (k * ans) % p, p);</td>
      </tr>
      <tr>
        <td id="L156" class="blob-num js-line-number" data-line-number="156"></td>
        <td id="LC156" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L157" class="blob-num js-line-number" data-line-number="157"></td>
        <td id="LC157" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">return</span> ans;</td>
      </tr>
      <tr>
        <td id="L158" class="blob-num js-line-number" data-line-number="158"></td>
        <td id="LC158" class="blob-code blob-code-inner js-file-line">}</td>
      </tr>
      <tr>
        <td id="L159" class="blob-num js-line-number" data-line-number="159"></td>
        <td id="LC159" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L160" class="blob-num js-line-number" data-line-number="160"></td>
        <td id="LC160" class="blob-code blob-code-inner js-file-line"><span class="pl-k">auto</span> <span class="pl-en">congruent</span>(<span class="pl-k">const</span> mpz_class &a, <span class="pl-k">const</span> mpz_class &b, <span class="pl-k">const</span> mpz_class &m) -> mpz_class</td>
      </tr>
      <tr>
        <td id="L161" class="blob-num js-line-number" data-line-number="161"></td>
        <td id="LC161" class="blob-code blob-code-inner js-file-line">{</td>
      </tr>
      <tr>
        <td id="L162" class="blob-num js-line-number" data-line-number="162"></td>
        <td id="LC162" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">if</span> (a == <span class="pl-c1">1</span> && b == <span class="pl-c1">1</span>) <span class="pl-k">return</span> mpz_class {<span class="pl-c1">1</span>};</td>
      </tr>
      <tr>
        <td id="L163" class="blob-num js-line-number" data-line-number="163"></td>
        <td id="LC163" class="blob-code blob-code-inner js-file-line">    mpz_class inv = <span class="pl-c1">computeInvertMod</span>(a, m);</td>
      </tr>
      <tr>
        <td id="L164" class="blob-num js-line-number" data-line-number="164"></td>
        <td id="LC164" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">return</span> (b * inv) % m;</td>
      </tr>
      <tr>
        <td id="L165" class="blob-num js-line-number" data-line-number="165"></td>
        <td id="LC165" class="blob-code blob-code-inner js-file-line">}</td>
      </tr>
      <tr>
        <td id="L166" class="blob-num js-line-number" data-line-number="166"></td>
        <td id="LC166" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L167" class="blob-num js-line-number" data-line-number="167"></td>
        <td id="LC167" class="blob-code blob-code-inner js-file-line"><span class="pl-k">auto</span> <span class="pl-en">computeCRT</span>(vector<tuple<mpz_class, <span class="pl-k">long</span>>> &residue) -> mpz_class</td>
      </tr>
      <tr>
        <td id="L168" class="blob-num js-line-number" data-line-number="168"></td>
        <td id="LC168" class="blob-code blob-code-inner js-file-line">{</td>
      </tr>
      <tr>
        <td id="L169" class="blob-num js-line-number" data-line-number="169"></td>
        <td id="LC169" class="blob-code blob-code-inner js-file-line">    mpz_class mul_m = <span class="pl-c1">1</span>;</td>
      </tr>
      <tr>
        <td id="L170" class="blob-num js-line-number" data-line-number="170"></td>
        <td id="LC170" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">for</span> (<span class="pl-k">auto</span> top : residue) {</td>
      </tr>
      <tr>
        <td id="L171" class="blob-num js-line-number" data-line-number="171"></td>
        <td id="LC171" class="blob-code blob-code-inner js-file-line">        mul_m *= get<<span class="pl-c1">1</span>>(top);</td>
      </tr>
      <tr>
        <td id="L172" class="blob-num js-line-number" data-line-number="172"></td>
        <td id="LC172" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L173" class="blob-num js-line-number" data-line-number="173"></td>
        <td id="LC173" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L174" class="blob-num js-line-number" data-line-number="174"></td>
        <td id="LC174" class="blob-code blob-code-inner js-file-line">    mpz_class z = <span class="pl-c1">0</span>, M, X, b, m;</td>
      </tr>
      <tr>
        <td id="L175" class="blob-num js-line-number" data-line-number="175"></td>
        <td id="LC175" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">for</span> (<span class="pl-k">auto</span> top : residue) {</td>
      </tr>
      <tr>
        <td id="L176" class="blob-num js-line-number" data-line-number="176"></td>
        <td id="LC176" class="blob-code blob-code-inner js-file-line">        b = get<<span class="pl-c1">0</span>>(top);</td>
      </tr>
      <tr>
        <td id="L177" class="blob-num js-line-number" data-line-number="177"></td>
        <td id="LC177" class="blob-code blob-code-inner js-file-line">        m = get<<span class="pl-c1">1</span>>(top);</td>
      </tr>
      <tr>
        <td id="L178" class="blob-num js-line-number" data-line-number="178"></td>
        <td id="LC178" class="blob-code blob-code-inner js-file-line">        M = mul_m / m;</td>
      </tr>
      <tr>
        <td id="L179" class="blob-num js-line-number" data-line-number="179"></td>
        <td id="LC179" class="blob-code blob-code-inner js-file-line">        X = <span class="pl-c1">congruent</span>(M, <span class="pl-c1">1</span>, m);</td>
      </tr>
      <tr>
        <td id="L180" class="blob-num js-line-number" data-line-number="180"></td>
        <td id="LC180" class="blob-code blob-code-inner js-file-line">        z += M * X * b;</td>
      </tr>
      <tr>
        <td id="L181" class="blob-num js-line-number" data-line-number="181"></td>
        <td id="LC181" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L182" class="blob-num js-line-number" data-line-number="182"></td>
        <td id="LC182" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">while</span> (z > <span class="pl-c1">0</span>) {</td>
      </tr>
      <tr>
        <td id="L183" class="blob-num js-line-number" data-line-number="183"></td>
        <td id="LC183" class="blob-code blob-code-inner js-file-line">        z -= mul_m;</td>
      </tr>
      <tr>
        <td id="L184" class="blob-num js-line-number" data-line-number="184"></td>
        <td id="LC184" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L185" class="blob-num js-line-number" data-line-number="185"></td>
        <td id="LC185" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">return</span> z + mul_m;</td>
      </tr>
      <tr>
        <td id="L186" class="blob-num js-line-number" data-line-number="186"></td>
        <td id="LC186" class="blob-code blob-code-inner js-file-line">}</td>
      </tr>
      <tr>
        <td id="L187" class="blob-num js-line-number" data-line-number="187"></td>
        <td id="LC187" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L188" class="blob-num js-line-number" data-line-number="188"></td>
        <td id="LC188" class="blob-code blob-code-inner js-file-line"><span class="pl-k">using</span> <span class="pl-c1">crt_t</span> = tuple<mpz_class, <span class="pl-k">long</span>>;</td>
      </tr>
      <tr>
        <td id="L189" class="blob-num js-line-number" data-line-number="189"></td>
        <td id="LC189" class="blob-code blob-code-inner js-file-line"><span class="pl-k">using</span> primeList_t = deque<<span class="pl-k">long</span>>;</td>
      </tr>
      <tr>
        <td id="L190" class="blob-num js-line-number" data-line-number="190"></td>
        <td id="LC190" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L191" class="blob-num js-line-number" data-line-number="191"></td>
        <td id="LC191" class="blob-code blob-code-inner js-file-line"><span class="pl-k">auto</span> <span class="pl-en">distribute</span>(<span class="pl-k">long</span> k, primeList_t primeList) -> vector<crt_t></td>
      </tr>
      <tr>
        <td id="L192" class="blob-num js-line-number" data-line-number="192"></td>
        <td id="LC192" class="blob-code blob-code-inner js-file-line">{</td>
      </tr>
      <tr>
        <td id="L193" class="blob-num js-line-number" data-line-number="193"></td>
        <td id="LC193" class="blob-code blob-code-inner js-file-line">    vector<<span class="pl-c1">crt_t</span>> rp;</td>
      </tr>
      <tr>
        <td id="L194" class="blob-num js-line-number" data-line-number="194"></td>
        <td id="LC194" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">auto</span> p_stime = <span class="pl-c1">chrono::high_resolution_clock::now</span>();</td>
      </tr>
      <tr>
        <td id="L195" class="blob-num js-line-number" data-line-number="195"></td>
        <td id="LC195" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">while</span> (!primeList.<span class="pl-c1">empty</span>()) {</td>
      </tr>
      <tr>
        <td id="L196" class="blob-num js-line-number" data-line-number="196"></td>
        <td id="LC196" class="blob-code blob-code-inner js-file-line">        <span class="pl-k">long</span> pp = primeList.<span class="pl-c1">front</span>();</td>
      </tr>
      <tr>
        <td id="L197" class="blob-num js-line-number" data-line-number="197"></td>
        <td id="LC197" class="blob-code blob-code-inner js-file-line">        primeList.<span class="pl-c1">pop_front</span>();</td>
      </tr>
      <tr>
        <td id="L198" class="blob-num js-line-number" data-line-number="198"></td>
        <td id="LC198" class="blob-code blob-code-inner js-file-line">        <span class="pl-c1">crt_t</span> tt = <span class="pl-c1">make_tuple</span>(<span class="pl-c1">computeBkModP</span>(pp,k), pp);</td>
      </tr>
      <tr>
        <td id="L199" class="blob-num js-line-number" data-line-number="199"></td>
        <td id="LC199" class="blob-code blob-code-inner js-file-line">        rp.<span class="pl-c1">push_back</span>(tt);</td>
      </tr>
      <tr>
        <td id="L200" class="blob-num js-line-number" data-line-number="200"></td>
        <td id="LC200" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L201" class="blob-num js-line-number" data-line-number="201"></td>
        <td id="LC201" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">auto</span> p_etime = <span class="pl-c1">chrono::high_resolution_clock::now</span>();</td>
      </tr>
      <tr>
        <td id="L202" class="blob-num js-line-number" data-line-number="202"></td>
        <td id="LC202" class="blob-code blob-code-inner js-file-line">    cout << <span class="pl-s"><span class="pl-pds">"</span>Parallel Time used: <span class="pl-pds">"</span></span> << chrono::duration_cast<chrono::milliseconds>(p_etime - p_stime).<span class="pl-c1">count</span>() << <span class="pl-s"><span class="pl-pds">"</span> msecs<span class="pl-pds">"</span></span> << endl;</td>
      </tr>
      <tr>
        <td id="L203" class="blob-num js-line-number" data-line-number="203"></td>
        <td id="LC203" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">return</span> rp;</td>
      </tr>
      <tr>
        <td id="L204" class="blob-num js-line-number" data-line-number="204"></td>
        <td id="LC204" class="blob-code blob-code-inner js-file-line">}</td>
      </tr>
      <tr>
        <td id="L205" class="blob-num js-line-number" data-line-number="205"></td>
        <td id="LC205" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L206" class="blob-num js-line-number" data-line-number="206"></td>
        <td id="LC206" class="blob-code blob-code-inner js-file-line"><span class="pl-k">auto</span> <span class="pl-en">B</span>(<span class="pl-k">long</span> k) -> mpq_class</td>
      </tr>
      <tr>
        <td id="L207" class="blob-num js-line-number" data-line-number="207"></td>
        <td id="LC207" class="blob-code blob-code-inner js-file-line">{</td>
      </tr>
      <tr>
        <td id="L208" class="blob-num js-line-number" data-line-number="208"></td>
        <td id="LC208" class="blob-code blob-code-inner js-file-line">    mpq_class bern_base[] {mpq_class {<span class="pl-c1">1</span>, <span class="pl-c1">1</span>}, mpq_class {<span class="pl-c1">1</span>, <span class="pl-c1">2</span>}, mpq_class {<span class="pl-c1">1</span>, <span class="pl-c1">6</span>} };</td>
      </tr>
      <tr>
        <td id="L209" class="blob-num js-line-number" data-line-number="209"></td>
        <td id="LC209" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">if</span> (k < <span class="pl-c1">3</span>) <span class="pl-k">return</span> bern_base[k];</td>
      </tr>
      <tr>
        <td id="L210" class="blob-num js-line-number" data-line-number="210"></td>
        <td id="LC210" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L211" class="blob-num js-line-number" data-line-number="211"></td>
        <td id="LC211" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">if</span> (k & <span class="pl-c1">1</span>) <span class="pl-k">return</span> mpq_class {<span class="pl-c1">0</span>, <span class="pl-c1">1</span>};</td>
      </tr>
      <tr>
        <td id="L212" class="blob-num js-line-number" data-line-number="212"></td>
        <td id="LC212" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">long</span> Y = <span class="pl-c1">long</span>(<span class="pl-c1">ceil</span>((k+<span class="pl-c1">0.5</span>) * <span class="pl-c1">log2</span>(k)));</td>
      </tr>
      <tr>
        <td id="L213" class="blob-num js-line-number" data-line-number="213"></td>
        <td id="LC213" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">if</span> (Y < <span class="pl-c1">37</span>) Y = <span class="pl-c1">37</span>;</td>
      </tr>
      <tr>
        <td id="L214" class="blob-num js-line-number" data-line-number="214"></td>
        <td id="LC214" class="blob-code blob-code-inner js-file-line">    PrimeTable <span class="pl-smi">primeTable</span>(Y);</td>
      </tr>
      <tr>
        <td id="L215" class="blob-num js-line-number" data-line-number="215"></td>
        <td id="LC215" class="blob-code blob-code-inner js-file-line">    mpz_class dk = <span class="pl-c1">computeDk</span>(k, primeTable);</td>
      </tr>
      <tr>
        <td id="L216" class="blob-num js-line-number" data-line-number="216"></td>
        <td id="LC216" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">long</span> beta = <span class="pl-c1">long</span>(<span class="pl-c1">ceil</span>( (k+<span class="pl-c1">0.5</span>) * <span class="pl-c1">log2</span>(k) - <span class="pl-c1">4.094</span> * k + <span class="pl-c1">2.470</span> + <span class="pl-c1">log2</span>(dk.<span class="pl-c1">get_d</span>())));</td>
      </tr>
      <tr>
        <td id="L217" class="blob-num js-line-number" data-line-number="217"></td>
        <td id="LC217" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">long</span> p = <span class="pl-c1">3</span>;</td>
      </tr>
      <tr>
        <td id="L218" class="blob-num js-line-number" data-line-number="218"></td>
        <td id="LC218" class="blob-code blob-code-inner js-file-line">    mpz_class M_ {<span class="pl-c1">1</span>};</td>
      </tr>
      <tr>
        <td id="L219" class="blob-num js-line-number" data-line-number="219"></td>
        <td id="LC219" class="blob-code blob-code-inner js-file-line">    mpz_class twoPowerBetaPlusOne;</td>
      </tr>
      <tr>
        <td id="L220" class="blob-num js-line-number" data-line-number="220"></td>
        <td id="LC220" class="blob-code blob-code-inner js-file-line">    <span class="pl-c1">mpz_ui_pow_ui</span>(twoPowerBetaPlusOne.<span class="pl-c1">get_mpz_t</span>(), <span class="pl-c1">2</span>, beta+<span class="pl-c1">1</span>);</td>
      </tr>
      <tr>
        <td id="L221" class="blob-num js-line-number" data-line-number="221"></td>
        <td id="LC221" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L222" class="blob-num js-line-number" data-line-number="222"></td>
        <td id="LC222" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">while</span> (M_ < twoPowerBetaPlusOne) {</td>
      </tr>
      <tr>
        <td id="L223" class="blob-num js-line-number" data-line-number="223"></td>
        <td id="LC223" class="blob-code blob-code-inner js-file-line">        p = primeTable.<span class="pl-c1">nextPrime</span>(p);</td>
      </tr>
      <tr>
        <td id="L224" class="blob-num js-line-number" data-line-number="224"></td>
        <td id="LC224" class="blob-code blob-code-inner js-file-line">        <span class="pl-k">if</span> (k % (p-<span class="pl-c1">1</span>) != <span class="pl-c1">0</span>) {</td>
      </tr>
      <tr>
        <td id="L225" class="blob-num js-line-number" data-line-number="225"></td>
        <td id="LC225" class="blob-code blob-code-inner js-file-line">            M_ *= p;</td>
      </tr>
      <tr>
        <td id="L226" class="blob-num js-line-number" data-line-number="226"></td>
        <td id="LC226" class="blob-code blob-code-inner js-file-line">        }</td>
      </tr>
      <tr>
        <td id="L227" class="blob-num js-line-number" data-line-number="227"></td>
        <td id="LC227" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L228" class="blob-num js-line-number" data-line-number="228"></td>
        <td id="LC228" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L229" class="blob-num js-line-number" data-line-number="229"></td>
        <td id="LC229" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">long</span> X = p;</td>
      </tr>
      <tr>
        <td id="L230" class="blob-num js-line-number" data-line-number="230"></td>
        <td id="LC230" class="blob-code blob-code-inner js-file-line">    mpz_class M {<span class="pl-c1">1</span>};</td>
      </tr>
      <tr>
        <td id="L231" class="blob-num js-line-number" data-line-number="231"></td>
        <td id="LC231" class="blob-code blob-code-inner js-file-line">    p = <span class="pl-c1">2</span>;</td>
      </tr>
      <tr>
        <td id="L232" class="blob-num js-line-number" data-line-number="232"></td>
        <td id="LC232" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L233" class="blob-num js-line-number" data-line-number="233"></td>
        <td id="LC233" class="blob-code blob-code-inner js-file-line">    primeList_t primeList;</td>
      </tr>
      <tr>
        <td id="L234" class="blob-num js-line-number" data-line-number="234"></td>
        <td id="LC234" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L235" class="blob-num js-line-number" data-line-number="235"></td>
        <td id="LC235" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">while</span> (p <= X) {</td>
      </tr>
      <tr>
        <td id="L236" class="blob-num js-line-number" data-line-number="236"></td>
        <td id="LC236" class="blob-code blob-code-inner js-file-line">        <span class="pl-k">if</span> (k % (p-<span class="pl-c1">1</span>) != <span class="pl-c1">0</span>) {</td>
      </tr>
      <tr>
        <td id="L237" class="blob-num js-line-number" data-line-number="237"></td>
        <td id="LC237" class="blob-code blob-code-inner js-file-line">            primeList.<span class="pl-c1">push_back</span>(p);</td>
      </tr>
      <tr>
        <td id="L238" class="blob-num js-line-number" data-line-number="238"></td>
        <td id="LC238" class="blob-code blob-code-inner js-file-line">            M *= p;</td>
      </tr>
      <tr>
        <td id="L239" class="blob-num js-line-number" data-line-number="239"></td>
        <td id="LC239" class="blob-code blob-code-inner js-file-line">        }</td>
      </tr>
      <tr>
        <td id="L240" class="blob-num js-line-number" data-line-number="240"></td>
        <td id="LC240" class="blob-code blob-code-inner js-file-line">        p = primeTable.<span class="pl-c1">nextPrime</span>(p);</td>
      </tr>
      <tr>
        <td id="L241" class="blob-num js-line-number" data-line-number="241"></td>
        <td id="LC241" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L242" class="blob-num js-line-number" data-line-number="242"></td>
        <td id="LC242" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">auto</span> rp = <span class="pl-c1">distribute</span>(k, primeList);</td>
      </tr>
      <tr>
        <td id="L243" class="blob-num js-line-number" data-line-number="243"></td>
        <td id="LC243" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L244" class="blob-num js-line-number" data-line-number="244"></td>
        <td id="LC244" class="blob-code blob-code-inner js-file-line">    mpz_class R = <span class="pl-c1">computeCRT</span>(rp);</td>
      </tr>
      <tr>
        <td id="L245" class="blob-num js-line-number" data-line-number="245"></td>
        <td id="LC245" class="blob-code blob-code-inner js-file-line">    mpz_class N_ = <span class="pl-c1">norm</span>((dk * R) % M, M);</td>
      </tr>
      <tr>
        <td id="L246" class="blob-num js-line-number" data-line-number="246"></td>
        <td id="LC246" class="blob-code blob-code-inner js-file-line">    mpz_class nk = (k % <span class="pl-c1">4</span> == <span class="pl-c1">2</span>)? N_ : N_ - M;</td>
      </tr>
      <tr>
        <td id="L247" class="blob-num js-line-number" data-line-number="247"></td>
        <td id="LC247" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">return</span> mpq_class {nk, dk};</td>
      </tr>
      <tr>
        <td id="L248" class="blob-num js-line-number" data-line-number="248"></td>
        <td id="LC248" class="blob-code blob-code-inner js-file-line">}</td>
      </tr>
      <tr>
        <td id="L249" class="blob-num js-line-number" data-line-number="249"></td>
        <td id="LC249" class="blob-code blob-code-inner js-file-line">
</td>
      </tr>
      <tr>
        <td id="L250" class="blob-num js-line-number" data-line-number="250"></td>
        <td id="LC250" class="blob-code blob-code-inner js-file-line"><span class="pl-k">auto</span> <span class="pl-en">main</span>(<span class="pl-k">int</span> argc, <span class="pl-k">char</span> *argv[]) -> int</td>
      </tr>
      <tr>
        <td id="L251" class="blob-num js-line-number" data-line-number="251"></td>
        <td id="LC251" class="blob-code blob-code-inner js-file-line">{</td>
      </tr>
      <tr>
        <td id="L252" class="blob-num js-line-number" data-line-number="252"></td>
        <td id="LC252" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">if</span> (argc != <span class="pl-c1">2</span>) {</td>
      </tr>
      <tr>
        <td id="L253" class="blob-num js-line-number" data-line-number="253"></td>
        <td id="LC253" class="blob-code blob-code-inner js-file-line">        cout << <span class="pl-s"><span class="pl-pds">"</span>usage: <span class="pl-pds">"</span></span> << argv[<span class="pl-c1">0</span>] << <span class="pl-s"><span class="pl-pds">"</span> m<span class="pl-pds">"</span></span> << endl;</td>
      </tr>
      <tr>
        <td id="L254" class="blob-num js-line-number" data-line-number="254"></td>
        <td id="LC254" class="blob-code blob-code-inner js-file-line">        <span class="pl-k">return</span> <span class="pl-c1">0</span>;</td>
      </tr>
      <tr>
        <td id="L255" class="blob-num js-line-number" data-line-number="255"></td>
        <td id="LC255" class="blob-code blob-code-inner js-file-line">    }</td>
      </tr>
      <tr>
        <td id="L256" class="blob-num js-line-number" data-line-number="256"></td>
        <td id="LC256" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">auto</span> t_stime = <span class="pl-c1">chrono::high_resolution_clock::now</span>();</td>
      </tr>
      <tr>
        <td id="L257" class="blob-num js-line-number" data-line-number="257"></td>
        <td id="LC257" class="blob-code blob-code-inner js-file-line">    cout << <span class="pl-s"><span class="pl-pds">"</span>B(<span class="pl-pds">"</span></span> << argv[<span class="pl-c1">1</span>] << <span class="pl-s"><span class="pl-pds">"</span>) = <span class="pl-pds">"</span></span> << <span class="pl-c1">B</span>(<span class="pl-c1">atoi</span>(argv[<span class="pl-c1">1</span>])) << endl;</td>
      </tr>
      <tr>
        <td id="L258" class="blob-num js-line-number" data-line-number="258"></td>
        <td id="LC258" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">auto</span> t_etime = <span class="pl-c1">chrono::high_resolution_clock::now</span>();</td>
      </tr>
      <tr>
        <td id="L259" class="blob-num js-line-number" data-line-number="259"></td>
        <td id="LC259" class="blob-code blob-code-inner js-file-line">    cout << <span class="pl-s"><span class="pl-pds">"</span>Total Time used: <span class="pl-pds">"</span></span> << chrono::duration_cast<chrono::milliseconds>(t_etime - t_stime).<span class="pl-c1">count</span>() << <span class="pl-s"><span class="pl-pds">"</span> msecs<span class="pl-pds">"</span></span> << endl;</td>
      </tr>
      <tr>
        <td id="L260" class="blob-num js-line-number" data-line-number="260"></td>
        <td id="LC260" class="blob-code blob-code-inner js-file-line">    <span class="pl-k">return</span> <span class="pl-c1">0</span>;</td>
      </tr>
      <tr>
        <td id="L261" class="blob-num js-line-number" data-line-number="261"></td>
        <td id="LC261" class="blob-code blob-code-inner js-file-line">}</td>
      </tr>
</table>

  <details class="details-reset details-overlay BlobToolbar position-absolute js-file-line-actions dropdown d-none" aria-hidden="true">
    <summary class="btn-octicon ml-0 px-2 p-0 bg-white border border-gray-dark rounded-1" aria-label="Inline file action toolbar">
      <svg class="octicon octicon-kebab-horizontal" viewBox="0 0 13 16" version="1.1" width="13" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M1.5 9a1.5 1.5 0 100-3 1.5 1.5 0 000 3zm5 0a1.5 1.5 0 100-3 1.5 1.5 0 000 3zM13 7.5a1.5 1.5 0 11-3 0 1.5 1.5 0 013 0z"></path></svg>
    </summary>
    <details-menu>
      <ul class="BlobToolbar-dropdown dropdown-menu dropdown-menu-se mt-2" style="width:185px">
        <li>
          <clipboard-copy role="menuitem" class="dropdown-item" id="js-copy-lines" style="cursor:pointer;">
            Copy lines
          </clipboard-copy>
        </li>
        <li>
          <clipboard-copy role="menuitem" class="dropdown-item" id="js-copy-permalink" style="cursor:pointer;">
            Copy permalink
          </clipboard-copy>
        </li>
        <li><a class="dropdown-item js-update-url-with-hash" id="js-view-git-blame" role="menuitem" href="/hpc-thai/HPCThai/blame/e1ffffd730a5072b7277c9a7bd39374479653786/introHPC/07/bern_amdahl.cpp">View git blame</a></li>
          <li><a class="dropdown-item" id="js-new-issue" role="menuitem" href="/hpc-thai/HPCThai/issues/new">Reference in new issue</a></li>
      </ul>
    </details-menu>
  </details>

  </div>

    </div>

  

  <details class="details-reset details-overlay details-overlay-dark">
    <summary data-hotkey="l" aria-label="Jump to line"></summary>
    <details-dialog class="Box Box--overlay d-flex flex-column anim-fade-in fast linejump" aria-label="Jump to line">
      <!-- '"` --><!-- </textarea></xmp> --></option></form><form class="js-jump-to-line-form Box-body d-flex" action="" accept-charset="UTF-8" method="get">
        <input class="form-control flex-auto mr-3 linejump-input js-jump-to-line-field" type="text" placeholder="Jump to line…" aria-label="Jump to line" autofocus>
        <button type="submit" class="btn" data-close-dialog>Go</button>
</form>    </details-dialog>
  </details>



  </div>
</div>

    </main>
  </div>
  

  </div>

        
<div class="footer container-lg width-full p-responsive" role="contentinfo">
  <div class="position-relative d-flex flex-row-reverse flex-lg-row flex-wrap flex-lg-nowrap flex-justify-center flex-lg-justify-between pt-6 pb-2 mt-6 f6 text-gray border-top border-gray-light ">
    <ul class="list-style-none d-flex flex-wrap col-12 col-lg-5 flex-justify-center flex-lg-justify-between mb-2 mb-lg-0">
      <li class="mr-3 mr-lg-0">© 2020 GitHub, Inc.</li>
        <li class="mr-3 mr-lg-0"><a data-ga-click="Footer, go to terms, text:terms" href="https://github.com/site/terms">Terms</a></li>
        <li class="mr-3 mr-lg-0"><a data-ga-click="Footer, go to privacy, text:privacy" href="https://github.com/site/privacy">Privacy</a></li>
        <li class="mr-3 mr-lg-0"><a data-ga-click="Footer, go to security, text:security" href="https://github.com/security">Security</a></li>
        <li class="mr-3 mr-lg-0"><a href="https://githubstatus.com/" data-ga-click="Footer, go to status, text:status">Status</a></li>
        <li><a data-ga-click="Footer, go to help, text:help" href="https://help.github.com">Help</a></li>

    </ul>

    <a aria-label="Homepage" title="GitHub" class="footer-octicon d-none d-lg-block mx-lg-4" href="https://github.com">
      <svg height="24" class="octicon octicon-mark-github" viewBox="0 0 16 16" version="1.1" width="24" aria-hidden="true"><path fill-rule="evenodd" d="M8 0C3.58 0 0 3.58 0 8c0 3.54 2.29 6.53 5.47 7.59.4.07.55-.17.55-.38 0-.19-.01-.82-.01-1.49-2.01.37-2.53-.49-2.69-.94-.09-.23-.48-.94-.82-1.13-.28-.15-.68-.52-.01-.53.63-.01 1.08.58 1.23.82.72 1.21 1.87.87 2.33.66.07-.52.28-.87.51-1.07-1.78-.2-3.64-.89-3.64-3.95 0-.87.31-1.59.82-2.15-.08-.2-.36-1.02.08-2.12 0 0 .67-.21 2.2.82.64-.18 1.32-.27 2-.27.68 0 1.36.09 2 .27 1.53-1.04 2.2-.82 2.2-.82.44 1.1.16 1.92.08 2.12.51.56.82 1.27.82 2.15 0 3.07-1.87 3.75-3.65 3.95.29.25.54.73.54 1.48 0 1.07-.01 1.93-.01 2.2 0 .21.15.46.55.38A8.013 8.013 0 0016 8c0-4.42-3.58-8-8-8z"></path></svg>
</a>
   <ul class="list-style-none d-flex flex-wrap col-12 col-lg-5 flex-justify-center flex-lg-justify-between mb-2 mb-lg-0">
        <li class="mr-3 mr-lg-0"><a data-ga-click="Footer, go to contact, text:contact" href="https://github.com/contact">Contact GitHub</a></li>
        <li class="mr-3 mr-lg-0"><a href="https://github.com/pricing" data-ga-click="Footer, go to Pricing, text:Pricing">Pricing</a></li>
      <li class="mr-3 mr-lg-0"><a href="https://developer.github.com" data-ga-click="Footer, go to api, text:api">API</a></li>
      <li class="mr-3 mr-lg-0"><a href="https://training.github.com" data-ga-click="Footer, go to training, text:training">Training</a></li>
        <li class="mr-3 mr-lg-0"><a href="https://github.blog" data-ga-click="Footer, go to blog, text:blog">Blog</a></li>
        <li><a data-ga-click="Footer, go to about, text:about" href="https://github.com/about">About</a></li>
    </ul>
  </div>
  <div class="d-flex flex-justify-center pb-6">
    <span class="f6 text-gray-light"></span>
  </div>
</div>



  <div id="ajax-error-message" class="ajax-error-message flash flash-error">
    <svg class="octicon octicon-alert" viewBox="0 0 16 16" version="1.1" width="16" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M8.893 1.5c-.183-.31-.52-.5-.887-.5s-.703.19-.886.5L.138 13.499a.98.98 0 000 1.001c.193.31.53.501.886.501h13.964c.367 0 .704-.19.877-.5a1.03 1.03 0 00.01-1.002L8.893 1.5zm.133 11.497H6.987v-2.003h2.039v2.003zm0-3.004H6.987V5.987h2.039v4.006z"></path></svg>
    <button type="button" class="flash-close js-ajax-error-dismiss" aria-label="Dismiss error">
      <svg class="octicon octicon-x" viewBox="0 0 12 16" version="1.1" width="12" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M7.48 8l3.75 3.75-1.48 1.48L6 9.48l-3.75 3.75-1.48-1.48L4.52 8 .77 4.25l1.48-1.48L6 6.52l3.75-3.75 1.48 1.48L7.48 8z"></path></svg>
    </button>
    You can’t perform that action at this time.
  </div>


    <script crossorigin="anonymous" async="async" integrity="sha512-WcQmT2vhcClFVOaaAJV/M+HqsJ2Gq/myvl6F3gCVBxykazXTs+i5fvxncSXwyG1CSfcrqmLFw/R/bmFYzprX2A==" type="application/javascript" id="js-conditional-compat" data-src="https://github.githubassets.com/assets/compat-bootstrap-59c4264f.js"></script>
    <script crossorigin="anonymous" integrity="sha512-Y86V8OBlvF6I/7e56GKOOt80Yg1RTGA09uqFFX18aiBtevLbKGxB7sVpCn79fukppFIBqyBTB/s6l0Bhn0kidQ==" type="application/javascript" src="https://github.githubassets.com/assets/environment-bootstrap-63ce95f0.js"></script>
    <script crossorigin="anonymous" async="async" integrity="sha512-ASMgX6+DJ9LVZX/3Fj0RzibSpfigU83ubvsxxwriojWmuBM3faUp1108gypkhXpqLHEBQhIhjlzDOejzOFd0gA==" type="application/javascript" src="https://github.githubassets.com/assets/vendor-0123205f.js"></script>
    <script crossorigin="anonymous" async="async" integrity="sha512-/m8I1HkTKfQgD4Lqec5vpR0qqCNHDINqdqbHHZnQDDaJff7C2KUPTSbPwu0Xhv2br1ccJkb3OtrrWyPWmbHPHw==" type="application/javascript" src="https://github.githubassets.com/assets/frameworks-fe6f08d4.js"></script>
    
    <script crossorigin="anonymous" async="async" integrity="sha512-qiO41q9D08ZPFIkTGHMecKrp/jHcX6w6Tf9mTKrtL1Mv1Tr74DCZeZPgHNWLoR/DUl8uucfHMyNeSTFRADzC3Q==" type="application/javascript" src="https://github.githubassets.com/assets/github-bootstrap-aa23b8d6.js"></script>
    
        <script crossorigin="anonymous" async="async" integrity="sha512-4GcSWGoe36+BoWho4gtJcByZe8j43w+lt2/PDe3rmBxRVSgD29YipDwuIywe8fvOd2b2CszBqaPGxSznUtE3Xg==" type="application/javascript" data-module-id="./drag-drop.js" data-src="https://github.githubassets.com/assets/drag-drop-e0671258.js"></script>
        <script crossorigin="anonymous" async="async" integrity="sha512-3Vk1NFIOm+TBUMM6pTA6DCUwwLLnc/QIT8jpENm71InvSU8O4p2plDagpst1tH1l+9jOBnneaXZnAskA9a2b3w==" type="application/javascript" data-module-id="./gist-vendor.js" data-src="https://github.githubassets.com/assets/gist-vendor-dd593534.js"></script>
        <script crossorigin="anonymous" async="async" integrity="sha512-urN6bhHnHu4C12A+cTH3dOp+CwLaycy2HUXr95hvu5pbYRdF8z6iR+UQcTZutQ6mZG3Njluw2MTZVCNmwcqh8g==" type="application/javascript" data-module-id="./randomColor.js" data-src="https://github.githubassets.com/assets/randomColor-bab37a6e.js"></script>
    
    
  <div class="js-stale-session-flash flash flash-warn flash-banner" hidden
    >
    <svg class="octicon octicon-alert" viewBox="0 0 16 16" version="1.1" width="16" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M8.893 1.5c-.183-.31-.52-.5-.887-.5s-.703.19-.886.5L.138 13.499a.98.98 0 000 1.001c.193.31.53.501.886.501h13.964c.367 0 .704-.19.877-.5a1.03 1.03 0 00.01-1.002L8.893 1.5zm.133 11.497H6.987v-2.003h2.039v2.003zm0-3.004H6.987V5.987h2.039v4.006z"></path></svg>
    <span class="js-stale-session-flash-signed-in" hidden>You signed in with another tab or window. <a href="">Reload</a> to refresh your session.</span>
    <span class="js-stale-session-flash-signed-out" hidden>You signed out in another tab or window. <a href="">Reload</a> to refresh your session.</span>
  </div>
  <template id="site-details-dialog">
  <details class="details-reset details-overlay details-overlay-dark lh-default text-gray-dark hx_rsm" open>
    <summary role="button" aria-label="Close dialog"></summary>
    <details-dialog class="Box Box--overlay d-flex flex-column anim-fade-in fast hx_rsm-dialog hx_rsm-modal">
      <button class="Box-btn-octicon m-0 btn-octicon position-absolute right-0 top-0" type="button" aria-label="Close dialog" data-close-dialog>
        <svg class="octicon octicon-x" viewBox="0 0 12 16" version="1.1" width="12" height="16" aria-hidden="true"><path fill-rule="evenodd" d="M7.48 8l3.75 3.75-1.48 1.48L6 9.48l-3.75 3.75-1.48-1.48L4.52 8 .77 4.25l1.48-1.48L6 6.52l3.75-3.75 1.48 1.48L7.48 8z"></path></svg>
      </button>
      <div class="octocat-spinner my-6 js-details-dialog-spinner"></div>
    </details-dialog>
  </details>
</template>

  <div class="Popover js-hovercard-content position-absolute" style="display: none; outline: none;" tabindex="0">
  <div class="Popover-message Popover-message--bottom-left Popover-message--large Box box-shadow-large" style="width:360px;">
  </div>
</div>


  </body>
</html>

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

</li>

<a href="/enterprise" class="HeaderMenu-link no-underline py-3 d-block d-lg-inline-block" data-ga-click="(Logged out) Header, go to Enterprise">Enterprise</a>

</li>

Explore

</svg>

</summary>

กลับมาเนื้องานของเรา ถ้าผมจับเวลาทั้งหมดบรรทัดแรกของ main() คร่อมไปปิดบรรทัดสุดท้าย จับเวลาได้เท่าไหร่ก็ตาม มันก็คือเวลาทั้งหมด หรือ 1 ตามกฏของแอมดาล และถ้าผมจับเวลาเฉพาะส่วนการวนรอบ computeBkModP(p, k) ก็คือการคร่อมการทำงานภายใน distribute() นั่นเอง โปรแกรมเต็มดูได้จาก HPCThai/introHPC/07/bern_amdahl.cpp

ถ้าเราจับเวลาคร่อมภายใน distribute() เราจะคำนวณได้ค่า P ตามกฏของแอมดาล แต่การที่จะได้ค่า P นั้น จะต้อเทียบกับเวลาที่ใช้ทั้งโปรแกรม ซึ่งประกอบด้วยส่วนประมวลผลแบบขนานคือฟังก์ชัน distribute และส่วนประมวลผลเดี่ยวคือที่เหลือทั้งหมด ถ้าผมจับเวลาที่ main() บรรทัดแรกคร่อมถึงบรรทัดสุดท้าย ผมจะได้เวลารวมทั้งหมด เอาไปลองรันดูก่อนครับ ได้ผลลัพธ์ดังนี้

โปรแกรมนี้ทำงานบน Banana Pi ตรวจคำตอบแล้วถูกต้อง ลอจิกการทำงานไม่ผิดเพี้ยน ถือว่าผ่าน สิ่งที่เราสนใจก็คือเวลาที่ใช้ บรรทัดล่างสุด ผมจับเวลาคร่อม main() ทั้งหมด ได้ 48,852 msecs หรือ เกือบๆ 49 วินาที นั่นคือเวลาทั้งหมดตามกฏของแอมดาลหรือ 1 นั่นเอง ส่วนเวลาที่ใช้ในการประมวลผลแบบขนานได้ทั้งหมดอยู่ข้างบนครับนั่นคือ 48,542 msecs เมื่อเทียบเป็นอัตราก็จะได้ 48,542/48,852 หรือ 0.993654 ซึ่งก็คือค่า P ตามกฏของแอมดาลนั่นเอง อาจกล่าวว่า เวลาที่ใช้ส่วนใหญ่คือมากกว่า 99% นั้นอยู่ในส่วนที่ประมวลผลแบบขนานได้ โปรแกรมลักษณะนี้คุ้มครับที่จะประมวลผลแบบขนาน

เมื่อได้ค่า P มาแล้ว เราลองมาเอาเข้ากฏเต็มรูปดูครับ จะได้

$S(N)=\frac{1}{(1-0.993654) + \frac{0.993654}{N}}$

เมื่อ N คือจำนวนตัวประมวลผล ผมลองปั่นจำนวนหน่วยประมวลผลจาก 1 ไปถึง 10 ดูว่าผลตอบสนองเป็นอย่างไร จะเร็วขึ้นได้กี่เท่า เรามาทดลองกันดีกว่าครับ วันนี้ผมขอแนะนำโปรแกรมเพิ่มอีกตัวหนึ่งครับ ถือได้ว่าเป็นสนามเด็กเล่นของชาว HPC เลยครับ นั่นก็คือ ipython notebook ครับ ไม่พูดพล่ามทำเพลง ไปที่ shell ไม่ว่าจะเป็น windows หรือ linux ก็ได้ พิมพ์คำว่าเลยครับ

ipython notebook --pylab inline

1	ipython notebook --pylab inline

โปรแกรมจะเปิดหน้าเว็ปขึ้นมา เหมือนกับ sagemath.org เราก็เลือก ‘new notebook’ จากนั้นก็พิมพ์โปรแกรมนี้ตามเลยครับ

def amdahl(N):
    return 1/( (1-0.993654) + 0.993654/N)

N = numpy.arange(1, 11)
plot(N, amdahl(N), 'r-')
grid()

def amdahl(N):

return 1/( (1-0.993654) + 0.993654/N)

N = numpy.arange(1, 11)

plot(N, amdahl(N), 'r-')

grid()

จากนั้นกดปุ่มรัน จะได้ผลลัพธ์ตามนี้ครับ

โปรแกรมที่เขียนอาจจะดูแปลกไปเล็กน้อย เพราะไม่ได้อ้างถึง matplotlib เลย ผมใช้ pylab ครับเป็น library ที่ขี่อยู่บน matplotlib อีกที ลักษณะคล้ายๆ MATLAB ครับ ใครมาทางสาย MATLAB จะคุ้นเคยครับ เรามาดูกราฟกัน ในแกน X คือจำนวนหน่วยประมวลผลที่เพิ่มขึ้น ส่วนแกน Y เป็นผลตอบสนองเป็นจำนวนเท่าที่ทำงานเร็วขึ้นหรือ S นั่นเอง เห็นอะไรไหมครับ อัลกอริทึมของเราดีมาก แทบจะตอบสนองกันเป็นเส้นตรง เพิ่มตัวประมวลผลหนึ่งตัวความเร็วเพิ่มขึ้นอีกหนึ่งเท่า

เดี๋ยวก่อนครับ โลกมันไม่ได้สวยงามขนาดนั้นครับ สมมติว่าผมไปใช้ Supercomputer ขนาดกลางๆ มีตัวประมวลผล 10,000 ตัว มันจะเร็วขึ้นอีกแค่ไหน ท่านลองเปลี่ยนตัวเลข 11 เป็น 10001 ดูครับ แล้วกดรันใหม่ จะได้ผลลัพธ์ทันทีเลย REPL แบบ graphics ตัวนี้ยอดเยี่ยมมาก ฟรีอีกต่างหาก ผลลัพธ์ชวนอึ้ง ดังนี้ครับ

ผลลัพธ์ชวนอึ้งไหมครับ ใส่ตัวประมวลผลเข้าไป 10,000 ตัว แต่ผลตอบสนองกับได้แค่ไม่ถึง 160 เท่า อย่าไปตกใจหรือแปลกใจครับ มันเป็นกฏธรรมชาติเข้าใจได้โดยไม่ยากครับ ตัวเลขอย่างนี้เพราะโจทย์ของเราเป็นโจทย์ง่ายครับ หา B(1000) ใช้เวลาประมาณหนึ่งนาที จะให้ใส่ตัวประมวลผลไป 10,000 ตัวแล้วกระพริบตาให้เสร็จเลย มันก็คงไม่ใช่ครับ แต่ถ้าหา B(2000) ค่า P จะสูงกว่านี้พอสมควรครับ ค่ายิ่งสูงยิ่งทำให้กราฟถดถอยช้าลง

ขอย้ำอีกทีนะครับ ตัวเลขที่หานั้นเป็นแค่เชิงทฤษฎีเท่านั้น ในทางปฏิบัติตัวเลขที่ได้แย่กว่านี้อีกมากครับ

จับความเร็ว computeBkModP(p, k)

ผมขอพักเรื่องทางทฤษฎีของแอมดาลเอาไว้ก่อนครับ เรามาดูปฏิบัติของจริงกันบ้าง จะได้เห็นโลกอีกมุม จากข้างต้น ผมแสดงให้ท่านเห็นแล้วว่า computeBkModP(p, k) นั้นสามารถประมวลผลแบบขนานได้ ผมลองใช้ตัวแปรสะสมค่าดู พบว่า มีค่า p อยู่ 568 จำนวนที่ต้องคำนวณ คำถามก็คือถ้าผมมีหน่วยประมวลผล 568 ตัว ส่งฟังก์ชันดังกล่าวขึ้นไปทำงาน คำถามก็คือใช้เวลาเท่าไหร่จึงจะเสร็จ คำตอบที่ท่านตอบจะก่อให้เกิดคำถามใหม่ ท่านคงตอบว่า ความเร็วที่ได้ขึ้นอยู่กับว่าตัวประมวลผลตัวไหนทำงานช้าที่สุด ตัวหน่วยประมวลผลที่ทำงานเสร็จแล้วก็ได้ไปพัก ที่ไม่เสร็จก็ต้องทำต่อไป ถ้าท่านพูดอย่างนี้ก็แสดงว่า ความเร็วที่ได้ก็จะเท่ากับเวลาที่ใช้ไปของตัวประมวลผลตัวที่ช้าที่สุด ในเมื่อตัวประมวลผลที่มีทุกตัวสเปคเดียวกันหมด จึงเร็วช้าก็ไม่น่าต่างกันมากนัก ถ้าอย่างนั้น แสดงว่าเวลาที่ใช้ในการประมวลผลในแต่ละค่าของ p ไม่เท่ากันใช่หรือไม่

ผมจะตอบคำถามนี้ด้วยการเขียนโปรแกรมครับ คือเอาโปรแกรมเดิมมาแก้ คราวนี้ผมจับเวลาที่ใช้ในการเรียกฟังก์ชันแต่ละครั้งกันเลย และเพื่อให้เห็นภาพผมจะนำผลมาแสดงเป็นกราฟ ซึ่งยังคงไว้ซึ่งจุดยืนครับคือใช้ภาษา C++ ถ้าเป็น Python ก็คงไม่กระไรนักเพราะเราคุ้นเคยกับ Matplotlib อยู่แล้ว แต่ใน Standard Library ของ C++ ไม่มีเรื่อง Graphics ครับ ต้องใช้ Library ภายนอก ตัวทำกราฟที่นิยมที่สุดของภาษาตระกูล C ก็คือ gnuplot ความสามารถสูสีกับ Matplotlib แถมยังรองรับภาษาคอมพิวเตอร์ได้หลากหลายกว่าครับ ที่พูดมาทั้งหมดนี้ ผมไม่ใช้ครับ เพราะมันจะทำเว็ปนี้ที่มันบวมอยู่แล้วมันจะบวมขึ้นอีก ผมจะใช้ Matplotlib ครับ

ภาษา Python กับภาษาตระกูล C นั้นมีความสัมพันธ์กันค่อนข้างแนบแน่น เราสามารถใช้ Python มาเรียก library ภาษา C ได้และในทางกลับกัน เราสามารถเขียนภาษา Python ภายในภาษา C ก็ยังได้ ถ้านึกตามไม่ออกว่ามันเป็นแบบไหน ก็ให้นึกถึงการเขียนภาษา SQL ในรูปแบบของ string ภายในภาษาที่เป็น host อื่น อารมณ์เดียวกันเลยครับ

เราต้องใช้ library ที่ชื่อว่า libpython สำหรับ *buntu แล้วเราติดตั้งได้โดย

sudo apt-get install libpython3.4-dev

1	sudo apt-get install libpython3.4-dev

แต่ถ้าเป็น Windows และใช้ Anaconda ไม่ต้องทำอะไรครับ มีให้มาในตัวเสร็จเรียบร้อยแล้ว เวลาต้องการใช้เราต้อง #include ในโปรแกรมภาษาตระกูล C เพิ่มดังนี้ครับ

#include <Python.h>

1	#include <Python.h>

สังเกตนะครับว่า P เป็นตัวอักษรใหญ่ คราวนี้มาดูตัวโปรแกรมกันครับ ผมเขียนใหม่แยกเป็นอีกแฟ้มหนึ่งเลยตั้งชื่อว่า HPCThai/introHPC/07/bern_tgraph.cpp ผมขอแสดงเฉพาะส่วนของการจับเวลาและสะสมค่าเวลา นั่นก็คือฟังก์ชัน distribute() นั่นเอง ดังนี้

#include <iostream>
#include <vector>
#include <cmath>
#include <gmpxx.h>
#include <tuple>
#include <stack>
#include <utility>
#include <deque>
#include <chrono>
#include <sstream>
#include <Python.h>

using namespace std;

class PrimeTable
{
public:
    PrimeTable(const long &size) : _size {size}, _table (size, true) {
        _table[0] = _table[1] = false;
        const long limit = (long)sqrt(size);
        for (long i=2; i<=limit; i++) {
            if (_table[i] == false) continue;
            for (long r=i+i; r<=size; r+=i) _table[r] = false;
        }
    }

    long nextPrime(long pos) {
        for (long i=pos+1; i<=_size; i++) {
            if (_table[i] == true) return i;
        }
        return -1;
    }
private:
    long _size;
    std::vector<bool> _table;
};

auto computeDk(const int &k, PrimeTable& primeTable) -> mpz_class
{
    long p {2};
    mpz_class dk {1};
    while (p != -1) {
        if (k % (p-1) == 0) dk *= p;
        p = primeTable.nextPrime(p);
    }
    return std::move(dk);
}

auto norm(mpz_class b, mpz_class p) -> mpz_class
{
    while (true) {
        if (b < 0) b += p;
        else if (b > p) b -= p;
        else break;
    }
    return b;
}

auto computePowerMod(const mpz_class &a, const long &k, const mpz_class &m) -> mpz_class
{
    int index = log2(k);
    mpz_class powmod = 1, powa = a, pow2 = 1;

    for (int i=0; i<=index; i++) {
        if ( (k & pow2) != 0) powmod *= powa;
        powa = (powa * powa) % m;
        pow2 <<= 1;
    }
    return norm(powmod % m, m);
}

auto computeInvertMod(const mpz_class &n, mpz_class p) -> mpz_class
{
    stack<tuple<mpz_class, mpz_class, mpz_class>> v;
    mpz_class a = p;
    mpz_class b = n;
    if (n > p) {
        a = n;
        b = p;
    }
    mpz_class d = a / b;
    mpz_class r = a % b;

    while (r > 1) {
        v.push(make_tuple(a, b, -d));
        a = b;
        b = r;
        d = a / b;
        r = a % b;
    }
    mpz_class m1 = 1, m2 = -d;
    mpz_class aa = a, bb = b;

    while (!v.empty()) {
        auto t = v.top();
        v.pop();
        a = get<0>(t);
        b = get<1>(t);
        d = get<2>(t);
        m1 += (m2 * d);
        bb = a;
        swap(m1, m2);
        swap(aa, bb);
    }
    mpz_class rr = (n == aa)? m1 : m2;
    return norm(rr, p);
}

auto computeOrderEp(const long &a, const long &p) -> long
{
    for (long k=1; k<p; k++) {
        if (computePowerMod(a, k, p) == 1) return k;
    }
    throw "computeOrderEp error";
}

auto computePrimitiveRoot(const long &p) -> long
{
    if (p == 2) return 1;
    for (int g=2; g<p; g++) {
        if (computeOrderEp(g, p) == (p - 1)) return g;
    }
    throw "computePrimitiveRoot error";
}

auto computeBkModP(const long &p, const long &k) -> mpz_class
{
    if (k == 0) return 1;
    if (k == 1) return (p == 2)? -1 : (p-1)/2;
    if (k &  1) return 0;
    if (p <= 3) return -1;

    long m = k % (p-1);
    if (m == 0) return -1;

    mpz_class g = computePrimitiveRoot(p);
    mpz_class r = computePowerMod(g, k-1, p);
    mpz_class u = (g + ((g % 2 == 1)? 0 : p) - 1) / 2;
    mpz_class S = 0, X = 1, Y = r;


    mpz_class hp = (p-1)/2, q, h, t;
    for (long i=1; i<=hp; i++) {
        q = norm( (g*X)/p, p);
        h = norm( (q-u)%p, p);
        t = norm( (h*Y)%p, p);
        S = norm( (S-t)%p, p);
        X = norm( (g*X)%p, p);
        Y = norm( (r*Y)%p, p);
    }
    mpz_class ans = computePowerMod(g, k, p);

    ans = computeInvertMod(p+1-ans, p);

    ans = norm( (S * ans) % p, p);
    ans = norm( (2 * ans) % p, p);
    ans = norm( (k * ans) % p, p);

    return ans;
}

auto congruent(const mpz_class &a, const mpz_class &b, const mpz_class &m) -> mpz_class
{
    if (a == 1 && b == 1) return mpz_class {1};
    mpz_class inv = computeInvertMod(a, m);
    return (b * inv) % m;
}

auto computeCRT(vector<tuple<mpz_class, long>> &residue) -> mpz_class
{
    mpz_class mul_m = 1;
    for (auto top : residue) {
        mul_m *= get<1>(top);
    }

    mpz_class z = 0, M, X, b, m;
    for (auto top : residue) {
        b = get<0>(top);
        m = get<1>(top);
        M = mul_m / m;
        X = congruent(M, 1, m);
        z += M * X * b;
    }
    while (z > 0) {
        z -= mul_m;
    }
    return z + mul_m;
}

auto genGraph(std::string strP, std::string strTime) -> void
{
    Py_Initialize();
    PyRun_SimpleString("import matplotlib");
    PyRun_SimpleString("matplotlib.use('Agg')");
    PyRun_SimpleString("import matplotlib.pyplot as plt");
    PyRun_SimpleString(strP.c_str());
    PyRun_SimpleString(strTime.c_str());
    PyRun_SimpleString("plt.plot(p, time, 'g*-')");
    PyRun_SimpleString("plt.title('Elapsed Time for each P')");
    PyRun_SimpleString("plt.xlabel('P')");
    PyRun_SimpleString("plt.ylabel('Time used (msecs)')");
    PyRun_SimpleString("plt.grid()");
    PyRun_SimpleString("plt.savefig('tgraph.png')");
    Py_Finalize();
    cout << "Generated tgraph.png" << endl;
}

using crt_t = tuple<mpz_class, long>;
using primeList_t = deque<long>;

auto distribute(long k, primeList_t primeList) -> vector<crt_t>
{
    vector<crt_t> rp;
    stringstream ssP, ssTime;
    ssP << "p = [";
    ssTime << "time = [";
    cout << "Prime Queue Size = " << primeList.size() << endl;

    while (!primeList.empty()) {
        long pp = primeList.front();
        primeList.pop_front();
        auto p_stime = chrono::high_resolution_clock::now();
        crt_t tt = make_tuple(computeBkModP(pp,k), pp);
        auto p_etime = chrono::high_resolution_clock::now();
        ssP << pp << ", ";
        ssTime << chrono::duration_cast<chrono::milliseconds>(p_etime - p_stime).count() << ", ";
        rp.push_back(tt);
    }
    ssP << "]";
    ssTime << "]";
    genGraph(ssP.str(), ssTime.str());
    return rp;
}

auto B(long k) -> mpq_class
{
    mpq_class bern_base[] {mpq_class {1, 1}, mpq_class {1, 2}, mpq_class {1, 6} };
    if (k < 3) return bern_base[k];

    if (k & 1) return mpq_class {0, 1};
    long Y = long(ceil((k+0.5) * log2(k)));
    if (Y < 37) Y = 37;
    PrimeTable primeTable(Y);
    mpz_class dk = computeDk(k, primeTable);
    long beta = long(ceil( (k+0.5) * log2(k) - 4.094 * k + 2.470 + log2(dk.get_d())));
    long p = 3;
    mpz_class M_ {1};
    mpz_class twoPowerBetaPlusOne;
    mpz_ui_pow_ui(twoPowerBetaPlusOne.get_mpz_t(), 2, beta+1);

    while (M_ < twoPowerBetaPlusOne) {
        p = primeTable.nextPrime(p);
        if (k % (p-1) != 0) {
            M_ *= p;
        }
    }

    long X = p;
    mpz_class M {1};
    p = 2;
    primeList_t primeList;

    while (p <= X) {
        if (k % (p-1) != 0) {
            primeList.push_back(p);
            M *= p;
        }
        p = primeTable.nextPrime(p);
    }

    auto rp = distribute(k, primeList);
    mpz_class R = computeCRT(rp);
    mpz_class N_ = norm((dk * R) % M, M);
    mpz_class nk = (k % 4 == 2)? N_ : N_ - M;
    return mpq_class {nk, dk};
}

auto main(int argc, char *argv[]) -> int
{
    if (argc != 2) {
        cout << "usage: " << argv[0] << " m" << endl;
        return 0;
    }
    auto t_stime = chrono::high_resolution_clock::now();
    cout << "B(" << argv[1] << ") = " << B(atoi(argv[1])) << endl;
    auto t_etime = chrono::high_resolution_clock::now();
    cout << "Total Time used: " << chrono::duration_cast<chrono::milliseconds>(t_etime - t_stime).count() << " msecs" << endl;
    return 0;
}

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

auto distribute(long k, primeList_t primeList) -> vector<crt_t>

{

vector<crt_t> rp;

stringstream ssP, ssTime;

ssP << "p = [";

ssTime << "time = [";

cout << "Prime Queue Size = " << primeList.size() << endl;

while (!primeList.empty()) {

long pp = primeList.front();

primeList.pop_front();

auto p_stime = chrono::high_resolution_clock::now();

crt_t tt = make_tuple(computeBkModP(pp,k), pp);

auto p_etime = chrono::high_resolution_clock::now();

ssP << pp << ", ";

ssTime << chrono::duration_cast<chrono::milliseconds>(p_etime - p_stime).count() << ", ";

rp.push_back(tt);

}

ssP << "]";

ssTime << "]";

genGraph(ssP.str(), ssTime.str());

return rp;

}

จะเห็นได้ว่าผมจับเวลาคร่อมบรรทัดที่ 223 เอาไว้ ผลลัพธ์ที่ได้คือค่า p และ time ซึ่งเป็นเวลาที่จับได้หน่วยเป็น msecs นั้นเอาไปต่อเป็น string ชื่อ ssP และ ssTime โดยใช้ stringstream ถ้าดูกันให้ดีแล้วจะเห็นว่า ใน string ทั้งสองเป็นการสร้างตัวแปรของ Python ชื่อ p และ time นั่นเอง และข้อมูลที่เอาไปต่อก็จะเป็น list แบบธรรมดา

เมื่อสะสมข้อมูลเสร็จเรียบร้อยแล้ว ผมก็เรียกฟังก์ชัน genGraph() ซึ่งนิยามมีดังนี้ครับ

#include <iostream>
#include <vector>
#include <cmath>
#include <gmpxx.h>
#include <tuple>
#include <stack>
#include <utility>
#include <deque>
#include <chrono>
#include <sstream>
#include <Python.h>

using namespace std;

class PrimeTable
{
public:
    PrimeTable(const long &size) : _size {size}, _table (size, true) {
        _table[0] = _table[1] = false;
        const long limit = (long)sqrt(size);
        for (long i=2; i<=limit; i++) {
            if (_table[i] == false) continue;
            for (long r=i+i; r<=size; r+=i) _table[r] = false;
        }
    }

    long nextPrime(long pos) {
        for (long i=pos+1; i<=_size; i++) {
            if (_table[i] == true) return i;
        }
        return -1;
    }
private:
    long _size;
    std::vector<bool> _table;
};

auto computeDk(const int &k, PrimeTable& primeTable) -> mpz_class
{
    long p {2};
    mpz_class dk {1};
    while (p != -1) {
        if (k % (p-1) == 0) dk *= p;
        p = primeTable.nextPrime(p);
    }
    return std::move(dk);
}

auto norm(mpz_class b, mpz_class p) -> mpz_class
{
    while (true) {
        if (b < 0) b += p;
        else if (b > p) b -= p;
        else break;
    }
    return b;
}

auto computePowerMod(const mpz_class &a, const long &k, const mpz_class &m) -> mpz_class
{
    int index = log2(k);
    mpz_class powmod = 1, powa = a, pow2 = 1;

    for (int i=0; i<=index; i++) {
        if ( (k & pow2) != 0) powmod *= powa;
        powa = (powa * powa) % m;
        pow2 <<= 1;
    }
    return norm(powmod % m, m);
}

auto computeInvertMod(const mpz_class &n, mpz_class p) -> mpz_class
{
    stack<tuple<mpz_class, mpz_class, mpz_class>> v;
    mpz_class a = p;
    mpz_class b = n;
    if (n > p) {
        a = n;
        b = p;
    }
    mpz_class d = a / b;
    mpz_class r = a % b;

    while (r > 1) {
        v.push(make_tuple(a, b, -d));
        a = b;
        b = r;
        d = a / b;
        r = a % b;
    }
    mpz_class m1 = 1, m2 = -d;
    mpz_class aa = a, bb = b;

    while (!v.empty()) {
        auto t = v.top();
        v.pop();
        a = get<0>(t);
        b = get<1>(t);
        d = get<2>(t);
        m1 += (m2 * d);
        bb = a;
        swap(m1, m2);
        swap(aa, bb);
    }
    mpz_class rr = (n == aa)? m1 : m2;
    return norm(rr, p);
}

auto computeOrderEp(const long &a, const long &p) -> long
{
    for (long k=1; k<p; k++) {
        if (computePowerMod(a, k, p) == 1) return k;
    }
    throw "computeOrderEp error";
}

auto computePrimitiveRoot(const long &p) -> long
{
    if (p == 2) return 1;
    for (int g=2; g<p; g++) {
        if (computeOrderEp(g, p) == (p - 1)) return g;
    }
    throw "computePrimitiveRoot error";
}

auto computeBkModP(const long &p, const long &k) -> mpz_class
{
    if (k == 0) return 1;
    if (k == 1) return (p == 2)? -1 : (p-1)/2;
    if (k &  1) return 0;
    if (p <= 3) return -1;

    long m = k % (p-1);
    if (m == 0) return -1;

    mpz_class g = computePrimitiveRoot(p);
    mpz_class r = computePowerMod(g, k-1, p);
    mpz_class u = (g + ((g % 2 == 1)? 0 : p) - 1) / 2;
    mpz_class S = 0, X = 1, Y = r;


    mpz_class hp = (p-1)/2, q, h, t;
    for (long i=1; i<=hp; i++) {
        q = norm( (g*X)/p, p);
        h = norm( (q-u)%p, p);
        t = norm( (h*Y)%p, p);
        S = norm( (S-t)%p, p);
        X = norm( (g*X)%p, p);
        Y = norm( (r*Y)%p, p);
    }
    mpz_class ans = computePowerMod(g, k, p);

    ans = computeInvertMod(p+1-ans, p);

    ans = norm( (S * ans) % p, p);
    ans = norm( (2 * ans) % p, p);
    ans = norm( (k * ans) % p, p);

    return ans;
}

auto congruent(const mpz_class &a, const mpz_class &b, const mpz_class &m) -> mpz_class
{
    if (a == 1 && b == 1) return mpz_class {1};
    mpz_class inv = computeInvertMod(a, m);
    return (b * inv) % m;
}

auto computeCRT(vector<tuple<mpz_class, long>> &residue) -> mpz_class
{
    mpz_class mul_m = 1;
    for (auto top : residue) {
        mul_m *= get<1>(top);
    }

    mpz_class z = 0, M, X, b, m;
    for (auto top : residue) {
        b = get<0>(top);
        m = get<1>(top);
        M = mul_m / m;
        X = congruent(M, 1, m);
        z += M * X * b;
    }
    while (z > 0) {
        z -= mul_m;
    }
    return z + mul_m;
}

auto genGraph(std::string strP, std::string strTime) -> void
{
    Py_Initialize();
    PyRun_SimpleString("import matplotlib");
    PyRun_SimpleString("matplotlib.use('Agg')");
    PyRun_SimpleString("import matplotlib.pyplot as plt");
    PyRun_SimpleString(strP.c_str());
    PyRun_SimpleString(strTime.c_str());
    PyRun_SimpleString("plt.plot(p, time, 'g*-')");
    PyRun_SimpleString("plt.title('Elapsed Time for each P')");
    PyRun_SimpleString("plt.xlabel('P')");
    PyRun_SimpleString("plt.ylabel('Time used (msecs)')");
    PyRun_SimpleString("plt.grid()");
    PyRun_SimpleString("plt.savefig('tgraph.png')");
    Py_Finalize();
    cout << "Generated tgraph.png" << endl;
}

using crt_t = tuple<mpz_class, long>;
using primeList_t = deque<long>;

auto distribute(long k, primeList_t primeList) -> vector<crt_t>
{
    vector<crt_t> rp;
    stringstream ssP, ssTime;
    ssP << "p = [";
    ssTime << "time = [";
    cout << "Prime Queue Size = " << primeList.size() << endl;

    while (!primeList.empty()) {
        long pp = primeList.front();
        primeList.pop_front();
        auto p_stime = chrono::high_resolution_clock::now();
        crt_t tt = make_tuple(computeBkModP(pp,k), pp);
        auto p_etime = chrono::high_resolution_clock::now();
        ssP << pp << ", ";
        ssTime << chrono::duration_cast<chrono::milliseconds>(p_etime - p_stime).count() << ", ";
        rp.push_back(tt);
    }
    ssP << "]";
    ssTime << "]";
    genGraph(ssP.str(), ssTime.str());
    return rp;
}

auto B(long k) -> mpq_class
{
    mpq_class bern_base[] {mpq_class {1, 1}, mpq_class {1, 2}, mpq_class {1, 6} };
    if (k < 3) return bern_base[k];

    if (k & 1) return mpq_class {0, 1};
    long Y = long(ceil((k+0.5) * log2(k)));
    if (Y < 37) Y = 37;
    PrimeTable primeTable(Y);
    mpz_class dk = computeDk(k, primeTable);
    long beta = long(ceil( (k+0.5) * log2(k) - 4.094 * k + 2.470 + log2(dk.get_d())));
    long p = 3;
    mpz_class M_ {1};
    mpz_class twoPowerBetaPlusOne;
    mpz_ui_pow_ui(twoPowerBetaPlusOne.get_mpz_t(), 2, beta+1);

    while (M_ < twoPowerBetaPlusOne) {
        p = primeTable.nextPrime(p);
        if (k % (p-1) != 0) {
            M_ *= p;
        }
    }

    long X = p;
    mpz_class M {1};
    p = 2;
    primeList_t primeList;

    while (p <= X) {
        if (k % (p-1) != 0) {
            primeList.push_back(p);
            M *= p;
        }
        p = primeTable.nextPrime(p);
    }

    auto rp = distribute(k, primeList);
    mpz_class R = computeCRT(rp);
    mpz_class N_ = norm((dk * R) % M, M);
    mpz_class nk = (k % 4 == 2)? N_ : N_ - M;
    return mpq_class {nk, dk};
}

auto main(int argc, char *argv[]) -> int
{
    if (argc != 2) {
        cout << "usage: " << argv[0] << " m" << endl;
        return 0;
    }
    auto t_stime = chrono::high_resolution_clock::now();
    cout << "B(" << argv[1] << ") = " << B(atoi(argv[1])) << endl;
    auto t_etime = chrono::high_resolution_clock::now();
    cout << "Total Time used: " << chrono::duration_cast<chrono::milliseconds>(t_etime - t_stime).count() << " msecs" << endl;
    return 0;
}

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

auto genGraph(std::string strP, std::string strTime) -> void

{

Py_Initialize();

PyRun_SimpleString("import matplotlib");

PyRun_SimpleString("matplotlib.use('Agg')");

PyRun_SimpleString("import matplotlib.pyplot as plt");

PyRun_SimpleString(strP.c_str());

PyRun_SimpleString(strTime.c_str());

PyRun_SimpleString("plt.plot(p, time, 'g*-')");

PyRun_SimpleString("plt.title('Elapsed Time for each P')");

PyRun_SimpleString("plt.xlabel('P')");

PyRun_SimpleString("plt.ylabel('Time used (msecs)')");

PyRun_SimpleString("plt.grid()");

PyRun_SimpleString("plt.savefig('tgraph.png')");

Py_Finalize();

cout << "Generated tgraph.png" << endl;

}

ผมเลือกที่ใช้งานให้ง่ายที่สุด โดยทำ string ให้สำเร็จเรียบร้อยแล้วป้อนเข้าไปสู่ PyRun_SimpleString() โดยที่ก่อนใช้งานนั้นก็ใช้ Py_Initialize() และปิดท้ายด้วย Py_Finalize() ภายในผมเรียกเอา matplotlib มาสร้างกราฟครับ ผลลัพธ์เป็นแฟ้มชื่อว่า tgraph.png

ก่อนรันต้องคอมไพล์โปรแกรมก่อนครับ อาจดูยุ่งยากเล็กน้อย ถ้าเป็น *buntu ใช้คำสั่งนี้ครับ

g++ -std=c++11 -O3 -o bern_tgraph bern_tgraph.cpp -lgmpxx -lgmp -lpython3.4m -I /usr/include/python3.4

1	g++ -std=c++11 -O3 -o bern_tgraph bern_tgraph.cpp -lgmpxx -lgmp -lpython3.4m -I /usr/include/python3.4

แต่ถ้าเป็น Windows ให้ใช้

g++ -Wall -std=c++11 -O3 -o bern_tgraph bern_tgraph.cpp -lgmpxx -lgmp -lpython34 -Ic:\mingw\include -Ic:\python\include -Lc:\mingw\lib -Lc:\python\libs

1	g++ -Wall -std=c++11 -O3 -o bern_tgraph bern_tgraph.cpp -lgmpxx -lgmp -lpython34 -Ic:\mingw\include -Ic:\python\include -Lc:\mingw\lib -Lc:\python\libs

เมื่อรันโปรแกรม

./bern_tgraph 1000

1	./bern_tgraph 1000

จะได้ผลลัพธ์เป็นกราฟ tgraph.png ดังนี้

ผลลัพธ์ที่ได้น่าสนใจมากครับ พบว่ามีฐานเป็นเส้นตรงที่เฉียงขึ้นเรื่อยๆ แต่ก็มีบางค่าใช้เวลามากกระโดดขึ้นไปเลย สิ่งที่ตอบคำถามได้อย่างชัดเจนก็คือแต่ละ p ใช้เวลาไม่เท่ากันและมีแนวโน้มว่าค่า p ยิ่งมากขึ้นยิ่งมีฐานที่สูงขึ้น โอกาสที่กระโดดสูงขึ้นก็มีมากกว่า ทำให้ใช้เวลามากกว่า ดังนั้นจากคำถามว่าถ้าเรามีตัวประมวลผล 568 ตัวเท่ากับจำนวน p นั้น งานจะเสร็จเร็วแค่ไหน บอกได้เลยว่า ใครเสร็จก่อนก็รอตัวเปล่าครับ ถ้า p ที่ประมาณ 3,000 ยังไม่เสร็จงานนี้ก็ไม่จบไปกระบวนการต่อไปไม่ได้ ซึ่ง p ที่ประมาณ 3,000 ใช้เวลาถึง 550msecs

ในชีวิตจริงเราคงไม่ได้มีหน่วยประมวลผลได้มากถึง 568 ตัวหรอกครับ ผมมี Banana Pi อยู่ 3 บอร์ดหรือ 6 cores ผมเอาตัวเลข 6 ตรงนี้มาใช้ก็แล้วกัน 568/6 ได้ประมาณ 95 หมายความว่าผมแบ่งให้แต่ละคอร์ประมวลผลค่า p 95 ค่าหรือเรียกฟังก์ชัน computeBkModP(p, k) 95 ครั้งนั่นเอง ถ้าผมแบ่งแบบง่ายๆ อย่างเช่น 95 ค่าแรก ใช้คอร์แรกและ 95 ค่าต่อไปใช้คอร์ถัดไป แบ่งแบบนี้ไปจนครบ แบบนี้จะทำงานได้เร็วไหม

เดาไม่ยากใช่ไหมครับคอร์สุดท้ายทำงานหนักสุดๆ ผิดกับคอร์แรกเสร็จก่อนแล้วนั่งเฉย วิธีนี้เป็นวิธีที่ไม่มีประสิทธิภาพอย่างแรงครับ โจทย์จะยิ่งยากกว่านี้ถ้าเราเพิ่มตัวแปรเข้าไปอีกก็คือ ความเร็วในการประมวลผลแต่ละคอร์ไม่เท่ากัน ดังนั้นจึงมีศาสตร์แยกออกเป็นแขนงหนึ่งเลยครับว่าด้วยการจัด Schduling ทำอย่างไรให้เครื่องจักรที่เรามีนั้นสามารถทำงานได้มีประสิทธิภาพสูงสุดตลอดเวลา

ทิ้งท้าย

บทความนี้เราเริ่มจากกฏของแอมดาล ผมใช้มันเป็นฐานในการนิยามกฏของอู๋ ซึ่งจะใช้เพื่อวัดศักภาพของเนื้อหาที่เราจะกล่าวถึงในบทต่อๆ ไป ในบทนี้ผมได้ปูพื้นเกี่ยวกับทฤษฎีการประมวลผลแบบขนานอย่างง่ายให้ท่านได้อ่านกันเพลินๆ แล้ว ในบทต่อไปคงถึงเวลาเสียทีทีที่โปรแกรมเราจะทำงานแบบขนานได้ ไว้ให้ถึงวันนั้นครับ

[Total: 7 Average: 3.6/5]

ก้าวแรก HPC #07: เตรียมเสบียงเลี้ยงตัว สู่โลกแห่งการประมวลผลแบบขนาน

เกริ่นนำ

Dr. Gene Amdahl ผู้นิยามขอบเขตการประมวลผลแบบขนาน

กฏของอู๋

กลับมาที่อัลกอริทึมการหา Bernoulli Number ของ Dr. Harvey

จับความเร็ว computeBkModP(p, k)

ทิ้งท้าย

You may also like...

Leave a Reply Cancel reply

เนื้อหา

ติดต่อ

ช่องทางอื่นในการติดตาม

ก้าวแรก HPC #07: เตรียมเสบียงเลี้ยงตัว สู่โลกแห่งการประมวลผลแบบขนาน

เกริ่นนำ

Dr. Gene Amdahl ผู้นิยามขอบเขตการประมวลผลแบบขนาน

กฏของอู๋

กลับมาที่อัลกอริทึมการหา Bernoulli Number ของ Dr. Harvey

จับความเร็ว computeBkModP(p, k)

ทิ้งท้าย

You may also like...

ล้อมวงกันเข้ามา จะเทศนาเรื่อง High Performance Computing

Functional Programming #4 : List Processing

Functional Programming #1 : ก้าวแรก

Leave a Reply Cancel reply

เนื้อหา

ติดต่อ

ช่องทางอื่นในการติดตาม