BGAFC Vendégkönyv

Σ: 1 post

TCH (statz)

#1, Főfasz (10443)

5116 | #1f1c | ^ | Idézet | Fri, 10 Aug 2012 00:02:23 +02

31.46.*.*

*.catv.pool.telekom.hu

Flood3r: Megkaptam, válaszoltam, kösz itt is.

@Prometheus:
Flood3r, az arcodról is tegyél ide egy képet, hogy fölismerjünk! Ha nincs, csináld meg ascii-kódokban!

És ezek után a talira eljön állszakállban és napszemüvegben. ;)

Kiváncsi voltam, hogy hogyan lehet kioptimalizálni a 255-el való osztást, hogy régi gépeken is jól menjen.
Sok hülye ember sok hülyeséget mond az interneten, itt viszont van egy értelmes megközelítés is, ami azt mondja, hogy mivel 1/255 majdnem ugyanannyi mint 257/65536, ezért x/255 = (x*257) / 65536, amiből az osztást ki lehet optimalizálni: (x*257) >> 16. Én még hozzátenném, hogy a szorzást is, mert olyan szám (legyen y) amiben csak két bit van bekapcsolva (legyen mondjuk n és m) az felírható így: x*y = (x << m) + (x << n) (igen, ha több bit van bekapcsolva, akkor ugyanígy bevehető a képletbe, csak sok bitnél már nincs értelme). És ésszerűen, ha az egyik bit a nulladik, akkor forgatni sem kell, vagyis x*257 = (x << 8) + x.
Vagyis felírható, hogy x/255 = ((x << 8) + x) >> 16.
Fasza, mi? Hát nem. Két gond is van vele. Az egyik, hogy 1/255 != 257/65536. A különbség tízmilliomodos nagyságrendű. Vagyis tízmilliós nagyságrendű számoknál eltérés lesz a végeredményben. Tehát ez nemhogy 32, de még 24 bitre sem jó.
16-ra már az lenne, ha nem állna fennt az a bibi, hogyha x%255 == 0 akkor x/255 = ((x*257) / 65536) +1!
Ez persze nem gáz annyira, hozzá kell olyankor adni egyet, oszt csumi. Csak ahhoz meg kell a modulo 255 eredménye, vagyis még egy osztás a nyakunkon.
Itt azt mondják a modulo 255-re, hogy

x = (x & 65535) + (x >> 16);
x = (x & 255) + (x >> 8);
x = (x & 255) + (x >> 8);
x = (x + ((x + 1) >> 8)) & 255;

Ez ugyan 32 bites, de ha lehagyjuk a legelső sort, akkor jó ez 16 bitesre is.
Csakhogy nekünk nem maga a végeredmény kell, hanem csak az, hogy nulla-e vagy sem, mert ha igen, akkor hozzáadunk egyet a végeredményhez. Ez persze egy csak egy if lenne, de most optimalizálunk; nixif. :P
Az itt javasolt módszer: ((n | (~n + 1)) >> 31) & 1
Ez ugyan fordítva működik, 0 esetén 0 és ha nem az, akkor 1, de ez nem baj, xor 1 és máris megfordult. (Egyébként erre a bohóckodásra assembly esetén nincs szükség, ott a carryval lehet ügyködni.) Sz*rk: Itt se, csak még láma voltam C-ből. x != 0 is azt adja vissza, hogy 1.
Vagyis a végeredmény valami ilyesmi lesz:

// division by 255
// for 16 bit integer
result = ((x << 8) + x) >> 16;
x = (x & 255) + (x >> 8);
x = (x & 255) + (x >> 8);
x = (x + ((x + 1) >> 8)) & 255;
result += x != 0; // ez a jo
x = ((x | (~x + 1)) >> 7) & 1;
result += x ^ 1;

Mivel ez 16 bites, ez mondjuk jó a 8 bites gépekhez. Úgyhogy ugyanez 6502-ben:

; FUCK MICROSOFT

div255	LDA #0
	STA result
	STA result+1

;	check if x == 0, if yes return
	LDA x
	BNE +
	LDA x+1
	BNE +
	RTS

; =====================================
; result = ((x << 8) + x) >> 16

; h: x high
; l: x low
; hl: h+l
; hc: (hl >> 8) + h
; C: (hc >> 8)

; 24 16 8  0  -8 -16
; ========================
; 0  0  0  0  0  0  =x
; 0  0  h  l  0  0  *256
; 0  h  l  0  0  0  +x
; C  hc hl l  0  0  /65536
; 0  0  C  hc hl l

;	get h+l
+	LDA x
	CLC
	ADC x+1

;	add carry => get hc
	LDA x+1
	ADC #0
	STA result

;	check carry => get C
	BCC +
	INC result+1


; =====================================
; x = (x & 255) + (x >> 8)
; two times

+	LDX #1

;	get h+l again
-	LDA x
	CLC
	ADC x+1
	STA x

;	clear h
	LDA #0
	STA x+1

;	check carry => store carry as h
	BCC +
	INC x+1

+	DEX
	BPL	-

; =====================================
; if (x == 255) ++result;

;	 check if x == 255
	LDA x
	CLC
	ADC #1
	BNE ++

;	 increment result
+	LDA result
	ADC #1
	STA result
	BCC +
	INC result+1

+	RTS

x	.word 19374
result	.word 0

Tisztán, kommentek nélkül:

div255	LDA #0
	STA result
	STA result+1
	LDA x
	BNE +
	LDA x+1
	BNE +
	RTS

+	LDA x
	CLC
	ADC x+1
	LDA x+1
	ADC #0
	STA result
	BCC +
	INC result+1

+	LDX #1
-	LDA x
	CLC
	ADC x+1
	STA x
	LDA #0
	STA x+1
	BCC +
	INC x+1
+	DEX
	BPL	-

	LDA x
	CLC
	ADC #1
	BNE ++
+	LDA result
	ADC #1
	STA result
	BCC +
	INC result+1
+	RTS

x	.word 19374
result	.word 0

Viszont ez csak 16 bithez jó, 32-höz nem.

Mond egy másikat is, ami azt mondja, hogy a GCC-ben így oldják meg ugyanezt 32 biten: (x*0x80808081)>>39.
Na igen, de ehhez meg 64 bites aritmetika kellene.

Egyebet nem találtam sajnos. Na, akkor van valakinek ötlete, vagy infoja, hogy lehet 32 biten, 32 bites aritmetikát használva 255-el osztani, úgy, hogy csak bitműveleteket és összeadást/kivonást használunk?