TS: Algorithmen zum Wochenende

Hello,

wie man Primzahlen auf einfache itertive Weise mit dem Computer bestimmen kann, lernt man wohl in jedem Informatik-Seminar für Programmierer.

Aber wie kann man eventuell auf ähnliche Weise die vollkommenen Zahlen bestimmen?
Hat da jemand einen Tipp für mich?

Liebe Grüße
Tom S.

-- Es gibt nichts Gutes, außer man tut es!
Das Leben selbst ist der Sinn.
  1. Hallo TS,

    Aber wie kann man eventuell auf ähnliche Weise die vollkommenen Zahlen bestimmen?

    Wenn das so einfach ginge, gäb es kein Geheimnis mehr um die geraden vollkommenen Zahlen. Alle ungeraden vollkommenen Zahlen kannst du dir über Mersenne'schen Primzahlen holen. Davon sind ca. 100 bekannt. Wieviele es gibt, ist hingegen unbekannt.

    Bis demnächst
    Matthias

    -- Rosen sind rot.
    1. Hallo Matthias,

      andersrum, gelle? Die bisher bekannten vollkommenen Zahlen sind gerade.

      Rolf

      -- sumpsi - posui - clusi
      1. Hallo Rolf B,

        andersrum, gelle? Die bisher bekannten vollkommenen Zahlen sind gerade.

        Gelle.

        Bis demnächst
        Matthias

        -- Rosen sind rot.
  2. Hello,

    wie man Primzahlen auf einfache itertive Weise mit dem Computer bestimmen kann, lernt man wohl in jedem Informatik-Seminar für Programmierer.

    Aber wie kann man eventuell auf ähnliche Weise die vollkommenen Zahlen bestimmen?
    Hat da jemand einen Tipp für mich?

    Hab meine Idee mal in Haskell aufgeschrieben. Um beispielsweise alle vollkommenen Zahlen kleiner als 1000 zu bekommen (https://repl.it/MztM/1):

    main :: IO () main = putStrLn (show (perfects)) perfects :: [Int] perfects = [ n | n <- [1..1000], isPerfect n] isPerfect :: Int -> Bool isPerfect n = sum (divisors n) == n divisors :: Int -> [Int] divisors n = [ i | i <- [1..n-1], n `mod` i == 0]

    Da besteht natürlich noch viel Optimierungspotenziak, bspw. ist es ziemlich dumm bei der Ermittlung der Teiler von 1 bis n-1 zu laufen.

    PS: Ein cooles Feature von Haskell ist, dass es mit unendlichen Mengen umgehen kann. Die Liste aller perfekter Zahlen wäre einfach [ n | n <- [1..], isPerfect n]. Das lüftet leider nicht alle Geheimnisse um die Zahlen: wenn ich zum Beispiel Haskell frage, ob die Menge endlich ist, dann terminiert Haskell möglicherweise nicht.

    1. Hello,

      wie man Primzahlen auf einfache iterative Weise mit dem Computer bestimmen kann, lernt man wohl in jedem Informatik-Seminar für Programmierer.

      Aber wie kann man eventuell auf ähnliche Weise die vollkommenen Zahlen bestimmen?
      Hat da jemand einen Tipp für mich?

      Hab meine Idee mal in Haskell aufgeschrieben. Um beispielsweise alle vollkommenen Zahlen kleiner als 1000 zu bekommen (https://repl.it/MztM/1):

      Schon mal vielen Dank für Deine Idee. Grund genug, dass ich mich mal mit Haskell auseinandersetze ;-)

      Was ich aber noch nicht ganz verinnerlicht habe:
      Welche Teiler müssen denn definitionsgemäß dabei sein? Eins gehört also immer dazu, die Zahl selber nicht (sonst wäre die Summe ja doppelt so hoch). Aber alle anderen ganzzahligen positiven Teiler gehören nicht unbedingt dazu?!

      Also könnte man doch einen expansiven Algorithmus auf das Problem ansetzen?

      Um den mit der aktuellen Digitaltechnik (64 Bit) erschlagen zu können, müsste man also "nur" passende Shift-Befehle einsetzen, bzw. die dazugehörigen Abbildungsfunktionen.

      Es geht also "nur" darum, den Adressraum virtuell auf N * X Bit zu erhöhen? rara
      Ist mir schon klar, dass das überhaupt schon immer ein Kernproblem der Rechentechnik war.

      Liebe Grüße
      Tom S.

      -- Es gibt nichts Gutes, außer man tut es!
      Das Leben selbst ist der Sinn.
      1. Schon mal vielen Dank für Deine Idee. Grund genug, dass ich mich mal mit Haskell auseinandersetze ;-)

        Wenn du einen guten Einstieg suchst, kann ich dir http://learnyouahaskell.com/ wärmstens empfehlen.

        Was ich aber noch nicht ganz verinnerlicht habe:
        Welche Teiler müssen denn definitionsgemäß dabei sein? Eins gehört also immer dazu, die Zahl selber nicht (sonst wäre die Summe ja doppelt so hoch). Aber alle anderen ganzzahligen positiven Teiler gehören nicht unbedingt dazu?!

        Die deutsche Wikipedia definiert die Funktion σ*(n) als Summe aller (positiven) Teiler von n, ausgenommen n, und die Funktion σ(n) als Summe aller (positiven) Teiler inklusive n. Dann kann man die vollkommen Zahlen entweder als { n ∈ ℕ | σ*(n) = n } oder als { n ∈ ℕ | σ(n) = 2n } definieren. Meine Implementierung stützt sich auf die erste Definition.

        1. Hello,

          Die deutsche Wikipedia definiert die Funktion σ*(n) als Summe aller (positiven) Teiler von n, ausgenommen n, und die Funktion σ(n) als Summe aller (positiven) Teiler inklusive n. Dann kann man die vollkommen Zahlen entweder als { n ∈ ℕ | σ*(n) = n } oder als { n ∈ ℕ | σ(n) = 2n } definieren. Meine Implementierung stützt sich auf die erste Definition.

          Der Hintergrund ist mir schon klar. Aber wie kann man das nun in einer Programmiersprache seiner Wahl realisieren. Die Sprachen scheitern i.d.R. doch alle an der maximalen Darstellbarkeit für Zahlen.

          Liebe Grüße
          Tom S.

          -- Es gibt nichts Gutes, außer man tut es!
          Das Leben selbst ist der Sinn.
          1. Der Hintergrund ist mir schon klar. Aber wie kann man das nun in einer Programmiersprache seiner Wahl realisieren. Die Sprachen scheitern i.d.R. doch alle an der maximalen Darstellbarkeit für Zahlen.

            Sowas wie eine maximale Darstellbarkeit für (natürliche oder ganze) Zahlen gibt es nicht. Haskell kennt zum Beispiel neben beschränkten Datentypen Int, der von -2^29 bis 2^29-1 geht, auch unbeschränkte Datentypen, zum Beispiel für die natürlichen Zahlen. In anderen Programmiersprachen gibt es Bibliotheken dafür. Das Problem ist eher, dass kein Rechner dieser Welt unendlich viel Speicher hat und dieser irgendwann voll läuft und man nicht mehr weitermachen kann, obwohl es eine Repräsentation für jede natürliche Zahl gibt. Man kann sich aber idealisierte theoretische Modelle konstruieren, die diese Beschränkung nicht haben, bspw. die Turing-Maschine oder im Falle von Haskell der Lambda-Kalkül.

            1. Hello,

              Der Hintergrund ist mir schon klar. Aber wie kann man das nun in einer Programmiersprache seiner Wahl realisieren. Die Sprachen scheitern i.d.R. doch alle an der maximalen Darstellbarkeit für Zahlen.

              Sowas wie eine maximale Darstellbarkeit für (natürliche oder ganze) Zahlen gibt es nicht. Haskell kennt zum Beispiel neben beschränkten Datentypen Int, der von -2^29 bis 2^29-1 geht,

              2^64 wäre dann bei einem 64-Bit-Prozessor schon interessanter ;-P

              Aber darum ging es ja gerade. Registerbreite ist nur "Peanuts". Wie kann man ELNs darstellen, die weit über die Registerbreite hinausgehen?

              Also käme als nächste Idee erst einmal eine Grenze für den Zahlenbereich von 0 bis 2^64^64 Bit in Frage. Wie baut man sowas? Da muss man ja dann swappen, weil der Arbeitsspeicher nicht mehr ausreicht. Aber wie kann man den Algorithmus und das Paging so geschickt aufbauen, dass trotzdem wenig Swaps notwendig sind?

              Glück Auf
              Tom S. vom Berg

              -- Es gibt nichts Gutes, außer man tut es!
              Das Leben selbst ist der Sinn.
              1. Aber darum ging es ja gerade. Registerbreite ist nur "Peanuts". Wie kann man ELNs darstellen, die weit über die Registerbreite hinausgehen?

                Keine Ahnung wie man bspw. einen Algorithmus zur Addition zweier natürlicher Zahlen direkt in Assembler kodieren würde oder ob so eine Implementierung überhaupt erstrebenswert wäre. Solche Algorithmen implementiert man in der Regel in einer höheren Programmiersprache und lässt den Compiler die Details herausfinden. Du kannst dir ja mal angucken, was der Haskell-Compiler dir ausspuckt, aber ich bezweifle, dass man auf so niedriger Ebene noch etwas vom ursprünglichen Algorithmus wiedererkennt. Immerhin fallen vom menschenlesbaren Programmcode bis zum maschinen-ausführbaren Assemlber-Code einige Transformationen an.

                1. @@1unitedpower

                  Immerhin fallen vom menschenlesbaren Programmcode bis zum maschinen-ausführbaren Assemlber-Code einige Transformationen an.

                  Assembler-Code ist nicht maschinen-ausführbar, sondern – mehr oder weniger – menschenlesbar.

                  Am in diesem Thread schon erwähnten LC 80 könnte ich dir den Unterschied anschaulich machen. Da gibt man nämlich keinen Assembler-Code ein, sondern den tatsächlichen Maschinencode.

                  LLAP 🖖

                  -- “When UX doesn’t consider all users, shouldn’t it be known as ‘Some User Experience’ or... SUX? #a11y” —Billy Gregory
                  1. Am in diesem Thread schon erwähnten LC 80 könnte ich dir den Unterschied anschaulich machen. Da gibt man nämlich keinen Assembler-Code ein, sondern den tatsächlichen Maschinencode.

                    Stimmt natürlich, bis zum Maschinencode wäre es noch eine weitere Code-Transformation. Kann man sich natürlich auch angucken, aber da wird man wohl noch weniger schlau draus.

                    1. Hello,

                      Am in diesem Thread schon erwähnten LC 80 könnte ich dir den Unterschied anschaulich machen. Da gibt man nämlich keinen Assembler-Code ein, sondern den tatsächlichen Maschinencode.

                      @Gunnar Bittersmann:
                      Hast Du tatsächlich in Maschinencode programmiert? Das war eklig! Ich habe das damals ganz schnell übersprungen. Assembler und Assembler-IDEs waren da schon interessanter, auch als ich schon lange meterlange Programme in Turbo-Pascal geschrieben habe, bzw. der Kollege in Modula-2. Da gab es immer zeitkritische Passagen, die man mittels "asm" in Assemblercode eingebaut hat. TP oder Modula-2 waren aufgrund der möglichen strengen Typenbindung und des konsequenten Rangecheckings beim DLR und seinen Ablegern vorgeschrieben. Mit C/++ hätten die keine Flugsteuersoftware geschrieben!

                      Stimmt natürlich, bis zum Maschinencode wäre es noch eine weitere Code-Transformation. Kann man sich natürlich auch angucken, aber da wird man wohl noch weniger schlau draus.

                      @1unitedpower:
                      Der ist mMn auch nur interessant, wenn man auf Hardwareebene (Steuerbus, Datenbus, Adressbus und Serial-Parallel-Konvertern) mittels "doofem" Logikanalyser Glitches suchen muss. Damals waren die Analyser nämlich nicht viel schneller, als die produktiven Prozessoren.

                      Liebe Grüße
                      Tom S.

                      -- Es gibt nichts Gutes, außer man tut es!
                      Das Leben selbst ist der Sinn.
                      1. @@TS

                        Hast Du tatsächlich in Maschinencode programmiert?

                        Das Programm überlege ich mir schon erst in Assemblersprache. Dann übersetze ich es in Maschinencode – mit Befehlstabelle. Ich bin der Assembler. That’s where the fun is.

                        LLAP 🖖

                        -- “When UX doesn’t consider all users, shouldn’t it be known as ‘Some User Experience’ or... SUX? #a11y” —Billy Gregory
    2. @@1unitedpower

      wenn ich zum Beispiel Haskell frage, ob die Menge endlich ist, dann terminiert Haskell möglicherweise nicht.

      Möglicherweise doch – nach 7,5 Millionen Jahren. Um dann die Antwort auszugeben.

      LLAP 🖖

      -- “When UX doesn’t consider all users, shouldn’t it be known as ‘Some User Experience’ or... SUX? #a11y” —Billy Gregory
      1. Hallo,

        wenn ich zum Beispiel Haskell frage, ob die Menge endlich ist, dann terminiert Haskell möglicherweise nicht.

        Möglicherweise doch – nach 7,5 Millionen Jahren. Um dann die Antwort auszugeben.

        und dann habe die Leute die Frage vergessen 😀

        Gruß
        Jürgen

  3. @@TS

    wie man Primzahlen auf einfache itertive Weise mit dem Computer bestimmen kann, lernt man wohl in jedem Informatik-Seminar für Programmierer.

    Auf dem Vintage Computing Festival Berlin (wo keiner von euch Banausen mit hin wollte) kam mir die Idee, meinen LC 80 mal wieder rauszukramen und das Sieb des Eratosthenes darauf zu implementieren – in einem Kilobyte RAM für Programm und Daten!

    Heute mal mit Stift und Papier damit angefangen. Puh, ewig keinen Maschinencode mehr geschrieben!

    Dummerweise finde ich das Netzteil für den LC 80 gerade nicht. (Ich hatte nur einen Trafo ohne Gehäuse.) Muss mich mal nach einem passenden Netzteil umsehen, um das Ding wieder in Betrieb zu nehmen.

    LLAP 🖖

    -- “When UX doesn’t consider all users, shouldn’t it be known as ‘Some User Experience’ or... SUX? #a11y” —Billy Gregory
    1. Hallo,

      Maschinencode

      sieht aber korrekt aus ;p

      Gruß
      Kalk

    2. Hello,

      Auf dem Vintage Computing Festival Berlin (wo keiner von euch Banausen mit hin wollte) [...]

      Stimmt ja gar nicht. Wir waren nur nicht ausreichend primed ;-)

      Jedenfalls habe ich sowas (Sieb des ...) auch noch in Assembler programmiert, allerdings dann schon für einen 8088, dafür aber schon mit Auslagerungsdatei auf einem DiskDrive puh...

      Das müsste doch heutzutage schon alles viel einfacher gehen. Einfach Auslagerungsdatei auf 10fachen Hauptspeicher einrichten, usw. ...

      Oder?

      Liebe Grüße
      Tom S.

      -- Es gibt nichts Gutes, außer man tut es!
      Das Leben selbst ist der Sinn.