| Die letzten 10 Beiträge |
| 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) |
| 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));
}
} |
|
|
| 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! 
jedoch verstehe ich noch nicht alles was du da gemacht hast. |
| eulerscheZahl |
Mal ein Beispiel:
![[latex]23^{18}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?23^{18})
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. |
| 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;
} |
|
|
| 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 |
| 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? |
| 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. |
| 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! |
| 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
*/
} |
|
|
| Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen. |
|
|
