Informatiker Board | Druckvorschau: b!tsh!fting

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Softwaretechnik (http://www.informatikerboard.de/board/board.php?boardid=18)
----- b!tsh!fting (http://www.informatikerboard.de/board/thread.php?threadid=1849)

Geschrieben von 0664jester am 25.04.2014 um 15:32:

b!tsh!fting

Ich schreibe an einem programm wo man nur +, - oder shift verwenden darf, da ich es dann auf Transistoren, etc ummünze.
Das Thema ist die Modulo Rechnung: a*b mod c, z. b: 4*4 mod 2 = 0

Hier zuerst wie weit ich bin. Dabei habe ich ein paar unwichtige Codefragment ausgelassen.

code:
1: 2: 3:

Es gibt nun mehrere Varianten, wie man shiftetet
1. Variante:
Man schiebt zu Beginn den Modul msolange nach links, bis das zweite Bit von links (im 16‐Bit‐Register) den Wert 1 kriegt. Der Automat merkt sich dabei die Anzahl der Schiebeoperationen (= j) für später.
Wenn dann nach der Multiplikation die Modulo‐Berechnung beginnt, kann man mit dem vorher
„geeignet“ nach links verschobenen Wert beginnen. Man subtrahiert also m*2^j
und sieht nach, obdas Ergebnis negativ wurde.
Wenn ja, dann ignoriert man dieses Ergebnis, schiebt m um eine Stelle
nach rechts und versucht es mit m*2^j‐1. Sobald das Ergebnis der Subtraktion positiv ist, merkt man
sich dieses Zwischenergebnis als neuen Wert. Dies macht man solange, bis man endlich das Ergebnis
hat.
--> Da fällt mir die Idee, wie ich erkennen kann das 2 bit von links.Kann mir da jemand auf die Sprüne helfen?

2. Variante:
Man schiebe m solange bis das verschobene Modul m größer ist bis das vorher berechnete Produkt.
--> ebenfalls noch keine Idee

Ziel ist es so schnell wie möglich die modulo rechnung durchzuführen ohne zu viele subtraktionen zu machen. Bei höheren Zahlen, würde das Programm dadurch langsam sein, wie z.b: bei (5*300) und dann 2 abziehen bis es nicht mehr geht.

Geschrieben von eulerscheZahl am 25.04.2014 um 18:56:

Zitat:

wie ich erkennen kann das 2 bit von links.

zahl & (1 << (sizeof(zahl) * 8 - 2))
zahl ist dein Bitmuster
das wird verundet mit 01000000 00000000 (für dein Beispiel mit 16 Bit), das heißt dieses eine Bit in zahl wird beibehalten, der Rest auf 0 gesetzt.
Dann musst du nur noch abfragen, ob das Ergebnis >0 ist.

Wenn du aber a*b mod c möglichst effizient berechnen willst, würde ich so vorgeben:
a*b (aber nicht mit Schleife über b, sondern wie beim schriftlichen Multiplizieren)
etwa (ungetestet)

code:

1:
2:
3:
4:
5:
6:
7:

int produkt = 0, tmp;
for(int i = 8*sizeof(b) - 1; i >= 0; i--){
    tmp = ((b & (1<<i))>>i); //ist das i. Bit gesetzt?
    if (tmp)
        tmp = a; //wenn Bit gesetzt, dann staht in tmp ein a (sonst 0)
    produkt += tmp << i; (verschieben um Position anzupassen, aufaddieren)
}

Auf ähnliche Weise kannst du dann das Produkt durch c dividieren (Ganzzahldivision, ohne Rest).

p mod c = p - p/c * c

edit: wenn deine Zahlen nicht so groß werden, dass du bei a*b einen Overflow kriegst, habe ich ein paar Zeilen zusammengetippt:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:

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

unsigned mult(unsigned a, unsigned b)
{
	unsigned prod = 0, tmp, i;
	for(i = 0; i < (sizeof(i) << 3); i++)
	{
		tmp = (b & (1<<i)) >> i; //ist das i. Bit gesetzt?
		if (tmp)
			tmp = a; //wenn Bit gesetzt, dann staht in tmp ein a (sonst 0)
		prod += tmp << i; //verschieben um Position anzupassen, aufaddieren
	}
	return prod;
}

unsigned divide(unsigned a, unsigned b)
{
	int shift = 0;
	unsigned quot = 0;
	while(a >= (b << shift))
		shift++;
	shift--;
	while(shift > 0 || a >= b)
	{
		a -= b << shift;
		quot |= 1 << shift;
		while(a < (b << shift) && shift > 0)
			shift--;
	}
	return quot;
}

unsigned mod(unsigned a, unsigned b, unsigned c)
{
	unsigned prod = mult(a, b);
	return prod - mult(divide(prod, c), c);
}

int main()
{
	int tests = (int)1e6, i;
	unsigned a, b, c;
	for(i = 0; i < tests; i++)
	{
		a = rand() % (1<<16);
		b = rand() % (1<<16);
		do {c = rand() % (1<<16);} while(c==0);
		if (mod(a,b,c) != (a*b)%c)
			printf("Fehler: a=%u, b=%u, c=%u\n", a, b, c);
	}
	/* OVERFLOW
	Fehler: a=59880, b=52711, c=17293
	Fehler: a=62753, b=48445, c=36316
	Fehler: a=63713, b=44540, c=9063
	Fehler: a=57002, b=49978, c=34299
	Fehler: a=59897, b=44892, c=9915
	Fehler: a=50532, b=64965, c=11028
	Fehler: a=44661, b=62053, c=10352
	Fehler: a=54538, b=55288, c=22685
	Fehler: a=48661, b=51969, c=1091
	*/
}

Geschrieben von 0664jester am 26.04.2014 um 12:54:

was macht diese zeile?

code:
1:	int tests = (int)1e6, i;

ich bin mir nicht so sicher, ob ich sizeof() verwenden darf.

da ich es dann in logisim umschreiben werde!

Geschrieben von eulerscheZahl am 26.04.2014 um 13:55:

Ich erzeuge 1 Million Zufallszahlenpaare und vergleiche das Ergebnis von % oder der von mir geschriebenen Methode, um etwaige Fehler zu entdecken.

sizeof() brauchst du nicht, wenn du weißt, wie viele Byte dein Datentyp groß ist.
Bin mir hat ein int 4 Byte, auf einen Microcontroller können es aber auch 2 Byte sein, musst du eben auf die vorhandene Hardware anpassen.

Geschrieben von 0664jester am 26.04.2014 um 16:15:

kann das sein, dass in der funktion divide sich vllt ein fehler eingeschlichen hat?
da wird return quot zurückgegeben aber nie damit gearbeitet oder täusche ich mich?

Geschrieben von eulerscheZahl am 26.04.2014 um 16:58:

In der while-Schleife
quot |= 1 << shift;
wenn dir das oder nicht gefällt, kannst du auch ein + nehmen, kommt auf das selbe raus

Geschrieben von 0664jester am 27.04.2014 um 07:25:

Kennt jemand eine möglichkeit, wie man eine potenzrechnung nur mit +, - oder shift ausführt?

z.B.: 2^3
Ich würde es für die Modularrechnung benötigen.
Wenn ich als summe 16 rausbekomme, funktioniert es zwar wunderbar, aber nicht nicht bei 19, 20 ...31. ab 32 wieder da ja 2 << 4 == 32

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:

int main()
{
  int konst = 000000001;
  int a = 4;
  int b = 4;
  int mod = 2;
  int i = 0;
  int sum = 0;

  if( mod == 0)
  {
  	printf("Modular must be bigger than 0!\n");
  }
  else
  {
  	//addieren
	  while(i < b) 
	  {
			sum = sum + a;
			i++;
	  }
		//Bitshifting
		//e.g. 8bit 0000 0001
		sum = 32; //soll sum in der zwischenzweit ersetzen
		int zahl1 = 0;
		int zahl2;
		int shift = 7;
		
return 0;
}

Geschrieben von eulerscheZahl am 27.04.2014 um 08:40:

Mal ein Beispiel:
$[latex]23^{18}[/latex]$
binär ist der Exponent 10010
Das Ergebnis ist zunächst 1
Bei jeder Ziffer in der Binärdarstellung quadrierst du das Ergebnis. Ist die Ziffer eine 1, wird das Ergebnis anschließend mit der Basis multipliziert.
Ergebnis = 1
Ergebnis = Ergebnis * Ergebnis * Basis = 1 * 1 * 23 = 23 (bei 10010)
Ergebnis = Ergebnis * Ergebnis = 23 * 23 = 529 (bei 10010)
Ergebnis = Ergebnis * Ergebnis= Ergebnis * Ergebnis = 529 * 529 = 279841 (bei 10010)
Ergebnis= Ergebnis * Ergebnis * Basis = 279841 * 279841 * 23 = 1801152661463 (bei 10010)
Ergebnis= Ergebnis * Ergebnis = 1801152661463 * 1801152661463 = 3244150909895248285300369 (bei 10010)
wenn du a^b mod c berechnen willst, solltest du nach jedem Einzelschritt die modulo-Rechnung durchführen, um die Zahlen klein zu halten.

Das lässt sich also mit recht wenigen Multiplikationen erreichen (dieser Weg über die Binärdarstellung ist nicht immer das Optimum, aber schon recht gut und einen schnelleren Weg zu finden kostet auch Rechenzeit)
Wie du die Multiplikation effizient schaffst, habe ich dir schon beschrieben, auch wenn du es noch nicht umgesetzt hast.

code:
1: 2: 3: 4: 5:	while(i < b) { sum = sum + a; i++; }

ist für ein kleines b schnell, wenn du aber mit großen Zahlen rechnen willst, rate ich davon ab.

Geschrieben von 0664jester am 27.04.2014 um 09:02:

ich möchte nicht a^b berechnen, sondern in meinem programm merkt er sich die anzahl der shifts.

c^anzahl shifts, die ich dann der summe abzähle, damit ich auf den rest komme.

die multiplikation für die summe werde ich noch ausbessern. im moment ist mir nur wichtig, dass ich überhaupt ein summe habe. das programm, was du da auf die schnelle geschrieben hast, läuft super! Daumen hoch

jedoch verstehe ich noch nicht alles was du da gemacht hast.

Geschrieben von eulerscheZahl am 27.04.2014 um 09:44:

Ok.
Ich habe verstanden, was du vorhast (deine Variante 1 im 1. Beitrag, die Encodingfehler hatten mich erst ein wenig vom Lesen abgeschreckt).
In deinem Programm finde ich dazu aber nicht mehr viele Parallelen.

So sieht dein Algorithmus in C aus, mit den Werten, die ich getestet habe, funktioniert er auch:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:

unsigned mod2(unsigned x, unsigned m)
{
	int shift = 0;
	while(m << shift < x)
		shift++;
	for(; shift >= 0; shift--)
		if(x >= m<<shift)
			x -= m<<shift;
	return x;
}

int main()
{
	unsigned m, x;
	while(1)
	{
		printf("x mod m\n  x eingeben: ");
		scanf("%u", &x);
		printf("  m eingeben: ");
		scanf("%u", &m);
		printf("%u mod %u = %u\n\n", x, m, mod2(x, m));
	}
}