Работа с большими номерами с характеристиками в стиле GMP в Go

Я изучаю Go, и я начал использовать пакет math/big для работы с целым числом произвольной длины.Работа с большими номерами с характеристиками в стиле GMP в Go

Я написал эту программу, которая вычисляет п-го числа Фибоначчи: (удалены в import ы):

func main() { 
    imax, _ := strconv.Atoi(os.Args[1]) 
    var a, b, c big.Int 
    a.SetUint64(0) 
    b.SetUint64(1) 
    for i := 0; i < imax; i++ { 
     c.Set(&b) 
     b.Add(&b, &a) 
     a.Set(&c) 
    } 
    fmt.Println(a.String()) 
}

Вот код программы C:

int main(int argc, char** argv) 
{ 
    int imax = atoi(argv[1]); 

    mpz_t a, b, c; 
    mpz_inits(a, b, c, NULL); 
    mpz_set_ui(a, 0); 
    mpz_set_ui(b, 1); 

    int i = 0; 
    for (i = 0; i < imax; i++) { 
     mpz_swap(a, b); 
     mpz_add(b, a, b); 
    } 

    char* astr = NULL; 
    astr = mpz_get_str(NULL, 10, a); 
    printf("%s\n", astr); 

    return EXIT_SUCCESS; 
}

Программа рассчитывает Go термин 100 000 в 0,1 секунду (средний), тогда как эквивалент C, использующий библиотеку GMP, работает только за 0,04 секунды. Это в два раза медленнее.

Есть ли способ получить такое же исполнение в моей программе Go?

источник

2016-03-25 Arno

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

Как это запрос на проверку кода? Я не хочу оптимизировать * эту * программу специально, но чтобы узнать, как получить те же самые функции на двух языках. Я попытался сделать обе программы настолько же похожими, насколько это возможно, чтобы получить необъективный бенчмарк. Ответ может быть другой арифметической арифметической библиотекой Go, например. – Arno

Если вы хотите сравнить операции, вам необходимо установить воспроизводимый тест. Мы не знаем, как вы компилируете и запускаете свой код. В моей системе код go вычисляет 10000 в ~ 55 мс. – JimB

Не печатайте на стандартный вывод, это медленно. Какой результат вы получите для этого кода?

package main 

import (
    "math/big" 
    "os" 
    "strconv" 
) 

func main() { 
    max, err := strconv.Atoi(os.Args[1]) 
    if err != nil { 
     panic(err) 
    } 
    a, b := big.NewInt(0), big.NewInt(1) 
    for i := 0; i < max; i++ { 
     a.Add(a, b) 
     a, b = b, a 
    } 
}

Go не ручной код ассемблера.

Ваша ценность 100 000 слишком мала для надежного теста. Используйте 1,000,000 или другое значение, которое длится не менее десяти секунд.

источник

2016-03-25 18:24:10 peterSO

Я пробовал с imax = 1,000,000, перенаправляя вывод в/dev/null, и для Go потребовалось 9 секунд, 3,6 секунды для C. Преимущество довольно ясное. Я попробую ваш код позже. – Arno

ОК, результаты с вашим кодом интересны. Он вычисляет 1,000,000-й термин за 4,5 секунды, а код C (без печати) занимает 3,5 секунды. Я думаю, что производительность зависит от библиотеки и будет похожа, если я использую привязку Go GMP. Благодаря ! – Arno

Переадресация вывода на '/ dev/null' не помогает: программе все равно нужно делать syscall каждый раз, когда что-то выводится. Пожалуйста, рассмотрите возможность использования контрольных средств стандартного пакета 'test'. И не печатайте что-либо в своем тестируемом коде - по крайней мере, когда вы не собираетесь специально тестировать ввод-вывод – kostix

В общем, GMP быстрее, потому что он создан для работы. Под капотом вы можете обнаружить, что он частично написан на сборке, что сокращает накладные расходы функций, может использовать некоторые инструкции CPU, такие как ADX и так далее.

Если вам небезразлична производительность, вы можете использовать рутину mpz_fib_ui, которая была бы еще быстрее, поскольку она выигрывает от некоторых математических приемов.

Прямой ответ на ваш вопрос, вероятно, заключается в использовании привязки Go для GMP.

источник

2016-03-25 18:22:09

Работа с большими номерами с характеристиками в стиле GMP в Go

ответ

Смежные вопросы