schnelle Iteration (C/C++) auf STM32

Gast #2061323 
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
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Melden Danke
Persönliche Seite 
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.
Antwort Zitieren Bearbeiten Löschen Melden Danke
Gast 
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
Antwort Zitieren Bearbeiten Löschen Melden Danke 
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
}
Antwort Zitieren Bearbeiten Löschen Melden Danke 
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
}
Antwort Zitieren Bearbeiten Löschen Melden Danke
Gast 
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
Antwort Zitieren Bearbeiten Löschen Melden Danke 
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?
Antwort Zitieren Bearbeiten Löschen Melden Danke
Gast 
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... :)
Antwort Zitieren Bearbeiten Löschen Melden Danke
Gast 
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....
Antwort Zitieren Bearbeiten Löschen Melden Danke 
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
Antwort Zitieren Bearbeiten Löschen Melden Danke 
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.
Antwort Zitieren Bearbeiten Löschen Melden Danke
Gast 
@Иван 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
Antwort Zitieren Bearbeiten Löschen Melden Danke
Thread beobachten

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 15 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Dein Name und deine E-Mail-Adresse

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.