🚀 go-pugleaf

On 30.09.2016 21:46, Borneq wrote:
> Nie udało się z biblioteką MPIR. Wersja Release dla trybu Debug
> potrzebowała jakiejś biblioteki, która nie dała się skompilować, a
> wersja z najnowszych źródeł Githuba miała problemy kompilacji dla DLL i
> static.
> Więc użyłem boost/multiprecision/cpp_int.hpp
> Rozkładam 5742507205757425072053 metodą szkolną więc najpierw
> wielokrotnie dzieląc przez 2 a potem przez nieparzyste liczby (choć
> pierwszych jest znacznie mniej) do pierwiastka z liczby.
> otrzymuję:
> 3 7 197 402529 3448409664461
> Kompilacja przez GCC: 0.201 s natomiast VC++ udało się zejść do 0.053 s
> Dlaczego GCC tak tu nieefektywny? 3.8 x
> Może warto jeszcze spróbować LLVM?
> A VC++ dla trybu 64 bit nawet 0.0367 s!

U mnie

3 7 197 402529 3448409664461 0.0529229s  //wrersja cpp
3 7 197 402529 3448409664461 0.0805347s  //wersja gmp

kompiluję  prosto z QTcreatrora lub przez
g++  main.cpp -std=c++11  -O2 -lgmp -lgmpxx

Procesor mocno nienajnowszy AMD Phenom(tm) II X4 955.

Nie zapomniałęś o optymalizacji?  ;>




>
> void factor(const cpp_int n)
> {
>     cpp_int x = n;

Uwaga techniczna. Pobierasz stałą n, potem ją kopiujesz
do x i nigdy nie uzywasz ponownie.
Po to wymyślono przekazywanie przez wartość


void factor(cpp_int x)
{

:)

>     while ((x % 2) == 0) {
>         x /= 2;
>         std::cout << 2 << " ";
>     }
>     cpp_int i, e;
>     i = 3;
>     e = sqrt(x);
>     while (i <= e) {
>         while ((x % i) == 0) {
>             x /= i;
>             e = sqrt(x);
>             std::cout << i << " ";
>         }
>         i+=2;
>     }
>     if (x > 1)
>         std::cout << x << " ";
> }
>
> Jednak podglądając kod assebmblera VC++ są tam dwie funkcje : do_divide
> i divide_unsigned_helper
> Czy w bibliotece cpp_int była by funkcja łącząca div i mod?

Trzeba szukać nieco dalej, w kalsie number<>
http://www.boost.org/doc/libs/1_62_0/libs/multiprecision/doc/html/boost_multiprecision/ref/number.html

divide_qr(x,y,q,r)

Ale jak podmieniłem, było wolniej ;-)

Kody:
http://pastebin.com/Z7DcaHWc

pzdr
bartekltg

W dniu 30.09.2016 o 23:49, bartekltg pisze:
>> A VC++ dla trybu 64 bit nawet 0.0367 s!

GCC nie taki zły. Pod Linuxem w VirtualBoxie, co też może nieco 
spowalniać, choć niewiele bo nie odwołuję się dysku, to było
... 0.0246 s!
Dlaczego pod Windows tak nie chce optymalizować?, debug ma 0.5, release 
0.2 sekundy. Nie działa w trybie 64 bity.

W dniu 01.10.2016 o 00:18, Borneq pisze:
> W dniu 30.09.2016 o 23:49, bartekltg pisze:
>>> A VC++ dla trybu 64 bit nawet 0.0367 s!
>
> GCC nie taki zły. Pod Linuxem w VirtualBoxie, co też może nieco
> spowalniać, choć niewiele bo nie odwołuję się dysku, to było
> ... 0.0246 s!
> Dlaczego pod Windows tak nie chce optymalizować?, debug ma 0.5, release
> 0.2 sekundy. Nie działa w trybie 64 bity.
>
>
>
Gdy pod Linuxem wyłączyłem wszystkie optymalizację to 0.18 s a pod 
Windows 0.56

W dniu 01.10.2016 o 00:23, Borneq pisze:
>> GCC nie taki zły. Pod Linuxem w VirtualBoxie, co też może nieco
>> spowalniać, choć niewiele bo nie odwołuję się dysku, to było
>> ... 0.0246 s!
> Gdy pod Linuxem wyłączyłem wszystkie optymalizację to 0.18 s a pod
> Windows 0.56
Ciekawe, że pod Linuxem dla tego przykładu cpp_int jest 2 razy szybsze 
od GMP.

On Saturday, October 1, 2016 at 12:23:05 AM UTC+2, Borneq wrote:
> W dniu 01.10.2016 o 00:18, Borneq pisze:
> > W dniu 30.09.2016 o 23:49, bartekltg pisze:
> >>> A VC++ dla trybu 64 bit nawet 0.0367 s!
> >
> > GCC nie taki zły. Pod Linuxem w VirtualBoxie, co też może nieco
> > spowalniać, choć niewiele bo nie odwołuję się dysku, to było
> > ... 0.0246 s!
> > Dlaczego pod Windows tak nie chce optymalizować?, debug ma 0.5, release
> > 0.2 sekundy. Nie działa w trybie 64 bity.
> >
> >
> >
> Gdy pod Linuxem wyłączyłem wszystkie optymalizację to 0.18 s a pod 
> Windows 0.56

Optymalizator powinien działać tak samo, powinien zależeć od procesora a nie
od systemu. Nie używasz gorszych opcji, starszej wersji, innej (wersji)
biblioteki?

