Collatz Problem

[Haska92]

Nabend,

ich habe eine Aufgabe bekommen, die ich lösen soll.
Leider habe ich noch kein richtiges Verständnis für python, sodass ich um eure Mithilfe bitte.

Anbei die Aufgabe:

ci+1 = ci /2, wenn ci gerade ist bzw.
ci+1 = 3 · ci − 1, wenn ci ungerade ist.

Somit ergibt sich zum Beispiel für den Startwert n = 19 die Folge
19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, . . .
Es gilt, dass, sobald die Folge einmal den Wert 1 erreicht, anschließend lediglich der
Zyklus 4, 2, 1 wiederholt wird. Es wird vermutet, dass dies für jeden Startwert n passiert,
bewiesen ist dies jedoch bisher nicht. Andererseits ist kein Startwert n bekannt, für den
nicht nach einer endlichen Anzahl von Schritten der Wert 1 erreicht wird.
Schreiben Sie ein Programm collatz.py, welches für die jeden möglichen Startwert
n ∈ [1000] die Länge l(n) der Collatz-Folge zum entsprechenden Startwert ausgibt. Die
Länge von (ci)i∈N ist definiert als das kleinste i, für das ci = 1 und ∞ sonst. Es gilt
also, dass l(1) = 1, l(2) = 2, l(3) = 8 und so weiter. Ihr Programm sollte keine Eingabe
entgegennehmen und die jeweiligen Längen mit der Funktion print ausgeben.

Und so habe ich angefangen:

Code: Alles auswählen

def collatz(n):
	while n > 1:
		if n % 2:
			n = 3 * n +1
		else:
		    n /= 2
		return n

Leider habe ich nun keine Ahnung wie ich weitermachen sollte, vllt könnt ihr mich auf den richtigen Weg bringen.

Vielen Dank

[BlackJack]

@Haska92: Warum hast Du so angefangen? Was macht diese Funktion? Ich frage das nicht weil ich das nicht weiss, sondern weil ich das gerne von Dir erklärt haben möchte. Der nächste Schritt wäre dann nämlich zu klären wo der Unterschied zu dem ist, was Du eigentlich machen möchtest.

Zum Beispiel wie gross das Teilproblem sein soll das von dieser Funktion gelöst wird. Dem Namen nach sollte man daraus eine Funktion machen, welche die Collatz-Reihe liefert. Dann braucht man allerdings nicht ``return`` sondern eine Generatorfunktion. Falls die Funktion schon die Länge liefern soll, dann ist sie ungünstig benannt.

[Üpsilon]

Erstmal muss das return eine Stufe weniger eingerückt werden, sonst wird nach dem ersten Schleifendurchgang sofort ein Ergebnis zurückgegeben. Außerdem willst du laut Aufgabenstellung nicht n zurückgeben, sondern eine Länge, die du in jedem Schleifendurchgang hochzählen musst.

[BlackJack]

@Haska92: Die Beschreibung der Rechenvorschrift für die Folge und die Umsetzung im Code weichen übrigens voneinander ab. Eins davon muss falsch sein.

[heiner88]

Eine ähnliche Aufgabe findet sich in:
viewtopic.php?f=1&t=39304

Wenn du die dortige Lösung verstehst, kannst du auch dieses Problem leicht lösen.

[BlackJack]

In Assembler für eine 16-Bit *.COM-Datei:
[codebox=asm file=Unbenannt.asm] cpu 386
org 100h
[map all]

;--------------------------------------
; Print the Collatz length of all starting values from 1 to 1000.

start:

segment .bss

.i:
resw 1

segment .code

mov word [.i],1
.mainloop:
mov ax,[.i]
cmp ax,1000
jg .done

call collatz_length
mov ax,cx
call print_number

inc word [.i]
jmp .mainloop
.done:
mov ax,4c00h
int 21h

;--------------------------------------
; Calculate the length of the Collatz sequence until 1 is reached.
;
; in:
; ax - n
;
; out:
; cx - length

collatz_length:
xor cx,cx
.L1:
cmp ax,1
je .done
inc cx
test ax,1
jz .even
.odd:
mov bx,ax
shl ax,1
add ax,bx
inc ax
jmp .L1
.even:
shr ax,1
jmp .L1
.done:
ret

;--------------------------------------
; Print unsigned 16 bit value as decimal number followed by CR/LF.
;
; in:
; ax - number

print_number:

segment .data

.scratch_space:
db " ",13,10,'$'

segment .code
mov di,.scratch_space+5
mov cx,10
std
.L1:
or ax,ax
jz .zero
xor dx,dx
div cx
mov bx,ax
mov al,dl
or al,'0'
stosb
mov ax,bx
jmp .L1
.zero:
cmp di,.scratch_space+5
jne .skip
mov al,'0'
stosb
.skip:
cld
inc di
mov dx,di
mov ah,9
int 21h

