b!tsh!fting

Neue Frage »

Auf diesen Beitrag antworten »
0664jester 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.
 
Auf diesen Beitrag antworten »
eulerscheZahl

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
	*/
}
Auf diesen Beitrag antworten »
0664jester

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!
Auf diesen Beitrag antworten »
eulerscheZahl

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.
 
Auf diesen Beitrag antworten »
0664jester

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?
Auf diesen Beitrag antworten »
eulerscheZahl

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

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;
}
Auf diesen Beitrag antworten »
eulerscheZahl

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.
Auf diesen Beitrag antworten »
0664jester

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.
Auf diesen Beitrag antworten »
eulerscheZahl

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));
	}
}
Auf diesen Beitrag antworten »
0664jester

Hallo,

Ich habe leider eine overflow bemerkt:
php:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
while(shift >= 0) 
{                  
//    printf("shift: %d\n", shift);             
if(sum >= mod<<shift)             
{             
//    printf("sum: %d\n", sum);                 
sum-= mod<<shift;             
//    printf("sum: %d\n", sum);             
}         
shift--;         
}


wie kann ich es mit unsigned lösen?

ich habe schon probiert mit
while(shift !=0)
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »