Forum: PC-Programmierung schnelle Iteration (C/C++) auf STM32


von Andi (Gast)


Lesenswert?

Hallo,

habe folgendes Problem bzw. Herausforderung *g*:

Ich habe ein Produkt zweier Zahlen gegeben im Wertebereich 0 bis 
268'365'825.

Nun muss ich die Faktoren dieses Produktes bestimmen. Dabei muss 
beachtet werden das Faktor 1 sich im Wertebereich von 0 bis 4095 (0xFFF) 
und Faktor 2 von 0 bis 65535 (0xFFFF) beläuft.

Bisher teile ich das Produkt solange bis es kleiner 65535 ist. Dann ist 
mein Nenner Faktor 1 und das geteilte Ergebnis Faktor 2.

Wenn das Produkt sehr groß ist kann das sehr lange dauern (9 ms). Nun 
gibt es sicherlich bessere Möglichkeiten diese Iteration durchzuführen 
und wollte daher mal nachfragen wie das funktioniert bzw. wie man sowas 
angeht?!?!

Vielen Dank für eure Hilfe
Gruß
Andi

von Kai S. (zigzeg)


Lesenswert?

Hm, interessantes Problemchen.

Ist es eigentlich das Produkt zweier Primzahlen ? Sonst ist die 
Zerlegung ja nicht eindeutig !

ZigZeg

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Für so kleine Zahlen ist Probedivision das Mittel der Wahl, bevorzugt 
mit einer Tabelle aller Primzahlen kleiner als Wurzel(268365825). 
Ausgefeilte Verfahren (Pollard's Rho, Elliptische Kurven, Quadratisches 
Sieb, etc) lohnen hier nicht.

Wie werden die Divisionen ausgeführt? In Hardware? Welche Arithmetik 
wird verwendet?

Es kann günstig sein, erst mal den ggT mit dem Produkt kleiner 
Primzahlen zu bilden, also z.B.

Ob das sinnvoll ist bzw. überhaupt machbar hängt von der 
zugrundeliegenden Arithmetik ab.

Alles in allem sind 9ms doch fix.

von Andi (Gast)


Lesenswert?

Nein sind keine primzahlen.... einfach ganze zahlen...
und 9ms sind nicht fix!- habe durch 2 weitere if verzweigungen die Zeit 
auf 6ms verbessert indem ich einfach ab einem bestimmten wert denn 
Nenner schon auf 1000 setze.... spare also 999 durchlaufe ein....

ich denke an ein ähnliches verfahren wie der quick sort Algorithmus....

Gruß
Andi

von Иван S. (ivan)


Lesenswert?

Aus dem Blauen geraten: Ich würde das Produkt einfach durch 65535 
teilen, damit hätte ich zumindest schon 'mal eine Grössenordnung für das 
Maximum von Faktor 2.

von Volker Z. (vza)


Lesenswert?

