Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #31431 > unrolled thread

Dokładny podział integera na k jednakowych integerów

Back to article view | Back to pl.comp.programming

Contents

  Dokładny podział integera na k jednakowych integerów Borneq <borneq@antyspam.hidden.pl> - 2018-01-30 18:39 +0100
    Re: Dokładny podział integera na k jednakowych integerów Borneq <borneq@antyspam.hidden.pl> - 2018-01-30 18:54 +0100
      Re: Dokładny podział integera na k jednakowych integerów Borneq <borneq@antyspam.hidden.pl> - 2018-01-30 18:56 +0100
        Re: Dokładny podział integera na k jednakowych integerów Borneq <borneq@antyspam.hidden.pl> - 2018-01-30 19:35 +0100

#31431 — Dokładny podział integera na k jednakowych integerów

To coś co ma wiele wspólnego przy powiększaniu rastra metodą Nearest 
przy niecałkowitym powiększeniu.

Metoda naiwna:
void divide_float(int n, int k)
{
	double interval = double(n)/k;
	//double
	for (int i=0; i<k; i++)
	{
		printf("%d %f %f\n",i,i*interval, (i+1)*interval);
	}
}

chcę działać na integerach ale i tak mam kłopot z zaokrągleniami:
void divide_int(int n, int k)
{
	double interval = double(n)/k;
	//int
	uint32_t intPartPos, fracPartPos;
	uint32_t intPartDelta,fracPartDelta,oldFrac;
	intPartPos = 0; fracPartPos = 0;
	intPartDelta = floor(interval);
	fracPartDelta = floor((interval - intPartDelta) * 65536 * 65536);
	for (int i = 0; i<k; i++)
	{
		intPartPos += intPartDelta;
		oldFrac = fracPartPos;
		fracPartPos += fracPartDelta;
		if (oldFrac > fracPartPos) // when LongWord overflow
			intPartPos++;
		printf("%d %d\n", i, intPartPos);
	}
}

divide(10, 3) zwraca 3,6,9 zamiast 3,6,10 dlatego że w ostatnim jest 
błąd rzędu 2^-32 i to wystarczy by było źle.

[toc] | [next] | [standalone]

#31432

W dniu 30.01.2018 o 18:39, Borneq pisze:
>      fracPartDelta = floor((interval - intPartDelta) * 65536 * 65536);

fracPartDelta = ceil((interval - intPartDelta) * 65536 * 65536);

ceil zamiast floor tutaj pomaga ale to niezbyt eleganckie rozwiązanie, 
trzeba nie używać interval ale wymiernego n/k, jak?

[toc] | [prev] | [next] | [standalone]

#31433

W dniu 30.01.2018 o 18:54, Borneq pisze:
> W dniu 30.01.2018 o 18:39, Borneq pisze:
>>      fracPartDelta = floor((interval - intPartDelta) * 65536 * 65536);
> 
> fracPartDelta = ceil((interval - intPartDelta) * 65536 * 65536);
> 
> ceil zamiast floor tutaj pomaga ale to niezbyt eleganckie rozwiązanie, 
> trzeba nie używać interval ale wymiernego n/k, jak?
ceil - nie!
a może to ma coś wspólnego z algorytmem Bresenhama?

[toc] | [prev] | [next] | [standalone]

#31434

W dniu 30.01.2018 o 18:56, Borneq pisze:
>> ceil zamiast floor tutaj pomaga ale to niezbyt eleganckie rozwiązanie, 
>> trzeba nie używać interval ale wymiernego n/k, jak?
> ceil - nie!

Rozwiązanie:
Chodzi o przydział wątków, więc mogę "po chamsku" wstawić ostatnią wartość:
vector<uint32_t> getRanges(int n, int k, int mintask)
{
	double interval = double(n) / k;
	if (interval<mintask)
	{
		k = n / mintask;
		interval = double(n) / k;
	}
	vector<uint32_t> result;
	result.push_back(0);
	uint32_t intPartPos, fracPartPos;
	uint32_t intPartDelta, fracPartDelta, oldFrac;
	intPartPos = 0; fracPartPos = 0;
	intPartDelta = (uint32_t)floor(interval);
	fracPartDelta = (uint32_t)floor((interval - intPartDelta) * 65536 * 65536);
	for (int i = 0; i<k - 1; i++)
	{
		intPartPos += intPartDelta;
		oldFrac = fracPartPos;
		fracPartPos += fracPartDelta;
		if (oldFrac > fracPartPos) // when LongWord overflow
			intPartPos++;
		result.push_back(intPartPos);
	}
	result.push_back(n);
	return result;
}


mintask to liczba , ile minimalnie obiektami może zająć się wątek, aby 
nie było nagle 1 czy 0.

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web