N-Queens Problem


  • Xerxes
  • 1601 Aufrufe 6 Antworten

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • N-Queens Problem

    Hallo an die ASM-Coder,

    ich erstelle gerade anhand des bekannten N-Damen-Problems einen Geschwindigkeitsvergleich für Taschenrechner und Pocket-Computer. Zum besseren Vergleich habe ich auch einige andere Systeme mit in die Tabelle aufgenommen.

    Ich würde gern auch den C64, unbestritten der Homecomputer schlechthin, in die Tabelle aufnehmen, würde dazu aber eure Hilfe benötigen. Unter Calculator Benchmark sind bereits mehrere Assembler-Versionen zu finden. Falls interesse besteht, kann ich den Quellcode kommentieren.

    Natürlich sind auch Ergebnisse anderer Programmiersprachen willkommen.
  • RE: N-Queens Problem

    Hallo Xerxes,

    ich habe dein N-Damen-Problem mal in c64-Assembler umgesetzt. Das Programm braucht für 1000 Wiederholungen 107 Sekunden. Es kann mit dem Assembler dasm übersetzt werden. Man kann das fertig übersetzte Programm mit RUN starten.

    Vorbild für mein Programm war das unstrukturierte C-Programm.

    Der C64 hat einen 6502-Prozessor, der mit etwa 0,985 MHz getaktet wird. Beim Test war der Interrupt aktiv und der Bildschirm war eingeschaltet.

    Viel Spaß mit dem Programm!
    Dateien
    • queens.txt

      (1,22 kB, 23 mal heruntergeladen, zuletzt: )
    • queens.prg

      (90 Byte, 8 mal heruntergeladen, zuletzt: )
  • Hallo Mafiosino,

    vielen Dank für deine Umsetzung. Ich habe zwar inzwischen auch eine Version gecoded, diese aber nicht testen können, da ich kein C64 habe. Allerdings hat mir die Analyse deines Programms geholfen, einige Eigenheiten des 6502 besser zu verstehen und meine Version zu debuggen. :)

    Hier ist meine Version (Vorbild war der HD61700 Code):

    Quellcode

    1. $0002: R
    2. $0003: S lo
    3. $0004: S hi
    4. $0005: T
    5. $0006: A[]
    6. LDA #$08
    7. STA $02
    8. LDX #$00
    9. STX $03
    10. STX $04
    11. L0 CPX $02
    12. BEQ L5
    13. INX
    14. LDA $02
    15. STA $06,X
    16. L1 TXA
    17. TAY
    18. INC $03
    19. BNE L2
    20. INC $04
    21. L2 DEY
    22. BEQ L0
    23. LDA $06,X
    24. SEC
    25. SBC $06,Y
    26. BEQ L4
    27. BCS L3
    28. EOR #$FF
    29. ADC #$01
    30. L3 STA $05
    31. TYA
    32. CLC
    33. ADC $05
    34. STA $05
    35. CPX $05
    36. BNE L2
    37. L4 DEC $06,X
    38. BNE L1
    39. DEX
    40. BNE L4
    41. L5 RTS
    Alles anzeigen

    Vermutlich wird es bei der Laufzeit keinen nennenswerten Unterschied geben. Der 6502 ist bisher der schnellste 8-Bit-Prozessor im Verhältnis zur Taktfrequenz.

    Wenn die Interrupts gesperrt und der Bildschirm ausgeschaltet wären, könnte man dann einfach die Takte der Befehle addieren um auf die Laufzeit zu schliessen? Ich war nämlich schon dabei einen kleinen Emulator in Pascal zu schreiben, der die Takte der Befehle addiert.
  • Original von Xerxes
    Wenn die Interrupts gesperrt und der Bildschirm ausgeschaltet wären, könnte man dann einfach die Takte der Befehle addieren um auf die Laufzeit zu schliessen? Ich war nämlich schon dabei einen kleinen Emulator in Pascal zu schreiben, der die Takte der Befehle addiert.

    Ja, das kann man. Wieso benutzt du dafür aber nicht einen der schon existierenden Emulatoren? VICE z.B. kann auch Taktzyklen zählen...

    Gruß,
    - Spiro.
  • Hallo strik,

    danke für deinen Hinweis. Natürlich habe ich mir schon gedacht, daß es sowas gibt. Ich bin aber davon ausgegangen, daß es länger dauert sich dort einzuarbeiten, als ein kleines Pascal-Programm zu schreiben, was etwas über eine Stunde gedauert hat.

    Das Programm ist auf 100007 Takte gekommen, also 100007 / 1 MHz = ~0,100 Sekunden, was ja in etwa mit Mafiosinos Ergebnis übereinstimmt. Ich habe deshalb 1 MHz angenommen, da es ja die PAL- und die NTSC- Version gibt.
  • Original von Xerxes
    @strik:
    So, habe nun doch Win-VICE heruntergeladen um ein paar Tests in BASIC zu machen, finde aber nicht heraus wo ich die Anzahl der Takte ersehen kann.

    Du mußt VICE selbst kompilieren, und zwar so, dass das C-Makro DEBUG definiert ist (#define DEBUG 1). Dann gibt es im File Menü einen Unterpunkt Debug, wo du einstellen kannst, was (CPU, Drive 8, Drive 9) du debuggen willst. Hier gibt dir VICE dann in die VICE.LOG immer aus, welcher Befehl gerade abgearbeitet wird, wie die Register stehen, und welcher Taktzyklus das gerade ist.

    Hiermit kann man wunderbar Taktzyklen zählen lassen.

    Gruß,
    Spiro
  • Benutzer online 1

    1 Besucher

  • Tags