schnelle Iteration (C/C++) auf STM32

Andi Gast #2061323
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
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Johann L. Persönliche Seite #2061724
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Andi Gast #2061918
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Volker Z. #2061968
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
}
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Kai S. #2062073
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
}
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Andi Gast #2062093
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Andi Gast #2062105
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... :)
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Andi Gast #2062127
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....
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Kai S. #2062131
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Andi Gast #2062317
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren