[C] Szybkość algorytmów zliczających liczbę cyfr

[MichalProg]

Dzień dobry.

Ku mojemu zdziwieniu okazało się, że algorytm zrobiony bez funkcji matematycznej (\(\displaystyle{ \log _{10}}\)), jest szybszy, niż algorytm z tą funkcją.

Sprawa wygląda tak:

Kod: Zaznacz cały

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>

#define ROZMIAR 10000000

int iloscCyfr(int liczba)
{
	int ilosc = 1;
	
	while (liczba)
	{
		liczba /= 10;
		
		if (liczba == 0)
			break;
		
		else
			ilosc++;
	}
	
	return ilosc;
}

void wypelnijLosowo(int * tab, int n, int mini, int maxi)
{
	int i = 0;
	
	for (i = 0; i < n; i++)
		tab[i] = mini + rand() % (maxi - mini + 1);
}

int main()
{
	int * liczby = (int *)malloc(ROZMIAR * sizeof(int));
	int czas;
	int i;
	
	srand(time(0));
	wypelnijLosowo(liczby, ROZMIAR, 999999999, 1000000099);
	
	czas = clock();
	for (i = 0; i < ROZMIAR; i++)
		iloscCyfr(liczby[i]);
	printf("%d
", clock() - czas);
	
	czas = clock();
	for (i = 0; i < ROZMIAR; i++)
		log10((double)liczby[i]) + 1;
	printf("%d
", clock() - czas);
	
	free(liczby);
	
	return 0;
}

Okazuje się, że algorytm bez logartmu, ma czas działania, prawie o 12% korzystniejszy. Jak można to wyjaśnić?

Kod: Zaznacz cały

652
739

[kalwi]

Kod: Zaznacz cały

#define ROZMIAR 10000000

Stosowanie #define do stałych jest passé. Tak nie należy robić.

Kod: Zaznacz cały

   wypelnijLosowo(liczby, ROZMIAR, 999999999, 1000000099);

Kod: Zaznacz cały

void wypelnijLosowo(int * tab, int n, int mini, int maxi)

Bez sensu. UB.

Kod: Zaznacz cały

   int czas;

Kod: Zaznacz cały

   czas = clock();

Znowu niepoprawnie.

Kod: Zaznacz cały

   printf("%d
", clock() - czas);

Kolejne UB.

Zakładając jednak, że te poprzednie błędy nie wpływają na resztę to odpowiedź leży w implementacji funkcji log10 w C.

Kod: Zaznacz cały

  double log10(double x)
  {
          if (__IsNan(x)) {
                  errno = EDOM;
                  return x;
         }
          if (x < 0) {
                  errno = EDOM;
                  return -HUGE_VAL;
          }
          else if (x == 0) {
                  errno = ERANGE;
                  return -HUGE_VAL;
          }
  
          return log(x) / M_LN10;
  }
  

[MichalProg]

Co Ci nie pasuje w tym kodzie?

Na początek, co Ci nie pasuje w wywołaniu funkcji wypelnijLosowo()?
Potem, jak rozumiem, chodzi Ci, o przypisanie wyniku, zmiennej typu clock_t, do int, tak?

Ale co Ci nie pasuje w tej funkcji?

[kalwi]

To, że w tej funkcji niekoniecznie mini będzie mniejsze od maxi

I tak, chodzi mi o przypisanie inta do clock_t. To najpewniej jest to samo - ale nie musi (np. u mnie nie jest).

[MichalProg]

Założyłem, że tak, jak przy podawaniu rozmiaru tablicy, tak i tu, odpowiedzialność na poprawności wpisanego przedziału, spoczywa na programiście. Mógłbym sprawdzać, czy \(\displaystyle{ mini <= maxi}\), i ew. "swapować", ale tu chodziło o sprawdzenie szybkości. Poza tym kod był pisany na szybko. W każdym razie, dziękuję za uwagi.

Jednak odpowiedź na moje pytanie (z 1 postu) mnie nie satysfakcjonuje. Nadal nie wiem, czemu log10 jest wolniejszy.

[a4karo]

Nie dziw się, że ten algorytm jest szybszy: ilość cyfr nie identyfikuje liczby, a logarytm tak, więc logarytm niesie dużo więcej informacji.

[kalwi]

Chodzi mi o to, że może dojść do przekroczenia zakresu - dałeś liczbę 999 999 999, a int ma zagwarantowane, że ma przynajmniej 2 bajty - i jeśli tyle ma, to wtedy następuję przekroczenie zakresu. Oczywiście najpewniej to się nie stanie na większości maszyn, ale na części tak może być. A przekroczenie zakresu liczby ze znakiem to jest UB.
Najlepiej tutaj byłoby użyć typu uint32_t.

Co do pytania: nie da się odpowiedzieć dokładnie. Operacja dzielenia najpewniej jest wysyłana prosto do ALU, z kolei log10 może być zaimplementowany np. jako log dzielony przez stałą (a sama funkcja log może być zaimplementowana np. jako szereg Taylora). Bez implementacji funkcji można sobie spekulować.