Liczby zaprzyjaźnione C (optymalizacja algorytmu)


(Wojtek49s) #1

Witam,

napisałem algorytm wyszukujący liczby zaprzyjaźnione w C. Jednak dla np. 10000000 wykonuje obliczenia w czasie 107s. Czy można bardziej zoptymalizować algorytm by wykonywał się szybciej oraz czy funkcję wyszukujące dzielniki poprawnie napisałem?

 


(kostek135) #2

Z cacheować wyniki? Są tylko 42 takie pary liczb, mniejszych niż milion.


(Wojtek49s) #3

tzn.?


(kostek135) #4

Tzn. liczysz sobie raz te 107 sekund, a następnie wynik zaszywasz w kodzie programu (dostęp w czasie stałym). Tych liczb jest mało. Tak się bardzo często robi z różnymi magicznymi liczbami pierwszymi w STL-u.


(Wojtek49s) #5

Takie rozwiązanie odpada :wink: (bo na lab  …)


(kostek135) #6

Nie rozumiem czemu odpada. Moim zdaniem jest to prosta obserwacja tego, że zbiór liczb spełniających warunki jest rzadki, a do tego jego rozwiązanie jest klasy NP-Hard. W celu optymalizacji stosujemy prosty hard-kod, bądź ujmując profesjonalnie metodę słownikowania.


(Wojtek49s) #7

 


(kostek135) #8

Jedyna optymalizacja jaką widzę, to zmniejszenie liczby if-ów przy drugim odwołaniu do funkcji suma dzielników. Po jedno razowym jej przejściu 

for(i=2; i<=where; i++)
		if(liczba%i == 0)

jak już raz przejdziesz tego if-a, to możesz zapamiętywać w jakimś zbiorze, które liczby go spełniły i wtedy przy kolejnych wywołania po prostu pominąć (wykonać tylko dla liczb ze zbioru). Ale ponieważ wywołania są tylko 2 to może przyśpieszy sekundę, czy dwie.


(Wojtek49s) #9

Dzięki :wink:


(nintyfan) #10

Czym są liczby zaprzyjaźnione? Czy chodzi o liczby sprężone, a może o liczby zespolone?


(Wojtek49s) #11

https://pl.wikipedia.org/wiki/Liczby_zaprzyjaźnione

Liczby zaprzyjaźnione  to para różnych liczb naturalnych, takich że suma dzielników każdej z tych liczb równa się drugiej (nie uwzględniając tych dwóch liczb jako dzielników).

Pierwszą parą takich liczb, która została podana już przez Pitagorasa, jest para liczb 220 i 284, ponieważ:

  • 220 = 1 + 2 + 4 + 71 + 142 (dzielniki 284)
  • 284 = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 (dzielniki 220)

Nie wiadomo, czy istnieje nieskończenie wiele par liczb zaprzyjaźnionych i czy istnieje taka para liczb o różnej parzystości.


(enedil) #12

Niestety, chyba zbyt duże wykorzystanie pamięci, bo gdzieś po 430402 dostaję segfaulta.

⌁ [enedil:~/Desktop] 5s 139 $ cat MojaWersja.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

int sumaDzielnikow(int liczba);

int main()
{
	int liczbaPierwsza=0;
	int liczbaDruga=0;
	int i=0;
	int wprowadzona;

	printf(": ");
	scanf("%d",&wprowadzona);

	clock_t t;
	t=clock();

    int *sumy;
    sumy = malloc((wprowadzona + 1) * sizeof(int));
    sumy[0] = 0;
    sumy[1] = 1;

    for(i = 2; i <= wprowadzona; i++) {
        sumy[i] = sumaDzielnikow(i);
    }

	for(i = 1; i <= wprowadzona; i++){
	   liczbaPierwsza = i;
	   liczbaDruga = sumy[liczbaPierwsza];
	   if(liczbaDruga > liczbaPierwsza)
		  if(sumy[liczbaDruga] == liczbaPierwsza)
			 printf("%d\t\t\t%d\n\n", liczbaPierwsza, liczbaDruga);
	}

	t = clock()-t;
	printf("\nCzas dzialania programu: %f\n",((float)t/CLOCKS_PER_SEC));

	return 0;
}

int sumaDzielnikow(int liczba)
{
	int sumaDz=1;
	int i;
	int where;

	where=floor(sqrt(liczba));

	for(i=2; i<=where; i++)
	    if(liczba%i == 0)
		    if((liczba/i) != i)
			    sumaDz+=i+liczba/i;
			else
			    sumaDz+=i;
	return sumaDz;
}
⌁ [enedil:~/Desktop] $ clang MojaWersja.c -o moja
MojaWersja.c:56:4: warning: add explicit braces to avoid dangling else [-Wdangling-else]
                        else
                        ^
1 warning generated.
⌁ [enedil:~/Desktop] $ clang TwojaWersja.c -o twoja
TwojaWersja.c:47:4: warning: add explicit braces to avoid dangling else [-Wdangling-else]
                        else
                        ^
1 warning generated.
⌁ [enedil:~/Desktop] $ ./moja
: 10000
220 284

1184 1210

2620 2924

5020 5564

6232 6368


Czas dzialania programu: 0.004872
⌁ [enedil:~/Desktop] 4s $ ./twoja
: 10000
220 284

1184 1210

2620 2924

5020 5564

6232 6368


Czas dzialania programu: 0.005998
⌁ [enedil:~/Desktop] 3s $ ./moja
: 1000000
220 284

1184 1210

