b!tsh!fting |
0664jester
Jungspund
Dabei seit: 22.03.2014
Beiträge: 18
|
|
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.
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.
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von 0664jester: 28.04.2014 08:04.
|
|
25.04.2014 15:32 |
|
|
|
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
*/
} |
|
__________________ Syntax Highlighting fürs Board (Link)
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von eulerscheZahl: 25.04.2014 20:21.
|
|
25.04.2014 18:56 |
|
|
0664jester
Jungspund
Dabei seit: 22.03.2014
Beiträge: 18
|
|
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!
|
|
26.04.2014 12:54 |
|
|
|
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
26.04.2014 13:55 |
|
|
0664jester
Jungspund
Dabei seit: 22.03.2014
Beiträge: 18
|
|
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?
|
|
26.04.2014 16:15 |
|
|
|
Mal ein Beispiel:
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
27.04.2014 08:40 |
|
|
|
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));
}
} |
|
__________________ Syntax Highlighting fürs Board (Link)
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von eulerscheZahl: 27.04.2014 10:26.
|
|
27.04.2014 09:44 |
|
|
|