Schriftliches Dividieren programmieren

[dullifulli]

Hallo Zusammen,
wir sind drei hilflose Studenten und brauchen Unterstützung für eine Aufgabe bezüglich Python.
Wir sollen mit Python die schriftliche Division (bekannt aus der Schule) programmieren.
Wir sind absolute Neulinge und sind kaum vertraut mit Python. Hilfeeeeeee.

[__blackjack__]

@dullifulli: Dann solltet ihr euch als erstes mal mit Python vertraut machen, denn man kann nichts in Python programmieren, wenn man kein oder kaum Python kann. In der Python-Dokumentation ist ein Tutorial, das ihr durcharbeiten könnt.

Danach macht euch Gedanken wie das manuell mit Stift und Papier funktioniert und wie man das als Regeln für jemanden der das nicht kennt, formulieren könnte, so dass der eine Anleitung hat wie man schriftlich dividiert.

Und diese Anleitung müsst ihr dann für jemand sehr dummen (dem Rechner) in Python formulieren.

Wenn ihr dabei dann konkrete Probleme habt, also Code der nicht das tut was er soll, dann könnt ihr das hier zeigen. Also den Code, mit einer Beschreibung was der eurer Meinung nach machen soll, und einer Beschreibung was er stattdessen tut, und warum ihr nicht versteht das er das tut was er tut. Falls es eine Ausnahme gibt, bitte den kompletten Traceback 1:1 zeigen. Ansonsten beschreiben wie das Verhalten vom erwarteten Verhalten abweicht.

[__blackjack__]

Ich habe das für ganze, positive Zahlen gerade mal in JavaScript umgesetzt und war direkt überrascht wie simpel das ist: viewtopic.php?f=5&t=44756#p340897

[Perlchamp]

@dullifulli:
ich glaube modulo (%) könnte euch weiterhelfen. Bin aber selbst nur Anfänger.

[__blackjack__]

@Perlchamp: Naja, Modulo ist ja im Grunde auch Division, nur das man eben den Rest der Division als Ergebnis bekommt und nicht den Quotienten. Würde ich ein bisschen als ”Schummeln” ansehen diese Operation zu verwenden. Ich habe es in JavaScript ja komplett ohne Division gemacht und auch bei der Multiplikation nur mit einer Konstante gearbeitet was wenn man das schriftlich macht ja nicht wirklich multiplizieren ist, oder zumindest beschreibt man das in Worten anders in diesem Fall. Da sagt ja keiner „und dann multipliziert man die Zahl mit Zehn und addiert den Wert einer Ziffer“ sondern „man hängt eine Ziffer an die Zahl an“.

Wenn man den Schritt der ”kleinen” Division vom schriftlichen Dividieren nicht mit addieren und subtrahieren lösen möchte, dann kann man dort auch gleich die `divmod()`-Funktion verwenden, statt Division und Restbildung mit Modulo in zwei Schritten zu machen.

[Perlchamp]

@ _blackjack_ :
oh, das ist schon sehr lange her, das schriftliche Dividieren. Hast aber (wie immer) Recht.

[__blackjack__]

Das ganze mal in 6510-Assembler für den C64. Die Begrenzung des Dividenten auf 127 Ziffern ist ein bisschen willkürlich, weil das eigentlich problemlos ohne grosse Code-Änderung auch mit bis zu 255 Ziffern gehen würde. Die Begrenzung des Divisors auf 4 Ziffern ist in der Begrenzung auf einen 16-Bit-Wert begründet, die ich wiederrum gewählt habe weil das BASIC-ROM praktischerweise eine Ausgaberoutine für 16-Bit-Werte hat die zur Ausgabe von Zeilennummern vom BASIC verwendet wird.

Code: Alles auswählen

;--------------------------------------
; Division of large integer numbers.
; Divident limit: 127 digits.
; Divisor limit: 4 digits.
; Assembler: 64tass
;--------------------------------------

    divisor=$9e
    remainder=$a5
    tmp=$a7
    divident_index=$02
    quotient_index=$a9
    test_data_ptr=$b0

    print=$ab1e
    print_word=$bdcd
    chrout=$ffd2

;--------------------------------------
    *=$0801
    
    .word (+), 2019
    .text $9e, format("%d", main), 0
+   .word 0
;--------------------------------------
main
    lda #<test_data
    sta test_data_ptr
    lda #>test_data
    sta test_data_ptr+1

_loop 
    ; set divisor
    ldy #0
    lda (test_data_ptr),y
    sta divisor
    iny
    lda (test_data_ptr),y
    sta divisor+1

    ; if divisor = 0 then exit
    ora divisor
    beq _exit
    
    ; set divident
    iny
-   lda (test_data_ptr),y
    sta divident-2,y
    beq +
    iny
    bne -
+
    ; advance test_data_ptr
    tya
    sec
    adc test_data_ptr
    sta test_data_ptr
    bcc +
    inc test_data_ptr+1
+
    jsr div   
    jsr print_result
    jmp _loop

_exit
    rts
;--------------------------------------
; In: divident, divisor, quotient, remainder
print_result
    lda #<divident
    ldy #>divident
    jsr print
    lda #":"
    jsr chrout
    ldx divisor
    lda divisor+1
    jsr print_word
    lda #"="
    jsr chrout
    ; TODO Skip leading zeroes.
    lda #<quotient
    ldy #>quotient
    jsr print
    lda #<txt_before_remainder
    ldy #>txt_before_remainder
    jsr print
    ldx remainder
    lda remainder+1
    jsr print_word
    lda #<txt_after_remainder
    ldy #>txt_after_remainder
    jmp print

;--------------------------------------
; In: divident, divisor
; Out: quotient, remainder
div
    lda #0
    sta divident_index
    sta quotient_index
    sta remainder
    sta remainder+1
_loop
    ldy divident_index
    ldx divident,y
    beq _exit
    
    asl remainder   ; remainder *= 10
    rol remainder+1
    lda remainder
    sta tmp
    lda remainder+1
    sta tmp+1
    asl remainder
    rol remainder+1
    asl remainder
    rol remainder+1
    clc
    lda remainder
    adc tmp
    sta remainder
    lda remainder+1
    adc tmp+1
    sta remainder+1
    
    txa     ; Add divident digit
    sec
    sbc #"0"
    clc
    adc remainder
    sta remainder
    bcc +
    inc remainder+1
+
    jsr small_div
    tya
    ora #"0"
    ldy quotient_index
    sta quotient,y
    inc quotient_index

    inc divident_index
    bne _loop
    
_exit
    lda #0
    ldy quotient_index
    bne +
    lda #"0"
    sta quotient,y
    iny
    lda #0
+
    sta quotient,y
    
    rts

;--------------------------------------
; In: remainder, divisor
; Out: Y = quotient, remainder
small_div
    ldy #0
    
-   sec
    lda remainder
    sbc divisor
    tax
    lda remainder+1
    sbc divisor+1
    bcc +
 
    stx remainder
    sta remainder+1
    iny
    bne -

+   rts

;--------------------------------------
txt_before_remainder
    .text " (", 0
txt_after_remainder
    .text ")", 13, 0

; Alternating divisor and 0-terminated
; divident string.
; End marked by 0 word.
test_data
    .word 4
    .text "500", 0

    .word 37
    .text "1260257", 0

    .word 11
    .text "26", 0

    ; Test the limits.
    .word 9999
    .fill 127, "9"
    .byte 0

    .word 0

;--------------------------------------
    .align $100
quotient
    .fill 128
divident
    .fill 128

[Perlchamp]

@ _blackjack_ :
du bist ja im positiven Sinne *verrückt*
ich kann nur das anbieten