Vorschläge für "normale" Zahlenverteilungen für Programmierwettbewerbe

[SideWinder]

;fricky schrieb:

volkard schrieb:

Können Java und Haskell eigetlich mit 64-Bit-Zahlen natürlich umgehen?

Java's longs sind 64 bit signed. ausserdem hat Java noch 'ne 'BigInteger' klasse mit dabei.

Wobei BigInteger eine Krücke ist und keinesfalls mit anderen Mathematik-Bibliotheken mithalten kann.

MfG SideWinder

[;fricky]

SideWinder schrieb:

Wobei BigInteger eine Krücke ist und keinesfalls mit anderen Mathematik-Bibliotheken mithalten kann.

das ist klar, geschwindigkeitsmässig kann's mit reinen C-implementationen wie GMP und 'bignum' leider nicht mithalten. primzahlenforscher werden mit 'BigInteger' wohl nicht glücklich werden.

[volkard]

;fricky schrieb:

volkard schrieb:

Können Java und Haskell eigetlich mit 64-Bit-Zahlen natürlich umgehen?

Java's longs sind 64 bit signed. ausserdem hat Java noch 'ne 'BigInteger' klasse mit dabei.

Ok, also müßte ich auf 63 Bit runter, um bei sowas Java zuzulassen.

[;fricky]

volkard schrieb:

Ok, also müßte ich auf 63 Bit runter, um bei sowas Java zuzulassen.

und leute mit alten 32-bit CPUs haben auch pech - *fg*

[knivil]

das hier ist schneller: http://www.alpertron.com.ar/ECM.HTM
gib z.b. mal 35742549198872617291353508656626642567 ein.
^^38 stellen, mehr als 2^64, unter einer sekunde.

Wie kommst du darauf? Wie hast du die Performance gemessen. Welche Hardware ist hinter der Seite ... Naja, EMC soll etwa genauso gut wie das Quadratische Sieb sein.

Beispiel msieve:

Mon Nov  9 13:31:01 2009  Msieve v. 1.43
Mon Nov  9 13:31:01 2009  random seeds: 324bc4df a040795f
Mon Nov  9 13:31:01 2009  factoring 1427247692705959881058285969449495136382746619 (46 digits)
Mon Nov  9 13:31:01 2009  prp46 factor: 1427247692705959881058285969449495136382746619
Mon Nov  9 13:31:01 2009  elapsed time 00:00:00

Also bei 0sec kann man noch nicht wirklich vergleichen.

Haskell eigetlich mit 64-Bit-Zahlen natürlich umgehen?

Fuer grosse Zahlen nutzt GHC die gmp-Library.

[;fricky]

knivil schrieb:

das hier ist schneller: http://www.alpertron.com.ar/ECM.HTM
gib z.b. mal 35742549198872617291353508656626642567 ein.
^^38 stellen, mehr als 2^64, unter einer sekunde.

Wie kommst du darauf? Wie hast du die Performance gemessen. Welche Hardware ist hinter der Seite ...

die zeit wird vom applet angezeigt. benutzt wird die hardware des rechners, der das applet ausführt.

[;fricky]

knivil schrieb:

Beispiel msieve:

Mon Nov  9 13:31:01 2009  Msieve v. 1.43
Mon Nov  9 13:31:01 2009  random seeds: 324bc4df a040795f
Mon Nov  9 13:31:01 2009  factoring 1427247692705959881058285969449495136382746619 (46 digits)
Mon Nov  9 13:31:01 2009  prp46 factor: 1427247692705959881058285969449495136382746619
Mon Nov  9 13:31:01 2009  elapsed time 00:00:00

Also bei 0sec kann man noch nicht wirklich vergleichen.

1427 247692 705959 881058 285969 449495 136382 746619 is prime 
Number of divisors:  2 
Sum of divisors:  1427 247692 705959 881058 285969 449495 136382 746620 
Euler's Totient:  1427 247692 705959 881058 285969 449495 136382 746618 
Moebius: -1
Sum of squares: a^2 + b^2 + c^2
a = 24081 754504 544022 807725 
b = 24081 754504 544022 807725 
c = 16351 938498 896918 681037 

Factorization complete in 0d 0h 0m 0s
ECM: 0 modular multiplications
Prime checking: 54368 modular multiplications
Timings:
Primality test of 1 number: 0d 0h 0m 0.0s

^^ ECM, bei mir auf'm amd athlon 64X2 dual core 4200+

[;fricky]

probier die mit msieve: 1427247692705959881058285969449495136382746619999999999999999999999999999999
bei mir:

1427 247692 705959 881058 285969 449495 136382 746619 999999 999999 999999 
999999 999999 = 103 x 127 x 1109 x 15619 x 381 308903 315467 509491 x 16 
519491 963197 520721 201913 382173 765630 439539 

Number of divisors:  64 

Sum of divisors:  1453 854517 149882 966534 763020 072486 242721 275148 
262883 161682 617901 348339 712000 

Euler's Totient:  1400 907720 253819 065431 410116 909535 498666 542922 
057105 783401 190982 899647 250560 

Moebius: 1

