mikrocontroller.net

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


Autor: Andi (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Kai S. (zigzeg)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hm, interessantes Problemchen.

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

ZigZeg

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Andi (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Иван S. (ivan)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Volker Zabe (vza)
Datum:

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

void teile(long fak2)
{
   long fak1=1;
   long *pP = prim + sizeof(prim)/sizeof(long)-1;
//   printf("->%ld = ",*pP);
   printf("Zahl=%07lX = ",fak2);
   while(fak2>0xFFFFuL && *pP!=0)
   {
      while(0==(fak2%*pP))
      {
         fak2 /= *pP;
         fak1 *= *pP;
//printf("(%ld)",*pP);
      }
      pP--;
   }
   printf("f1=%04lX * f2=%05lX   (%ld)\n",fak1,fak2,*pP);
}

int main(int argc, char* argv[])
{
   teile( 268365825);
   teile(0x00123abc);
   teile(0x0FE23abc);

   printf("\nHit any key to exit.\n");
   getchar();
   return 0;
}

Autor: Andi (Gast)
Datum:

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

Autor: Kai S. (zigzeg)
Datum:

Bewertung
0 lesenswert
nicht 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:
f2 = 1;
while((p & 1) == 0) // Wenn p gerade ist
{
    p /= 2;
    f2 *= 2;
}

Autor: Andi (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Volker Zabe (vza)
Datum:

Bewertung
0 lesenswert
nicht 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?

Autor: Andi (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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... :)

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du wirst immer EXAKTE Faktoren bekommen, nur halt keine eindeutigen, ...

Mit Quicksort hat das nichts zu tun

Autor: Andi (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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....

Autor: Kai S. (zigzeg)
Datum:

Bewertung
0 lesenswert
nicht 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:
#include <math.h>

...
int p, f1, f2;

f1 = pow(p, 1.0/3.0); // dritte Wurzel ist dasselbe wie x^(1/3)
f2 = p / f1;
...

Habe ich jetzt nicht getestet, sollte aber so ungefaehr funktionieren.
Evtl. f2 noch etwas runden, z.B. so:
f2 = (p + f1/2) / f1;

ZigZeg

Autor: Иван S. (ivan)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Andi (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Kai S. (zigzeg)
Datum:

Bewertung
0 lesenswert
nicht 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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.