Optimerings problem

[Stenmark]

Hej
Jag skulle behöva implementera en adderare som lägger ihop bitar ur variabler på samma bit position tex 3 st 8 bitar tal så här

Kod: Markera allt

1001 1100
0010 1101
1110 0010
------------
2121 2211

just nu gör jag det genom att genomlöpa hela varje variabel bitvis och lägger till för vajre etta jag får manuellt i en annan variabel med hjälp av if satser.
Det jag skulle behöva är en effektivare version, det jag sitter och funderar på är om man kan använda sig av logik funktioner/aritmetik som jobbar på hela variabeln åt gången vilket skulle minska körtiden rejält. Som det är nu så är algortimen kvardratisk och skalar därför rätt kass med fler variabler och större tal.

[JimmyAndersson]

Ett sätt:

Tänk varje byte som ett decimalt tal. Sedan är det bara att plussa ihop.
(Eftersom det är väldigt stora tal så får du förstås dela upp dem.)

Skulle det fungera?

[speakman]

Förstår nog inte riktigt hur du tänkt göra.
Ska du lagra summan av bit:ar hos två 8-bitars variabler i en array lika stor som antalet bitar?
Annars förstår jag inte hur du ska få in både 0 1 och 2 i bitfälten. Eller är det kvantdatorer du pysslar med?

En idé kan ju vara att klistra in din kod, så förstår man ju precis hur det ska se ut i slutänden...

Mvh
speakman

[Stenmark]

Att addera talen går inte eftersom att 1+1 binärt blir noll plus carry och man kan inte få ut carry för varje bit.

Jag kanske var lite luddig igår kväll, man ska nog inte skriva sånna inlägg för sent.
Jag ska förklara lite mer vad det är jag vill ha. Egentligen så är det inte så viktigt att få ut ett tal som "summan" det jag vill göra är att se om det finns flest ettor eller nollor i en "kolumn". Det sätt jag gör på nu är som speakman säger jag räknar alla ettor manuellt i två nästlad loopar och adderar i en array.
så en bättre förklaring skulle vara att jag vill ha ut ett resultat som ser ut så här:

Kod: Markera allt

1001 1100 
0010 1101 
1110 0010
------------
1010 1100

Nollorna ska dessutom vara dominanta, dvs om det finns lika många nollor som ettor så ska nollorna "vinna".
Jag hoppas någon förstår lite bättre vad jag vill åstakomma nu

EDIT: ändrade exemplet så det stämmer

[speakman]

Kod: Markera allt

int n,r;
unsigned char rows[3] = {0x9C, 0x2D, 0xE2};
int result[8] = {0,0,0,0,0,0,0,0};

for(r=0; n<sizeof(rows); n++)
	for(n=0; n<8; n++)
		result[1<<n] += (rows[n] & 1<<n) ? 1 : 0);

for(n=0; n<8; n++)
	printf("Kolumn %d: %d ettor", n, result[n]);

Mvh
speakman

[sodjan]

Processorfamilj ?
Favoritspråk ?

En metod är att först nollställa en räknare, sedan räkna upp med ett
för varje "1" och räkna ner med ett för varje "0".
Sedan, om räknaren > 0 så är svaret "1", annars "0".

Du behöver ju igentligen inte veta exakt hur *många* ettor
respektive nollor det är, bara vilka det är flest av, eller hur ?

Sen underlättar det om du visar korrekta exempel.
Kolla på ditt sista exempel en gång till...

[Stenmark]

Skriver i C och processorn är en freescale HC12 eller en frescale power PC MPC 565.
Sodjan: Jag gör så som du beskriver just nu, problemet är att algoritmen tar för lång tid då det krävs att jag genomlöper varje bit minst en gång för att räkna upp eller ner. Med lite större system så på säg 32 bitars tal och 10 tal så blir det 32*10=320 varv i loopen och det hinner jag helt enkelt inte med.
En lösning som jag funderar på är att köra logiska operationer på hela talet och på så sätt bara behöva loopa igenom anatalet tal det skulle då bli 10 varv istället för 320. Men frågan är om man kan bygga en logiska operation som klarar majoritet.
Dvs X ingångar i operationen och ut kommer 1 om det finns fler än X/2 ettor på ingången.

[speakman]

Eller så optimerar man loopen så den går snabbt. Jag kommer iaf inte på någon annat metod. I.o.m. att du har ett okänt antal rader, så måste man ju komma ihåg antalet bitar för alla rader.

Mvh
speakman

[sodjan]

> så måste man ju komma ihåg antalet bitar för alla rader.

Om du menar antalet "1" resp "0" för varje position, så tror jag inte det.
Det är inte det *absoluta* antalet "1" resp "0" som är intressant, utan bara
*rellationen* mellan antalet "1" resp "0". Jag tror att det går att göra rutinern
lite smartare genom att utnyttja det...

[speakman]

Men om du tänker dig in i en funktion som inte vet hur många gånger den kommer att anropas, så blir det väldigt svårt för den att "tänka tillbaka" om den inte får hålla i minnet nånting. Förstår du hur jag tänker?
Har man ett givet antal rader, så kan det eventuellt gå att optimera en del (vissa C-kompilatorer gör loopar ineffektiva av nån skum anledning...).

Mvh
speakman

[ahlsten]

Att funktionen måste "tänka tillbaka", minnas variabeln, är väl inget större problem då det i C-standarden finns lagringsklassen static som medför att variabeln förblir statisk mellan funktionsanropen?
Själva nöten var dock ursvår att knäcka, man vill ju hitta ett logiknät som löser det men som sagt...