Sum of squares: a^2 + b^2 + c^2 + d^2
a = 31 171293 432603 504229 379419 111307 565577 
b = 14 870915 147465 912772 903524 215279 510299 
c = 13 697859 058020 968099 894780 901863 934663 
d = 6 842711 330163 746856 478196 796552 648710 

[b]Factorization complete in 0d 0h 1m 27s[/b]
ECM: 6946913 modular multiplications
Prime checking: 58341 modular multiplications
SIQS: 60843 polynomials sieved
      51774 sets of trial divisions
      2723 smooth congruences found (1 out of every 1989161 values)
      28628 partial congruences found (1 out of every 189202 values)
      2811 useful partial congruences

Timings:
Primality test of 3 numbers: 0d 0h 0m 0.0s
Factoring 1 number [b]using ECM: 0d 0h 0m 8.5s[/b]
Factoring 1 number [b]using SIQS: 0d 0h 1m 18.7s[/b]

[rapso]

volkard schrieb:

Ein kleines "if(n<1000) return precomputed[n];" wird sich wohl stets einschleichen, aber egal, das macht jeder und dann isses wieder fair.

und welchen sinn macht dann die pruefung von zahlenbereichen die alle gleich vorberechnet haben?
am ende benachteiligst du die, die die eigentliche aufgabe loesen.

du solltest zahlenbereiche die mit 08/15 mitteln geloest werden koennen einfach explizit aus dem contest lassen.

ansonsten wird nicht die aufgabenstellung eine herausvorderung sein, sondern die adaption an deine zahlenskala.

[knivil]

@;fricky: du hast das applet nicht verstanden:

When the number to be factorized is in the range 31-90 digits, after computing some curves in order to find small factors, the program switches to SIQS

ECM wurde nur fuer kleine Faktoren genutzt. Schaltet man SIQR ab, so braucht ECM etwa 42sec und msieve etwa 55sec.

[;fricky]

knivil schrieb:

@;fricky: du hast das applet nicht verstanden:

schau dir mal den source-code an. den wirst auch du nicht verstehen. *fg*

...so braucht ECM etwa 42sec und msieve etwa 55sec.

heisst das etwa, ein popeliges Java-applett schlägt ein C-programm im 'number crunching'?
^^finde ich witzig, jetzt wird wohl keiner mehr behaupten, dass Java zu langsam ist.

[knivil]

;fricky schrieb:

heisst das etwa, ein popeliges Java-applett schlägt ein C-programm im 'number crunching'?
^^finde ich witzig, jetzt wird wohl keiner mehr behaupten, dass Java zu langsam ist.

Nein, es hat auch nichts mit Numbercrunching zu tun, da nur Relationen aufgebaut werden. msieve nutzt z.B. die GMP nicht, sondern etwas eigenes fuer grosse Zahlen. Dieser Code macht laut Doku etwa 10 % aus. Desweiteren schreibt msieve Zwischenergebnisse auf die Platte, damit diese bei anderen Anfragen wiederverwendet werden koennen. Auch ist der Speicherverbrauch wesentlich geringer. Ein korrekter Vergleich der Performance kann auch nur erfolgen, wenn der Algorithmus des Applets in C (oder C++) implementiert wird.

popeliges Java-applett

Dieses Applet unterscheidet sich wohl kaum gegenueber einer richtigen Javaanwendung.

[volkard]

rapso schrieb:

und welchen sinn macht dann die pruefung von zahlenbereichen die alle gleich vorberechnet haben?
am ende benachteiligst du die, die die eigentliche aufgabe loesen.

du solltest zahlenbereiche die mit 08/15 mitteln geloest werden koennen einfach explizit aus dem contest lassen.

ansonsten wird nicht die aufgabenstellung eine herausvorderung sein, sondern die adaption an deine zahlenskala.

Deine Argumentation hat was vür sich. Wenn es gute Lösungen vür ein paar Zahlenbereiche gibt, kann die Anpassung an die in der Anwendung zu erwartende Zahlenverteilung auch ein Bot erledigen.

[FachmannFürV]

volkard schrieb:

...hat was vür sich. Wenn es gute Lösungen vür...

Du Provi?

[volkard]

FachmannFürV schrieb:

volkard schrieb:

...hat was vür sich. Wenn es gute Lösungen vür...

Du Provi?

Ich nur gerne Anpassung. Orthogonal zu Fachdiskussion.

[;fricky]

knivil schrieb:

...Desweiteren schreibt msieve Zwischenergebnisse auf die Platte, damit diese bei anderen Anfragen wiederverwendet werden koennen. Auch ist der Speicherverbrauch wesentlich geringer.

dieses applet greift ja auch auf vorberechnete ergebnisse zu. aber es ist einfach nur schlau gemacht und deshalb so schnell.

knivil schrieb:

Ein korrekter Vergleich der Performance kann auch nur erfolgen, wenn der Algorithmus des Applets in C (oder C++) implementiert wird.

und hätte man das applet in C programmiert, wär's bestimmt noch etwas schneller.
ach ja, er hat auch 'nen faktorisierer für monsterzahlen jenseits von gut und böse in C++ geschrieben (naja, eigentlich ist es assembler): http://www.alpertron.com.ar/GOOGOL.ZIP