2620 2924

5020 5564

6232 6368

10744 10856

12285 14595

17296 18416

63020 76084

66928 66992

67095 71145

69615 87633

79750 88730

100485 124155

122265 139815

122368 123152

141664 153176

142310 168730

171856 176336

176272 180848

185368 203432

196724 202444

280540 365084

308620 389924

319550 430402

Segmentation fault: 11

 


(Wojtek49s) #13

Dzięki enedil za propozycję, ale pamięć dynamiczna tutaj się nie sprawdzi bo nie wiem jaką liczbę wprowadzi na wejściu prowadzący (a będzie duża :wink: ). Faktem jest to, że tylko raz odwołujesz się do funkcji sumaDzielnkow() co wpływa bardzo na szybkość.

Czy jest inna możliwość ?

 

edit: 

sumy = malloc((wprowadzona + 1) * sizeof(int));

nie powinno być:

sumy = (int*) malloc((wprowadzona + 1) * sizeof(int));

?


(enedil) #14

Nie dokońca rozumiem jak może to pomóc, ale dla liczb względznie pierwszych, funkcja ta jest łączna multiplikatywnie, czyli sumaDzielnkow(a*b) = sumaDzielnkow(a) * sumaDzielnkow(b).

Zaufane źródła twierdzą, że nie ma to znaczenia.


(tomms) #15

 

Takie rzeczy szybko zdiagnozujesz korzystając z debuggera, przykład:

/home/tomek/roboczy/prog/test$ clang -g -o a a.c -lm
a.c:59:4: warning: add explicit braces to avoid dangling else [-Wdangling-else]
                        else
                        ^
1 warning generated.
/home/tomek/roboczy/prog/test$ ./a > /dev/null
1000000
Segmentation fault (core dumped)
/home/tomek/roboczy/prog/test$ gdb -q a a.core
/home/tomek/.gdbinit:1: Error in sourced command file:
Undefined command: "python". Try "help".
Core was generated by `a'.
Program terminated with signal 11, Segmentation fault.
Reading symbols from /lib/libm.so.5...done.
Loaded symbols for /lib/libm.so.5
Reading symbols from /lib/libc.so.7...done.
Loaded symbols for /lib/libc.so.7
Reading symbols from /libexec/ld-elf.so.1...done.
Loaded symbols for /libexec/ld-elf.so.1
#0 0x0000000000400985 in main () at a.c:36
36 if(sumy[liczbaDruga] == liczbaPierwsza)
(gdb) q

 

I już widzisz że wychodzisz poza tablicę ‘sumy’, dodaj warunek sprawdzający czy liczbaDruga nie jest większa niż rozmiar tablicy:

if(liczbaDruga > liczbaPierwsza && liczbaDruga < wprowadzona+1)
       {
          if(sumy[liczbaDruga] == liczbaPierwsza)
             printf("%d\t\t\t%d\n\n", liczbaPierwsza, liczbaDruga);
        }

ale jeśli algorytm ma być prawidłowy to musisz większy rozmiar tablicy zadać.

 


(Wojtek49s) #16

tomms i enedil DZIĘKI za pomoc !!! =D

Przy wejściu 10000000 tylko ~70s ! (33mb ram)


(stasinek) #17

I co, to wszystko? Dostateczny z minusem :slight_smile:

Funkcja sumaDzielników jest nadal do kitu ;) Skoro masz tablice dlaczego nie liczysz sumy dzielników przy użyciu mnożeń tylko reszty z dzielenia? Raz że złożoność zamiast n*logn masz n^2, dwa, że wykorzystujesz dzielenia co zajmuje od 20 do 80 cykli procesora(zamiast 4). Poza tym zapotrzebowanie na RAM w stylu Chrome, bo dla zakresu 1mld liczb wyniesie aż 4-8GB. Ale w tej sprawie nie mam koncepcji.

Na moim kompie wykonanie tej niby lepszej wersji zajmuje aż 650s (Pentium M ULV 1.1GHz) myśle że można by to zbić do 200s (u Ciebie do 10-20s). 


(Wojtek49s) #18

Poprawka na

int sumaDzielnikow(int liczba)
{
	int sumaDz=1;
	int i;
	//int where;

	//where=floor(sqrt(liczba));

	for(i=2; /*i<=where*/ i*i<=liczba; i++)
	    if(liczba%i == 0)
		    if((liczba/i) != i)
			    sumaDz+=i+liczba/i;
			else
			    sumaDz+=i;
	return sumaDz;
}

Poprawiła czas 69s ;). Dzięki! Temat do zamknięcia, bo oddaje za 1h.


(stasinek) #19

Taka optymalizacja to żadna optymalizacja, nie o to mi chodziło, okej za póxno na poprawki. Ale dlaczego temat do zamkniecia? Jesteś pewny zaliczenia? Jako jedyny miałeś i bedziesz mieć takie zadanie? Na temat problemu nie można dalej prowadzić dyskusji? Optymalizacje sprawdze we własnym zakresie, w swoim czasie dla własnej ciekawości skoro temat chcesz zamykać.

3.13 Zabrania się umieszczania próśb w celu odrobienia pracy domowej, zleceń (np. zrobienie strony WWW, napisanie kodu, i.t.p.), zaliczeń etc. jak i podawania rozwiązań w organizowanych quizach.


(Drobok) #20

Kto tak powiedział ? :stuck_out_tongue:

,można spróbować podmienić funkcję sumy dzielników na Funkcje σ, ew podzielić zadanie na procesy