[Icecap]

Nu fick jag en tanka som kanske inte är så bra men ändå, den kan halvera antalet nödvändiga beräkningar:

Om vi håller oss till 2 variabler åt gången gäller följande:
'1' i båda variabler ger '1' ut, '0' i någon av variablerna ger '0' ut.

Detta klarar en vanlig bitwise AND.

0010 1101
1110 0010
------------
0010 0000

Därmed har antalet nödvändiga iretationer halverats.

Jag har en liten tanka med att sedan AND'a alla resultaten av första AND'ning men jag har annat i tankerna just nu...

[exile]

Tja hur hade du tänkt att logisk operator? visst kan du minsta tids åt gången med ca 4-10gånger men med 32gånger har jag svårt att tro ska lyckas med...



Ett exemple på lite exemple som ska ta lite mindre tid på 32bitar cpu...

Kod: Markera allt

#define 	Antal = X; //max 255
unsigned int	data_in[Antal] = {något roligt} //Antar att int är 32 bitar
unsigned char	count_bit[32];
unsigned int	temp0,temp1,temp2,temp3,temp4,temp5,temp6,temp7 = 0;

for(int i = 0; i < Antal; i++){
	//
	temp0 += (data[i] & 0x01010101);
	temp1 += ((data[i] >> 1) & 0x01010101);
	temp2 += ((data[i] >> 2) & 0x01010101);
	temp3 += ((data[i] >> 3) & 0x01010101);
	temp4 += ((data[i] >> 4) & 0x01010101);
	temp5 += ((data[i] >> 5) & 0x01010101);
	temp6 += ((data[i] >> 6) & 0x01010101);
	temp7 += ((data[i] >> 7) & 0x01010101);
}

count_bit[0] = temp0 & 0xFF;
count_bit[1] = temp1 & 0xFF;
count_bit[2] = temp2 & 0xFF;
count_bit[3] = temp3 & 0xFF;
count_bit[4] = temp4 & 0xFF;
count_bit[5] = temp5 & 0xFF;
count_bit[6] = temp6 & 0xFF;
count_bit[7] = temp7 & 0xFF;

count_bit[8] = (temp1 >> 8) & 0xFF;
count_bit[9] = (temp2 >> 8) & 0xFF;
count_bit[10] = (temp2 >> 8) & 0xFF;
count_bit[11] = (temp2 >> 8) & 0xFF;
count_bit[12] = (temp2 >> 8) & 0xFF;
count_bit[13] = (temp2 >> 8) & 0xFF;
count_bit[14] = (temp2 >> 8) & 0xFF;
count_bit[15] = (temp2 >> 8) & 0xFF;

count_bit[16] = (temp2 >> 16) & 0xFF;
count_bit[17] = (temp2 >> 16) & 0xFF;
count_bit[18] = (temp2 >> 16) & 0xFF;
count_bit[19] = (temp2 >> 16) & 0xFF;
count_bit[20] = (temp2 >> 16) & 0xFF;
count_bit[21] = (temp2 >> 16) & 0xFF;
count_bit[22] = (temp2 >> 16) & 0xFF;
count_bit[23] = (temp2 >> 16) & 0xFF;

count_bit[24] = (temp2 >> 24) & 0xFF;
count_bit[25] = (temp2 >> 24) & 0xFF;
count_bit[26] = (temp2 >> 24) & 0xFF;
count_bit[27] = (temp2 >> 24) & 0xFF;
count_bit[28] = (temp2 >> 24) & 0xFF;
count_bit[29] = (temp2 >> 24) & 0xFF;
count_bit[30] = (temp2 >> 24) & 0xFF;
count_bit[31] = (temp2 >> 24) & 0xFF;

[Stenmark]

Icecap:
Jag har haft dem tankarna med, att lösa det med AND operationer. Det fungerar som sagt med 2 variabler. Men jag har inte lyckats få det att fungera med fler tal.
Jag hade en "divide and conquer" lösning på gång som ungefär gick ut på att man ANDar ihop två tal och tar reda på om det var en strikt majoritet som blev resultatet, dvs båda talen var samma. Sen skickar man det vidare och slår ihop resultatet från två sådana röstningar osv. Blir en form av trädstrukturslösning.

Kod: Markera allt

tal1
     -----|
tal2      |    resultat från övre
           |----resulttat från unre ---> osv
tal3      |
     -----|
tal4

problemet är att jag antog att om man slår ihop två resultat där man har två olika majoriteter från den undre nivån så tar jag och ANDar ihop resultet och får rätt svar, vilket inte stämmer. Svårt att förklara, men jag kunde inte komma på ett ihoslagnings steg som fungerar i alla fall. Men det är mycket möjligt att det finns ett sätt att lösa problemet på detta sätt.

Exile:
Jag har lite svårt att direkt se hur din kod fungerar. Jag får återkomma imorrn när jag tänkt lite. Men när jag sa 32 gånger snabbare så var det på ett ungefär. Har man läst algoritm kurser så blir man lite skadad och tycker att alla berökningar som är konstanta inte räknas om man har tex. en for loop som görs många gånger.

EDIT:
här är en metod som jag har tittat på, det löser inte exakt mitt problem men det kanske går att modifiera så att det fungerar. Här används sekvensnät och karnaaugh diagram för att uttnytjja enbart booleansk logik.
http://www.dattalo.com/technical/softwa ... rtcnt.html