Dein Problem läst sich nicht lösen.
1
long prim[]={0,
2
    2,     3,     5,     7,    11,    13,    17,    19,    23,    29,    31,    37,    41,    43,
3
   47,    53,    59,    61,    67,    71,    73,    79,    83,    89,    97,   101,   103,   107,
4
  109,   113,   127,   131,   137,   139,   149,   151,   157,   163,   167,   173,   179,   181,
5
  191,   193,   197,   199,   211,   223,   227,   229,   233,   239,   241,   251,   257,   263,
6
  269,   271,   277,   281,   283,   293,   307,   311,   313,   317,   331,   337,   347,   349,
7
  353,   359,   367,   373,   379,   383,   389,   397,   401,   409,   419,   421,   431,   433,
8
  439,   443,   449,   457,   461,   463,   467,   479,   487,   491,   499,   503,   509,   521,
9
  523,   541,   547,   557,   563,   569,   571,   577,   587,   593,   599,   601,   607,   613,
10
  617,   619,   631,   641,   643,   647,   653,   659,   661,   673,   677,   683,   691,   701,
11
  709,   719,   727,   733,   739,   743,   751,   757,   761,   769,   773,   787,   797,   809,
12
  811,   821,   823,   827,   829,   839,   853,   857,   859,   863,   877,   881,   883,   887,
13
  907,   911,   919,   929,   937,   941,   947,   953,   967,   971,   977,   983,   991,   997,
14
 1009,  1013,  1019,  1021,  1031,  1033,  1039,  1049,  1051,  1061,  1063,  1069,  1087,  1091,
15
 1093,  1097,  1103,  1109,  1117,  1123,  1129,  1151,  1153,  1163,  1171,  1181,  1187,  1193,
16
 1201,  1213,  1217,  1223,  1229,  1231,  1237,  1249,  1259,  1277,  1279,  1283,  1289,  1291,
17
 1297,  1301,  1303,  1307,  1319,  1321,  1327,  1361,  1367,  1373,  1381,  1399,  1409,  1423,
18
 1427,  1429,  1433,  1439,  1447,  1451,  1453,  1459,  1471,  1481,  1483,  1487,  1489,  1493,
19
 1499,  1511,  1523,  1531,  1543,  1549,  1553,  1559,  1567,  1571,  1579,  1583,  1597,  1601,
20
 1607,  1609,  1613,  1619,  1621,  1627,  1637,  1657,  1663,  1667,  1669,  1693,  1697,  1699,
21
 1709,  1721,  1723,  1733,  1741,  1747,  1753,  1759,  1777,  1783,  1787,  1789,  1801,  1811,
22
 1823,  1831,  1847,  1861,  1867,  1871,  1873,  1877,  1879,  1889,  1901,  1907,  1913,  1931,
23
 1933,  1949,  1951,  1973,  1979,  1987,  1993,  1997,  1999,  2003,  2011,  2017,  2027,  2029,
24
 2039,  2053,  2063,  2069,  2081,  2083,  2087,  2089,  2099,  2111,  2113,  2129,  2131,  2137,
25
 2141,  2143,  2153,  2161,  2179,  2203,  2207,  2213,  2221,  2237,  2239,  2243,  2251,  2267,
26
 2269,  2273,  2281,  2287,  2293,  2297,  2309,  2311,  2333,  2339,  2341,  2347,  2351,  2357,
27
 2371,  2377,  2381,  2383,  2389,  2393,  2399,  2411,  2417,  2423,  2437,  2441,  2447,  2459,
28
 2467,  2473,  2477,  2503,  2521,  2531,  2539,  2543,  2549,  2551,  2557,  2579,  2591,  2593,
29
 2609,  2617,  2621,  2633,  2647,  2657,  2659,  2663,  2671,  2677,  2683,  2687,  2689,  2693,
30
 2699,  2707,  2711,  2713,  2719,  2729,  2731,  2741,  2749,  2753,  2767,  2777,  2789,  2791,
31
 2797,  2801,  2803,  2819,  2833,  2837,  2843,  2851,  2857,  2861,  2879,  2887,  2897,  2903,
32
 2909,  2917,  2927,  2939,  2953,  2957,  2963,  2969,  2971,  2999,  3001,  3011,  3019,  3023,
33
 3037,  3041,  3049,  3061,  3067,  3079,  3083,  3089,  3109,  3119,  3121,  3137,  3163,  3167,
34
 3169,  3181,  3187,  3191,  3203,  3209,  3217,  3221,  3229,  3251,  3253,  3257,  3259,  3271,
35
 3299,  3301,  3307,  3313,  3319,  3323,  3329,  3331,  3343,  3347,  3359,  3361,  3371,  3373,
36
 3389,  3391,  3407,  3413,  3433,  3449,  3457,  3461,  3463,  3467,  3469,  3491,  3499,  3511,
37
 3517,  3527,  3529,  3533,  3539,  3541,  3547,  3557,  3559,  3571,  3581,  3583,  3593,  3607,
38
 3613,  3617,  3623,  3631,  3637,  3643,  3659,  3671,  3673,  3677,  3691,  3697,  3701,  3709,
39
 3719,  3727,  3733,  3739,  3761,  3767,  3769,  3779,  3793,  3797,  3803,  3821,  3823,  3833,
40
 3847,  3851,  3853,  3863,  3877,  3881,  3889,  3907,  3911,  3917,  3919,  3923,  3929,  3931,
41
 3943,  3947,  3967,  3989,  4001,  4003,  4007,  4013,  4019,  4021,  4027,  4049,  4051,  4057,
42
 4073,  4079,  4091,  4093};