ret[/code]

[sebastian0202]

Was ich ja spannend finde: es sieht so aus, als gäbe es eine maximale Anzahl an Vorgängen.
Bei Zahlen von 2<n<=10.000.000 gab es nur eine Zahl die genau 685 While Durchläufe brauchte.

Durch unendlich Zahlen wachsen natürlich auch die Durchläufe unendlich an.
Obwohl es zum Ende sehr dünn wird. Gerade so, als müssten sie existieren
um die Logik dahinter zu erfüllen. Lückenfüllerzahlen.

[Dav1d]

In Erlang:

[codebox=erlang file=Unbenannt.txt]
-module(collatz).

%% API
-export([collatz/1]).


% even
collatz(N) when N > 1, N rem 2 =:= 0 ->
[N | collatz(N div 2)];

% odd
collatz(N) when N > 1, N rem 2 =/= 0 ->
[N | collatz(N * 3 + 1)];

collatz(N) ->
[N].
[/code]

Code: Alles auswählen

9> c(collatz).         
{ok,collatz}
10> collatz:collatz(19).
[19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
11> collatz:collatz(1000).
[1000,500,250,125,376,188,94,47,142,71,214,107,322,161,484,
 242,121,364,182,91,274,137,412,206,103,310,155,466,233|...]
12> io:format("~p~n", [collatz:collatz(1000)]).
[1000,500,250,125,376,188,94,47,142,71,214,107,322,161,484,242,121,364,182,91,
 274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,
 1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,
 319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,
 1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,
 976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]
ok

[heiner88]

Den Code habe ich verstanden bis auf Zeile 15+16.
Kannst du kurz erklären, was die machen?

[Dav1d]

Klar

[codebox=erlang file=Unbenannt.txt]
% even (N rem 2 == 0) und N > 1
% konstruiere eine Liste mit N als "Head" der Liste und einem rekursiven collatz Aufruf (welcher eine Liste zurück gibt) als "Rest" der Liste.
collatz(N) when N > 1, N rem 2 =:= 0 ->
[N | collatz(N div 2)];

% odd (N rem 2 != 0) und N > 1
% selbe wie obere Funktion nur andere Bedingung.
collatz(N) when N > 1, N rem 2 =/= 0 ->
[N | collatz(N * 3 + 1)];

% Alle anderen Fälle also N <= 1
% Endbedingung, returne N (was wenn die Serie richtig funktioniert immer 1 ist) in einer Liste, weil als Ergebnis der collatz-Funktion eine Liste erwartet wird
collatz(N) ->
[N].

[/code]

[bwbg]

Und hier das Ganze in Haskell. Ich habe hier die Wert 0 und 1 als Endbedingung gewählt. Darüber hinaus Numeric.Natural, um negative Werte abzufangen (zur Laufzeit, das scheint Dav1ds Lösung nicht abzufangen):[codebox=haskell file=Unbenannt.hs]import Numeric.Natural

collatz :: Natural -> [Natural]
collatz x
| x `elem` [0, 1] = [x] -- Terminal condition
| even x = x : collatz (x `div` 2)
| odd x = x : collatz (x * 3 + 1)[/code]

Code: Alles auswählen

GHCi, version 8.0.1: http://www.haskell.org/ghc/  :? for help
Prelude> :l collatz
[1 of 1] Compiling Main             ( collatz.hs, interpreted )
Ok, modules loaded: Main.
*Main> collatz 0
[0]
*Main> collatz 1
[1]
*Main> collatz 19
[19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
*Main> collatz 1000
[1000,500,250,125,376,188,94,47,142,71,214,107,322,161,484,242,121,364,182,91,27
4,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,
445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1
438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,615
4,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,
92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]
*Main> collatz (-1)
*** Exception: arithmetic underflow
*Main>

@BlackJack: Wo bleibt Deine obligatorische C64-Basic-Lösung?

[Dav1d]

Ja, war etwas zu faul den Guard zu setzen:

[codebox=erlang file=Unbenannt.txt]collatz(N) when N > 1, N rem 2 =:= 0 ->
[N | collatz(N div 2)];

collatz(N) when N > 1, N rem 2 =/= 0 ->
[N | collatz(N * 3 + 1)];

collatz(N) when is_integer(N) ->
[N].
[/code]

Es reicht den Guard auf die Endbedingung zu setzen, da `rem` nur für Integer funktioniert und deshalb der Guard auch nur für Integer greift.

Code: Alles auswählen

1> c(collatz).
{ok,collatz}
2> collatz:collatz(19).
[19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
3> collatz:collatz(19.0).
** exception error: no function clause matching collatz:collatz(19.0) (collatz.erl, line 8)

Der Vollständigkeit halber:

Code: Alles auswählen

4> io:format("Länge: ~p~n", [length(collatz:collatz(1000))]).
Länge: 112

Bzw.:

Code: Alles auswählen

~/workspaces/python/Playground/collatz(branch:master*) » erl -pa . -noshell -eval "io:format(\"Length: ~p~n\", [length(collatz:collatz(1000))]),init:stop()." 
Length: 112

[BlackJack]

Weil bwbg danach gefragt hat.
[codebox=locobasic file=Unbenannt.txt] 10 FOR I=1 TO 1000:N=I:L=0
20 L=L+1:T=INT(N/2):IF N=1 THEN PRINT I,L:NEXT:END
30 IF N-T*2 THEN N=N*3+1:GOTO 20
40 N=T:GOTO 20[/code]
Falls sich jemand fragt warum der Test auf (un)gerade nicht einfach mit ``AND`` gemacht wird: das funktioniert nur solange die Zahl noch als vorzeichenbehaftete 16-Bit Zahl darstellbar ist. Das geht bis I=446 gut. Aber bei I=447 ist die 57. Zahl dann zu gross dafür: 39364.

Laufzeit ist 23½ Minuten.

Edit: Etwas angepasst und mit Kommentaren für den BASIC-Boss-Compiler versehen ist die Laufzeit nur noch 8 Minuten (kompiliert):
[codebox=locobasic file=Unbenannt.txt] 10 REM@ £PROTOCOL:£WORD I=FAST,L=FAST:£FASTFOR:£SHORTIF
20 FOR I=1 TO 1000:N=I:L=0
30 L=L+1:T=INT(N/2):IF N=1 THEN 60
40 IF N-T*2 THEN N=N*3+1:GOTO 30
50 N=T:GOTO 30
60 PRINT I,L:NEXT[/code]
Ich hatte dann auch mal geschaut wie gross N maximal wird, um auszuschliessen das der Wert für den Wertebereich der Gleitkommavariablen nicht zu gross wird, also das noch exakt bleibt. Maximalwert ist 250504.

[Dav1d]

Edit: Etwas angepasst und mit Kommentaren für den BASIC-Boss-Compiler versehen ist die Laufzeit nur noch 8 Minuten (kompiliert):
[snip]
Ich hatte dann auch mal geschaut wie gross N maximal wird, um auszuschliessen das der Wert für den Wertebereich der Gleitkommavariablen nicht zu gross wird, also das noch exakt bleibt. Maximalwert ist 250504.

Schon cool zu sehen wie sich Hard- und Software entwickelt hat, doofer "Benchmark/Vergleich" :

Code: Alles auswählen

27> timer:tc(fun () -> length(collatz:collatz(99999999999999999999999999999999999999999999999999999999999999)) end). 
{3001,1859}

Also 3001 Micorseconds ~3ms.

[BlackJack]

@David: Auch das kompilierte BASIC-Programm muss ja noch mit Gleitkommazahlen in Software auf einem 8-Bit/1 Mhz-Rechner arbeiten. Das ganze in C kann alles mit ganzen Zahlen rechnen und den (un)gerade-Test mit Und-Verknüpfung realisieren, und braucht dann nur noch 2 Minuten:
[codebox=c file=Unbenannt.c]#include <stdint.h>
#include <stdio.h>


int main(void) {
uint16_t i;
register uint16_t length;
register uint32_t number;

for (i = 1; i <= 1000; ++i) {
number = i;
length = 1;
while (number != 1) {
++length;
if (number & 1) {
number = number * 3 + 1;
} else {
number /= 2;
}
}
printf("%4d %d\n", i, length);
}

return 0;
}[/code]
Dein Vergleich hinkt, der berechnet ja was anderes als die Aufgabe. Folgendes C-Programm braucht dafür 21 Sekunden auf dem C64:
[codebox=c file=Unbenannt.c]#include <stdint.h>
#include <stdio.h>
#include "bigint.h"


int main(void)
{
BigInt number;
uint16_t length;

BigInt_init(&number);
BigInt_assign_str(
&number,
"99999999999999999999999999999999999999999999999999999999999999",
10
);
length = 1;
while (!BigInt_equals_uint16(&number, 1)) {
++length;
if (BigInt_is_odd(&number)) {
BigInt_imult_uint16(&number, 3);
BigInt_iadd_uint16(&number, 1);
} else {
BigInt_idiv_2(&number);
}
}
BigInt_destroy(&number);

printf("%d\n", length);
return 0;
}[/code]
Die BigInt-Funktionen sind von mir, ebenfalls in C geschrieben.

[Dav1d]

Ja den "Vergleich" darf man nicht so ernst nehmen, trotzdem fand ich es erwähnenswert.

Hab ich die Aufgabe falsch verstanden. n ∈ [1000], "[1000]" ist keine Liste sondern ein Intervall von 0 bis 1000???...

Also nochmal:

[codebox=erlang file=Unbenannt.txt]47> IF = fun(X) -> io:format("~p -> ~p~n", [X, length(collatz:collatz(X))]) end.
#Fun<erl_eval.6.52032458>
48> OF = fun() -> lists:foreach(IF, lists:seq(0, 1000)) end.
#Fun<erl_eval.20.52032458>
49> timer:tc(OF).
0 -> 1
1 -> 1
2 -> 2
3 -> 8
4 -> 3
5 -> 6
6 -> 9
7 -> 17
[snip]
995 -> 24
996 -> 50
997 -> 50
998 -> 50
999 -> 50
1000 -> 112
{57148,ok}
50> [/code]

Also so, 57ms mit Ausgabe formatieren und in die Konsole schreiben.

[BlackJack]

@Dav1d: Ich habe es als Intervall aufgefasst, weil sonst der Text dazu nicht so viel Sinn macht. Das C-Programm braucht auf meinem Laptop 3ms statt der 2 Minuten auf dem C64.

[BlackJack]

So, jetzt noch mal für den C64 in Assembler. Braucht nur noch 55 Sekunden und ist damit doppelt so schnell wie das C-Programm. Obwohl man an dem Assembler sicher noch ein bisschen schrauben kann, lohnt sich das nicht wirklich, denn die eigentliche Berechnung, wenn man mal die Ausgabe der Zahlen auskommentiert, braucht nur 3 Sekunden. Warum die Ausgabe so lange dauert, wird klar wenn man sich mal überlegt, dass bei einem 25 Zeilen-Display und der Ausgabe von 1000 Zeilen mindestens 975 mal der Text (1000 Bytes) und die Farbinformation (1000 Bytes) bewegt werden müssen und das etwas mehr als 1,8 MiB an Daten sind, die der arme kleine C64 da bewegen muss.

Die Laufzeiten zum Vergleich als Diagramm (Werte in Sekunden):
[codebox=text file=Unbenannt.txt]██████████████████████████████████████████████████████████ 1410 Basic
███████████████████ 480 Basic (comp.)
████ 120 C
██ 55 Assembler
[/code]

[codebox=6502acme file=Unbenannt.txt] !to "test.prg", cbm
!convtab pet
!sl "test.labels"

i = $9e
number = $b0
tmp = $b3
length = $f7

*= $0801

basic_header
!word .next_line
!word 2016 ; BASIC line number.
!pet "ti$", $b2, 34, "000000", 34, ":" ; Set clock to 00:00:00.
!byte $9e ; SYS token.
!byte "0" + (start / 1000), "0" + ((start / 100) % 10)
!byte "0" + ((start / 10) % 10), "0" + (start % 10)
!pet ":", $99, "ti$" ; PRINT clock value.
!byte 0 ; BASIC line end marker.
.next_line
!word 0

;--------------------------------------
!zone
start:
ldx #1 ; i = 1
stx i
dex
stx i+1
.loop:
jsr calculate_length

inc i ; i++
bne .skip
inc i+1
.skip:
lda i ; if i != 1001 then loop
cmp #<1001
bne .loop
lda i+1
cmp #>1001
bne .loop

rts

;--------------------------------------
!zone
calculate_length:
lda i ; number = i
sta number
lda i+1
sta number+1
ldx #1 ; length = 1
stx length
dex
stx length+1
stx number+2
.loop:
lda number ; if number = 1 then exit loop
cmp #1
bne .skip1
lda number+1
ora number+2
beq .exit_loop
.skip1:
inc length ; length++
bne .skip2
inc length+1
.skip2:
lda number
and #1
beq .number_is_even

.number_is_odd:
lda number ; tmp = number * 2
asl
sta tmp
lda number+1
rol
sta tmp+1
lda number+2
rol
sta tmp+2

sec ; number += tmp + 1
lda number
adc tmp
sta number
lda number+1
adc tmp+1
sta number+1
lda number+2
adc tmp+2
sta number+2
bcc .loop
brk ; almost an assertion that number stays < 2^24

.number_is_even:
lsr number+2 ; number /= 2
ror number+1
ror number
bcc .loop ; 'bcc' is possible because number was even!

.exit_loop:
ldx i ; print i and length
lda i+1
jsr $bdcd
lda #' '
jsr $ffd2
ldx length
lda length+1
jsr $bdcd
lda #13
jmp $ffd2

;--------------------------------------[/code]