W dniu 30.09.2016 o 23:49, bartekltg pisze:
> 3 7 197 402529 3448409664461 0.0529229s  //wrersja cpp
> 3 7 197 402529 3448409664461 0.0805347s  //wersja gmp

Dlaczego wersja GMP jest wolniejsza: gdy sprawdzałem mnożenie w liczeniu 
silni, cpp i gmp były identyczne, tu mamy operacje modulo i dzielenie, 
przy czym biblioteka cpp wywołuje raz i gmp chyba dwa razy. Może wołać 
raz, jeśli te dwa operatory zamieniane są na jedną funkcję.

> kompiluję  prosto z QTcreatrora lub przez
> g++  main.cpp -std=c++11  -O2 -lgmp -lgmpxx
>
> Procesor mocno nienajnowszy AMD Phenom(tm) II X4 955.
>
> Nie zapomniałęś o optymalizacji?  ;>

Pod Linuxem działa bardzo szybko a pod Windows (MinGw): sprawdzałem 
programem CodeXL i okazuje się że funkcja dzielenia tylko ma 13.3 % 
czasu a około 60% mają funkcje pthread_XXX wołane z 
_Unwind_SjLj_Register, czyli obsługa przerwań wołane z funkcji dzielenia.

On Wednesday, October 5, 2016 at 3:58:26 AM UTC+2, Borneq wrote:
> W dniu 30.09.2016 o 23:49, bartekltg pisze:
> > 3 7 197 402529 3448409664461 0.0529229s  //wrersja cpp
> > 3 7 197 402529 3448409664461 0.0805347s  //wersja gmp
> 
> Dlaczego wersja GMP jest wolniejsza: gdy sprawdzałem mnożenie w liczeniu 
> silni, cpp i gmp były identyczne, tu mamy operacje modulo i dzielenie, 
> przy czym biblioteka cpp wywołuje raz i gmp chyba dwa razy. Może wołać 
> raz, jeśli te dwa operatory zamieniane są na jedną funkcję.
> 
> > kompiluję  prosto z QTcreatrora lub przez
> > g++  main.cpp -std=c++11  -O2 -lgmp -lgmpxx
> >
> > Procesor mocno nienajnowszy AMD Phenom(tm) II X4 955.
> >
> > Nie zapomniałęś o optymalizacji?  ;>
> 
> Pod Linuxem działa bardzo szybko a pod Windows (MinGw): sprawdzałem 
> programem CodeXL i okazuje się że funkcja dzielenia tylko ma 13.3 % 
> czasu a około 60% mają funkcje pthread_XXX wołane z 
> _Unwind_SjLj_Register, czyli obsługa przerwań wołane z funkcji dzielenia.



On Wednesday, October 5, 2016 at 3:58:26 AM UTC+2, Borneq wrote:
> W dniu 30.09.2016 o 23:49, bartekltg pisze:
> > 3 7 197 402529 3448409664461 0.0529229s  //wrersja cpp
> > 3 7 197 402529 3448409664461 0.0805347s  //wersja gmp
> 
> Dlaczego wersja GMP jest wolniejsza:

Z pełnym poczuciem znawstwa mogę powiedzieć:
cholera wie ;-)


> gdy sprawdzałem mnożenie w liczeniu 
> silni, cpp i gmp były identyczne, tu mamy operacje modulo i dzielenie, 
> przy czym biblioteka cpp wywołuje raz i gmp chyba dwa razy. Może wołać 
> raz, jeśli te dwa operatory zamieniane są na jedną funkcję.

Podejrzewam raczej drobiazgi jak nieszczęsne dodawanie +2
czy inicjalizacja. 

Jak zbadasz dokałdniej problem, może warto napsiać do GMP.
Pewnie trzeba byłoby sprawdzioc, czy robią na pewno to samo. 
Wydaje mi się, że oba typy to liczby dowolnej (rosnącej w razei
potrzeby) długości zbudowane ze stałego kawałka i dynamicznie 
alokowanej papięci. 

pzdr
bartekltg

W dniu 05.10.2016 o 12:22, bartekltg pisze:
> Jak zbadasz dokałdniej problem, może warto napsiać do GMP.
> Pewnie trzeba byłoby sprawdzioc, czy robią na pewno to samo.
> Wydaje mi się, że oba typy to liczby dowolnej (rosnącej w razei
> potrzeby) długości zbudowane ze stałego kawałka i dynamicznie
> alokowanej papięci.

Pytałem się - biblioteka GMP ma działać na ogromnych liczbach, tutaj w 
przykładzie  dla #define itype mpz_int i itype a("3448409664461") - pierwsza
void test(const itype n)
{
	itype x = n;
	while ((x % 2) == 0) {
		x /= 2;
		std::cout << 2 << " ";
	}
	itype i = 3;
	itype e = sqrt(x);
	while (i <= e) {
		//if ((x % i) == 0) break;
		i+=2;
	}
}

lepiej działa gdy się zamieni na
   if (mpz_divisible_p(x.get_mpz_t(), i.get_mpz_t())) break;
czego nie mogę sprawdzić, bo się nie kompiluje
Ta liczb jest bardzo mała: limb jest = 1 (to chyba 64 bity)

W dniu 06.10.2016 o 14:52, Borneq pisze:
> lepiej działa gdy się zamieni na
>   if (mpz_divisible_p(x.get_mpz_t(), i.get_mpz_t())) break;
> czego nie mogę sprawdzić, bo się nie kompiluje
> Ta liczb jest bardzo mała: limb jest = 1 (to chyba 64 bity)

Reszta z dzielenia na liczbach o 6.5 tysiąca cyfr - ponad 3 razy 
szybciej na GMP.