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



  • Also ich könnte mir vorstellen dass durchaus ein paar der einfachsten Verteilungen oft Sinn machen.

    * gleichverteilt
    * normalverteilt
    * 1/n
    * 1/n², 1/n³, ...
    * 1/k^n



  • Wie wäre es, mit einer Reyleigh-Verteilung?

    http://en.wikipedia.org/wiki/Rayleigh_distribution

    Besonders der abschnitt 'Generating Rayleigh-distributed random variates'.



  • volkard schrieb:

    Ob nun magicnumer=1000 oder magicnumber=2000 macht keinen meßbaren Unterschied mehr wenn ich über alle möglichen Eingaben mittle. Wenn ich nur über [1;5000] mittle aber sehr wohl. Würde ich eine Verteilung wählen, die kleine Zahlen bevorzugt, wäre es vielleicht möglich, ohne genaues vorheriges Wissen der Problemstellung dafür sorgen zuz können, daß Leute, die die magicnumbers nicht nur raten, sondern ausmessen, auch messbar gewinnen.

    Was könnten denn sinnvolle Verteilungen für sowas sein und warum?

    Wenn du die Verteilung nicht in der Aufgabe bekannt gibst, dann kann man die magicnumber nur raten. Wenn du sie angibst, ist die genaue Verteilung egal. Sag halt einfach z.b. 100 x ( 0 - 1000 ); 100 x ( 1000 - 1000000 ); 100 x ( 1000000 - 1000000000 ) oder gib eine Liste mit n Zahlen vor. Wenn fuer alle gleiche Bedingungen herrschen gibt es keine Anspruch an die Guete der Verteilung ausser die von dir definierten. f'`8k

    Gruß, TGGC (Was Gamestar sagt...)



  • bool istPrimzahl(UInt32 n);
    

    Du wirfst also 10.000 Zufallszahlen in einem bestimmten Intervall auf diese Funktion. Nun nutze ich in meiner Funktion eine Variante des Siebes von Eratosthenes. Ein Test von n=12345 kann alle weiteren Funktionsaufrufe mit kleineren n beschleunigen, in dem ich mir einfach Zwischenergebnisse merke.

    Was ich damit sagen will: 10.000 mal die Funktion mit Zufallszahlen aufzurufen und die Zeit messen, ist nicht wirklich ein geeignetes Kriterium. Natuerlich kann man durch Regeln beim Wettbewerb ausschliessen, doch die sind manchmal recht einschraenkend und sollten gut ueberlegt sein. Beispiel: Zu starke Restriktionen haben eine gutes Programm fuer die Loesung des Problems der (begrenzeten) exakten Summe verhindert.



  • TGGC schrieb:

    Wenn du die Verteilung nicht in der Aufgabe bekannt gibst, dann kann man die magicnumber nur raten.

    Ich will die Verteilung angeben.

    TGGC schrieb:

    Wenn du sie angibst, ist die genaue Verteilung egal. Sag halt einfach z.b. 100 x ( 0 - 1000 ); 100 x ( 1000 - 1000000 ); 100 x ( 1000000 - 1000000000 )

    Ja, die ist nett. Die kann man auch nach Blue-Tiger stetig machen. x=untergrenze*pow(basis,zufall) oder sowas.

    TGGC schrieb:

    oder gib eine Liste mit n Zahlen vor.

    Dann kriege ich nur vorausberechnete Tabellen, fürchte ich.
    Stattdessen mag ich die erzeugende Funktion angeben und nur den ramdom-seed beim Messen austauschen.



  • Mehrere Bereiche machen und die dann zu einem vermischen, damit es keine Reihenfolge gibt.



  • knivil schrieb:

    bool istPrimzahl(UInt32 n);
    

    Du wirfst also 10.000 Zufallszahlen in einem bestimmten Intervall auf diese Funktion. Nun nutze ich in meiner Funktion eine Variante des Siebes von Eratosthenes. Ein Test von n=12345 kann alle weiteren Funktionsaufrufe mit kleineren n beschleunigen, in dem ich mir einfach Zwischenergebnisse merke.

    Ja, aber das sind ja eh nur Tricks bei kleinen Zahlen. Die Plätze 10 bis 15 mögen sich um sowas streiten. Die vorderen Plätze entscheiden sich im Bereich 2^63 bis 2^64, wo die kleinen schon lange raus sind. Das stelle ich mir so vor, daß ich unter Beibehaltung zum Beispiel der Exponentialverteilung zuerst nur 100-1000 werfe, dann 100-10000, dann 100-100000 und so fort und sukzessive die rauswerfe, die länger als 10 Minuten brauchen bis ich dann zu den elend schnellen komme, die bei 100-2^64 noch unter 10 min brauchen und die sollten normalerweise auch deutliche Unterschiede zeigen. Und in den Bereichen hilft kein caching. Irgendwelche Beschränkungen an den Speicher werde ich auch machen, zum Beispiel max 1G Plattenplatz nach und max 10min für "make learn", max 10M nach und mach 10min für "make build".

    knivil schrieb:

    Was ich damit sagen will: 10.000 mal die Funktion mit Zufallszahlen aufzurufen und die Zeit messen, ist nicht wirklich ein geeignetes Kriterium. Natuerlich kann man durch Regeln beim Wettbewerb ausschliessen, doch die sind manchmal recht einschraenkend und sollten gut ueberlegt sein. Beispiel: Zu starke Restriktionen haben eine gutes Programm fuer die Loesung des Problems der (begrenzeten) exakten Summe verhindert.

    Ja, ich habe mal bei einem Wettbewerb mitgemacht, der alle vorausberechneten Tabellen verboten hatte. Aber hey, die Primzahlen bis 30 für einen Vortest als Tabelle abzulegen ist eine *sehr* gute Idee für alle Größenordnungen. Sowas will ich gar nicht einschränken. Wenn nur die besten Tabellen gewinnen, war die Aufgabenstellung schlecht.

    Gegen caching während des Programmlaufs und Vorausberechnung kleiner Eingabewerte kann ich mich bei 10000 Eingabezahlen nicht generell schützen. Die Aufgabenstellungen müssen halt so sein, daß das nicht enorm viel bringt. Ein kleines "if(n<1000) return precomputed[n];" wird sich wohl stets einschleichen, aber egal, das macht jeder und dann isses wieder fair. Besonder coole Programmierer werden auf diese Kinderkacke normalerweise verzichten, außer natürlich, sie rechnen damit, daß der zweitplazierte für 2^63 bis 2^64 auf den Takt genau gleichschnell ist.

    Ok, ich könnte, wenn ich nur Funktionsaufrufe messen würde und den Code sichten würde, aber das will ich nicht. Ich will, daß alle Sprachen mitspielen können. Und ich will nicht sichten und bewerten müssen, ob was regelgerecht ist. Deswegen auch die Möglichkeit, ein makefile oder -script abzugeben, daß mit "make learn" erstmal checkt, wieviele Kerne da sind und ob DIV 20-mal so langsam wie MUL ist oder nur 10-mal.



  • a) Wo kann ich mich beim Wettbewerb anmelden? 🙂
    b) Du solltest einige gaengige Implementationen vorher mal besichtigen, z.B. msieve. Fuer Zahlen im Bereich von 2^64 braucht es nur wenige Sekunden.



  • knivil schrieb:

    z.B. msieve. Fuer Zahlen im Bereich von 2^64 braucht es nur wenige Sekunden.

    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.
    🙂



  • knivil schrieb:

    b) Du solltest einige gaengige Implementationen vorher mal besichtigen, z.B. msieve. Fuer Zahlen im Bereich von 2^64 braucht es nur wenige Sekunden.

    Pro Zahl, oder? f'`8k

    Autocogito

    Gruß, TGGC (Was Gamestar sagt...)



  • knivil schrieb:

    a) Wo kann ich mich beim Wettbewerb anmelden? 🙂

    Hier. Siehe sig, wenns soweit ist, falls es überhaupt soweit kommt. Aber ich muß mir noch viele Gedanken machen und ich fange auch erst an, wenn ich genug gute Aufgaben habe. So ein Puffer von zwei Jahren schwebt mir vor.

    knivil schrieb:

    b) Du solltest einige gaengige Implementationen vorher mal besichtigen, z.B. msieve. Fuer Zahlen im Bereich von 2^64 braucht es nur wenige Sekunden.

    Lachhaft. 🙂 Wenn die Obergrenze 2^64 ist, gehts Faktorisieren (was deutlich teurer ist als nur Primalität festzustellen) gerne in 1ms. Aber Primzahlen sind ja nur ein Beispiel.

    Ich denke, ich werde auch von Ein- und Ausgabeperformance absehen können, wenn ich den Problemgenerator vorgebe und zum Beispiel als Anfrage nur sende "seed maxwert anzahl" und nur einen Hashwert (normalerweise Summe) der Ausgaben frage. Das Summieren ist aber nur ein Zugeständnis daran, daß manche völlig interesasante Themen recht schnell berechenbar sind und das Programmstarten viel länger dauert als eine einzelne Problemlösung. Bei Sachen wie 9-Live Dreiecke-Rätsel geht die Rechenzeit auch so dermaßen hoch, daß eine Aufgabe pro Programmstart reicht. Vermutlich. Wenn doch mehr als einer eine Lösung in log(n) findet und die Programmstartzeit die Lösezeit überwiegt, müßte ich dann dummerweise diese Aufgabe nochmal starten.

    Ich rechne aber damit, daß viele interessante Probleme so sind, daß sie ruck zuck in wenigen Millisekunden gelöst sind, weshalb ich an die Zeitsumme von 10000 Problemen denke.

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



  • 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.
    🙂



  • ;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



  • 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.
    🙂



  • ;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.



  • 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*
    🙂



  • 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.



  • 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.
    🙂



  • 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+
    🙂



  • 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]
    

    🙂


Anmelden zum Antworten