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
Hm, interessantes Problemchen. Ist es eigentlich das Produkt zweier Primzahlen ? Sonst ist die Zerlegung ja nicht eindeutig ! ZigZeg
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.
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
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.
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 | }
|
puuu könntest du deinen code bissle kommentieren ^^ bzw. erklären was deine rangehensweise ist.... aber 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 | }
|
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
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?
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... :)
Du wirst immer EXAKTE Faktoren bekommen, nur halt keine eindeutigen, ... Mit Quicksort hat das nichts zu tun
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....
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
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.
@Иван 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
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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.