43
44
void teile(long fak2)
45
{
46
   long fak1=1;
47
   long *pP = prim + sizeof(prim)/sizeof(long)-1;
48
//   printf("->%ld = ",*pP);
49
   printf("Zahl=%07lX = ",fak2);
50
   while(fak2>0xFFFFuL && *pP!=0)
51
   {
52
      while(0==(fak2%*pP))
53
      {
54
         fak2 /= *pP;
55
         fak1 *= *pP;
56
//printf("(%ld)",*pP);
57
      }
58
      pP--;
59
   }
60
   printf("f1=%04lX * f2=%05lX   (%ld)\n",fak1,fak2,*pP);
61
}
62
63
int main(int argc, char* argv[])
64
{
65
   teile( 268365825);
66
   teile(0x00123abc);
67
   teile(0x0FE23abc);
68
69
   printf("\nHit any key to exit.\n");
70
   getchar();
71
   return 0;
72
}

von Andi (Gast)


Lesenswert?

puuu könntest du deinen code bissle kommentieren ^^ bzw. erklären was 
deine rangehensweise ist.... aber danke :-)

von Kai S. (zigzeg)


Lesenswert?

Volker Zabe schrieb:
> Dein Problem läst sich nicht lösen.

> ... C-Programm ...

Verstehe den Zusammenhang nicht. Muss ich das C-Programm erst laufen 
lassen, um das zu verstehen ?

Wenn es sich nicht um das Produkt von Primzahlen handelt, so ist das 
Problem nicht EINDEUTIG loesbar. Es gibt also mehrere moegliche 
Zerlegungen.

Eine Moeglichkeit waere es, alle Primfaktoren des Produktes zu 
bestimmen. Dann kann man die Primfaktoren (fast) beliebig in zwei Mengen 
aufteilen, wobei sich durch multiplizieren jeweils die beiden Faktoren 
ergeben. Die einzige Randbedingung ist, dass der eine Faktor kleiner als 
4096 ist.

Geht es nur darum, die Berechnung "ein bischen" schneller zu machen, 
hier ein paar Ideen:
- Es ist
 als ist
, also
, also
. Man kann also ausrechnen, wie gross f2 mindestens sein muss (p/4096), 
und die Schleife erst von da ab laufen lassen.

- Vielfache von 2 kann man sehr leicht erkennen, und vorab aus dem 
Produkt entfernen:
1
f2 = 1;
2
while((p & 1) == 0) // Wenn p gerade ist
3
{
4
    p /= 2;
5
    f2 *= 2;
6
}

von Andi (Gast)


Lesenswert?

ok irgendiwe verliere ich hier langsam bissle den überblick ^^ ich 
verstehe nicht ganz was das immer mit den primzahlen zu tun hat g das 
es mehrere möglichkeiten gibt und dass das ergebnis nicht eindeutig 
lösbar ist ist ja wohl klar, deswegen brauch ich dieses iterative 
verfahren :)

ich suche jedeglich eine schnelle möglichkeit EINE lösung unter den 
randbedingungen zu finden...

bisher teile ich das produkt einfach durch einen nenner solange bis es 
kleiner 65536 ist... und zack hab ich die 2 faktoren (1.Faktor: Nenner, 
2. Faktor: das geteilte ergebnis)
wenn das produkt aber groß ist durchläuft er die schleife sehr oft (x/2, 
x/3, x/4, x/5, x/6,.... x/3000,....bis maximal x/4096)...

hab da wahrscheinlich eure antworten nicht richtig verstanden...

Danke
Andi

von Volker Z. (vza)


Lesenswert?

Ganz einfache Erklärung:
Alle Primzahlen zwischen 65536 und 268365825 lassen sich nicht 
aufteilen.
Und davon giebt es eine ganze Menge.

Oder geht es nur darum heraus zu finden, ob sie sich nach Deinen 
Bedingungen aufteilen lassen?

von Andi (Gast)


Lesenswert?

aso ja stimmt :) daran hab ich gar net gedacht... nein ich brauche 2 
faktoren, wenn diese nicht exakt bestimmbar sind dann halt eine 
näherung....

diese 2 faktoren werden nachher einem timer zugeführt und bestimmen die 
zeitbasis... wenn diese nicht 100% passt ist das auch net so wild... :)

von D. I. (Gast)


Lesenswert?

Du wirst immer EXAKTE Faktoren bekommen, nur halt keine eindeutigen, ...

Mit Quicksort hat das nichts zu tun

von Andi (Gast)


Lesenswert?

ja mit quicksort hatte ich nur im kopf das ich den nenner nicht bei 2 
loslaufen lass sondern in der mitte (2048) und dann wieder mitte und 
wieder mitte und so.... damit habe ich den worstcase nichtmehr das mir 
die schleife 4095 mal durchläuft....

also irgendwie sowas hab ich im kopf....

von Kai S. (zigzeg)


Lesenswert?

Andi schrieb:
> aso ja stimmt :) daran hab ich gar net gedacht... nein ich brauche 2
> faktoren, wenn diese nicht exakt bestimmbar sind dann halt eine
> näherung....

Naeherung reicht, na sag das doch gleich :-)

> diese 2 faktoren werden nachher einem timer zugeführt und bestimmen die
> zeitbasis... wenn diese nicht 100% passt ist das auch net so wild... :)

Eigentlich braucht man dann gar keine Schleife:
Nimm einfach die dritte Wurzel der Ausgangszahl. Das ergibt dann den 
einen Faktor (da immer kleiner als 4096). Den anderen Faktor kannst Du 
dann durch Division ausrechnen:
1
#include <math.h>
2
3
...
4
int p, f1, f2;
5
6
f1 = pow(p, 1.0/3.0); // dritte Wurzel ist dasselbe wie x^(1/3)
7
f2 = p / f1;
8
...
Habe ich jetzt nicht getestet, sollte aber so ungefaehr funktionieren.
Evtl. f2 noch etwas runden, z.B. so:
1
f2 = (p + f1/2) / f1;

ZigZeg

von Иван S. (ivan)


Lesenswert?

Kai S. schrieb:
> Nimm einfach die dritte Wurzel der Ausgangszahl. Das ergibt dann den
> einen Faktor (da immer kleiner als 4096). Den anderen Faktor kannst Du
> dann durch Division ausrechnen.

Am schnellsten ginge es, wenn man das Produkt einfach durch 65535 
dividieren würde. Ergibt ebenfalls den kleinen Faktor.

von Andi (Gast)


Lesenswert?

@Иван S.

mhh stimmt geht aber nur wenn das produkt größer 65536 ist aber das kann 
man ja leicht abfangen :) werds mal so probieren... die primitivsten 
lösungen sind meistens die besten :)

gruß
andi

von Kai S. (zigzeg)


Lesenswert?

In der Tat, man sollte alles nur so komplex machen wie notwendig.
Was die beste Loesung ist haengt halt stark davon ab, wie genau der 
Timer laufen soll.

ZigZeg

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.