Fibonacci-Zahlen in MBASIC / GW-BASIC

Zeile 80

80 IF C#>L THEN GOTO 200

wäre was für den Herrn Dijkstra ...

und das gleich in doppelter Hinsicht ( Typfehler, Sprung )

Fibonacci mit beliebig großen Zahlen wird dann aber schon schnell eng.

Da das mit den großen Zahlen ja evtl interessant lösbar schien, habe ich gestern mal was gebastelt, was das Thema zumindest ein wenig angeht.

Die Berechnung erfolgt hier direkt "ohne" Berechnung. Es werden einfach die Additionen der Einzelziffern aus einem Array ausgelesen und die beiden Zahlen (die man addieren will) dazu stückweise in Einzelzeichen / Ziffern zerlegt - und zwar als String$ Operationen. Dadurch kann eine Zahl erstmal so lang sein, wie es das jeweilige BASIC für einen String$ erlaubt.

REM Fibonacci Reihe berechnen - aber mit String$'s statt Zahlen
REM Vorteil: sehr lange Zahlen sind moeglich ...
REM
REM benutzt eine Matrix mit den Ergebnissen der einstelligen
REM Addition und eine Zusatzmatrix fuer die dabei auftretenden
REM Ueberlaeufe
REM String$'s werden von rechts in Einzelcharakters zerlegt und
REM jeweils der Ergebniswert in der ersten Matrix nachgesehen

REM Fibonacci Reihe (Prinzip)
REM addiert immer den letzten und vorletzten Wert einer Reihe,
REM die mit 0 und 1 beginnt ; also 0 1 1 2 3 5 8 13 21 usf

DIM Addition$(9, 9), Uebertrag(9, 9)

FOR I = 0 TO 9
  FOR J = 0 TO 9
    READ Addition$(I, J)
  NEXT J
NEXT I

REM   0   1   2   3   4   5   6   7   8   9

DATA "0","1","2","3","4","5","6","7","8","9" : REM 0
DATA "1","2","3","4","5","6","7","8","9","0" : REM 1
DATA "2","3","4","5","6","7","8","9","0","1" : REM 2
DATA "3","4","5","6","7","8","9","0","1","2" : REM 3
DATA "4","5","6","7","8","9","0","1","2","3" : REM 4
DATA "5","6","7","8","9","0","1","2","3","4" : REM 5
DATA "6","7","8","9","0","1","2","3","4","5" : REM 6
DATA "7","8","9","0","1","2","3","4","5","6" : REM 7
DATA "8","9","0","1","2","3","4","5","6","7" : REM 8
DATA "9","0","1","2","3","4","5","6","7","8" : REM 9

FOR I = 0 TO 9
  FOR J = 0 TO 9
    READ Uebertrag(I, J)
  NEXT J
NEXT I

REM   0  1  2  3  4  5  6  7  8  9

DATA  0, 0, 0, 0, 0, 0, 0, 0, 0, 0 : REM 0
DATA  0, 0, 0, 0, 0, 0, 0, 0, 0, 1 : REM 1
DATA  0, 0, 0, 0, 0, 0, 0, 0, 1, 1 : REM 2
DATA  0, 0, 0, 0, 0, 0, 0, 1, 1, 1 : REM 3
DATA  0, 0, 0, 0, 0, 0, 1, 1, 1, 1 : REM 4
DATA  0, 0, 0, 0, 0, 1, 1, 1, 1, 1 : REM 5
DATA  0, 0, 0, 0, 1, 1, 1, 1, 1, 1 : REM 6
DATA  0, 0, 0, 1, 1, 1, 1, 1, 1, 1 : REM 7
DATA  0, 0, 1, 1, 1, 1, 1, 1, 1, 1 : REM 8
DATA  0, 1, 1, 1, 1, 1, 1, 1, 1, 1 : REM 9


REM Startwerte sind "0" und "1" in SUMMAND1 (S1$) und SUMMAND2 (S2$)

S1$ = "0"
S2$ = "1"

PRINT : PRINT " Fibonacci Numbers  ( press SPACE for next , ESC for end)"
PRINT S1$; " - "; S2$;

START:

REM beide Strings auf gleiche Laenge bringen ( Auffuellen mit "0" )

L2 = LEN(S2$)

LABEL1:

L1 = LEN(S1$)

IF L1 < L2 THEN S1$ = "0" + S1$: GOTO LABEL1


REM C$ Zwischenaddition / Ergebnis der Addition zweier Ziffern
REM EG$ Ergebnis String , wird spaeter dann zum naechsten S2$ (und S2$ zu S1$)
REM UB - Uebertrag aus der Uebertrag-Matrix
REM XB - eXtra Uebertrag, wenn nach Addition mit UB=1 ein 9 nach 0 auftritt

C$ = "": EG$ = "": UB = 0

REM die Strings von rechts nach links ziffernweise durchaddieren

FOR I = L1 TO 1 STEP -1

  A$ = MID$(S1$, I, 1): A = ASC(A$) - 48
  B$ = MID$(S2$, I, 1): B = ASC(B$) - 48
 
  C$ = Addition$(A, B)

  XB = 0
  IF UB = 1 THEN
    C = ASC(C$) - 48: C$ = Addition$(C, 1)
    IF C = 9 THEN XB = 1
  END IF

  UB = Uebertrag(A, B)

  UB = UB OR XB

  EG$ = C$ + EG$

NEXT I

IF UB = 1 THEN EG$ = "1" + EG$

PRINT " - "; EG$;

REM Stringvariablen fuer die kommende Runde setzen (Letzter und Vorletzter)

S1$ = S2$
S2$ = EG$


REM Tasten: SPACE - naechste Zahl , ESC - Ende

KEYTEST:

K$ = INKEY$

IF K$ = CHR$(32) THEN GOTO START
IF K$ = CHR$(27) THEN END

GOTO KEYTEST

Probe aufs Fibo ... ( äh Exempel )

_{Bild1 Testlauf mit noch kleinen Zahlen}

In der Version hier wird die Auswertung der Überträge in einem IF Block gemacht. Das haben nun nicht alle BASICs , daher würde man dort stattdessen wohl einen Sprung benutzen (siehe nächstes Bild)

Außerdem wird das C dabei auf einen Wert direkt abgefragt, was auch eleganter geht, indem man das Array der Überträge benutzt (wenns eh' schonmal da ist; C+1 bedeutet zweite Zeile auslesen (zweite Spalte ginge natürlich auch)).

Das XB=0 vor der Konstruktion (egal ob vor dem IF Block oder vor dem Sprung) ist nötig, da es sonst nicht notwendigerweise zurückgesetzt würde, da ja nicht jede Stelle in die Übertragsauswertung "reinläuft".

_{Bild2 die Version mit GOTO}

Zumindest kommt man so schonmal auf ganz schön lange Zahlen, wo man nicht mehr wüßte, wie die benannt werden ( was kommt nach der Trilliarde ... (?) ). Und die Zahlen sind schön exakt (wenn nicht noch irgendwo ein Fehler schlummert), und enden nicht nach 8 Stellen und sagen dann nur noch den 10er Exponenten dazu an (sowas macht da schnell auch ganz schön große Fehler; fast wie bei den Astronomen).

Wer das noch weitertreiben will: Es ist eigentlich auch sehr schön möglich das von den Strings weg und hin zu einer PEEK/POKE Variante umzubauen. Dort würde man die Zahlen / Ziffern als BYTEs direkt im Speicher ablegen (quasi als ein langes Feld; kann man je nach BASIC wahrscheinlich sogar als DIM und mit Indexzugriff machen, wenn so große DIMs erlaubt sind). Dabei könnte dann eine Zahl ungefähr so groß sein wie ein Drittel des verfügbaren freien Speichers, bei 64kByte sind das schonmal ca. 21000 Stellen ... ; mit ein bißchen Trickserei kann man auch die Ergebnisziffern gleich in den Summanden S1$ fortlaufend "einarbeiten" und muß dann in jedem Durchgang beachten, daß die beiden Summanden jetzt quasi immer "wechseln" und daher das nächste Ergebnis, dann direkt in den anderen Bereich geschrieben werden muß. Damit sollten dann bei 64KByte etwas um 32000 Stellen möglich werden (vielleicht bißchen weniger, da das Programm ja auch Platz braucht).

Wer Fehler findet, darf die gerne mitteilen ! (und nicht selbst behalten).

Optimierung: die Zugriffe in ein zweidimensionales Array (zum Addieren) sind wahrscheinlich relativ langsam - evtl. ließen sich da auch einzelne Zeilen (eindimensional) draus machen ; die Überlauftabelle kann je nach CPU evtl als Bitmuster viel schneller ausgelesen werden (Shifts) ; die Stringverwaltung mit MID$ ist wahrscheinlich gewaltig langsam, wobei man ja eigentlich weiß, daß man immer nur genau ein Byte an einer definierten Position auslesen will ; beliebigere Größen ließen sich evtl auch durch Abspeichern/Nachladen von Teilbereichen der Zahlen (Bruchstücke; "Quanteln" mit z.B. 5000 Ziffern) erreichen ; usf

.

Hier jetzt noch einer der Vorschläge. Diesmal werden die Zahlen in Form von Einzelziffern innerhalb eines Arrays abgelegt. Dabei bekommt erstmal jeder Summand sein eigenes Array. Auf das Ergebnisarray wird verzichtet - und damit auf das aufwendige Umschreiben des fertigen Ergebniswertes in eines der Summandenarrays. Stattdessen werden die Zwischenergebnisse der Ziffernadditionen direkt in das Summandenarray geschrieben, in dem die Zahl liegt, die aktuell die VORLETZTE in der Reihe ist. D.h. während der Berechnung steht in diesem Array ein lustiger Mix aus Ziffern der VORLETZTEN Zahl, die noch nicht mit Ziffern der LETZTEN Zahl addiert worden sind, und daneben bereits die ersten Ziffern aus dem Ergebniswert.

Damit das klappt, gibt es einen Rundenzähler (RD), der immer zwischen den Werten "1" und "2" hin und her wechselt. Je nachdem wird dann in S1%() oder S2%() gelesen / geschrieben. VORLETZTE und LETZTE Zahl der Folge wechseln also in jeder Runde gewissermaßen die Plätze (bzw. das Array).

REM Fibonacci Reihe berechnen - aber mit DIM's statt Zahlen
REM Vorteil: sehr lange Zahlen sind moeglich ...
REM Jede Ziffer, d.h. "Byte" des Arrays, wird einzeln betrachtet
REM Gezaehlt wird dabei von Pos 1 an aufwaerts, die kleinste
REM Stelle der Zahl ist also Pos 1 im Array, die Zahl wird
REM gewissermassen "nach rechts" verlaengert

REM Fibonacci Reihe (Prinzip)
REM addiert immer den letzten und vorletzten Wert einer Reihe,
REM die mit 0 und 1 beginnt ; also 0 1 1 2 3 5 8 13 21 usf

REM FRE("-1") zeigt die maximal moegliche Laenge fuer ein Feld
REM PRINT FRE("-1")

REM LGMAX - die maximale Zahlenlaenge

LGMAX = 256
DIM S1%(LGMAX), S2%(LGMAX)

FOR I = 0 TO LGMAX - 1
  S1%(I) = 0
  S2%(I) = 0
NEXT I

REM Startwerte sind "0" und "1" in SUMMAND1 (S1%) und SUMMAND2 (S2%)

S1%(1) = 0
S2%(1) = 1

REM LG - die aktuelle Laenge der Zahl
REM RD - zaehlt ob in dieser Runde S1% oder S2% das Ergebnisarray ist,
REM      wechselt dafuer jede Runde zwischen "1" und "2" (neu=3-act)

LG = 1
RD = 2

PRINT : PRINT " Fibonacci Numbers  ( press SPACE for next , ESC for end )"
PRINT CHR$(S1%(1) + 48); " - "; CHR$(S2%(1) + 48);

START:

REM EG$ Ergebnis String
REM UB - Uebertrag

UB = 0

REM die Ziffern im Array einzeln (ziffernweise) durchaddieren

RD = 3 - RD

FOR I = 1 TO LG
  A = S1%(I)
  B = S2%(I)
  C = A + B

  IF UB = 0 THEN GOTO LABEL1

    C = C + 1
    UB = 0

LABEL1:

  IF C >= 10 THEN UB = 1: C = C - 10
 
  IF RD = 1 THEN S1%(I) = C ELSE S2%(I) = C

NEXT I


IF UB = 0 THEN GOTO LABEL2

  LG = LG + 1
  IF RD = 1 THEN S1%(LG) = 1 ELSE S2%(LG) = 1


LABEL2:


REM die aktuelle Zahl ausgeben

EG$ = ""

FOR I = LG TO 1 STEP -1
  IF RD = 1 THEN C = S1%(I) + 48 ELSE C = S2%(I) + 48
  REM PRINT CHR$(C);
  EG$ = EG$ + CHR$(C)
NEXT I

PRINT " - "; EG$;

IF LG >= LGMAX - 1 THEN PRINT : PRINT "maximale Arraylaenge erreicht ...": END


REM Tasten: SPACE - naechste Zahl , ESC - Ende

KEYTEST:

K$ = INKEY$

IF K$ = CHR$(32) THEN GOTO START
IF K$ = CHR$(27) THEN END

GOTO KEYTEST

Die schöne (und interessant krude) Variante der Addition durch Auslesen aus einer Matrix ist hier jetzt schnödem normalen Addieren der Einzelziffern gewichen. Dabei werden wieder die Überträge extra beachtet / bearbeitet.

Die Maximallänge der Arrays kann man wohl mit FRE("-1") ermitteln - es ist aber dann möglich auch längere Werte zu definieren, ohne daß ein Out Of Memory Error o.ä. kommt ... irgendwie sehr seltsam. Deshalb muß das per Hand gemacht werden und LGMAX sinnvoll vorgegeben werden. Längen um 1024 oder 4096 Ziffern für beide Arrays sollten aber problemlos sein. Prinzipiell sollte man den Speicher auch komplett mit beiden Arrays (je 1/2 VariablenRAM) ausfüllen können.

IF Blöcke sind wieder aufgelöst in GOTOs ; sollte also auch in uralt BASICs laufen.

_{Bild1 Fibonacci Zahlen mit Einzelzifferaddition in Arrays}

Die Definition der Arrays als S1%() , S2%() legt ja nicht zwangsläufig BYTEs an. Das können also auch 16Bit Zahlen oder 32Bit sein. Auf BASICs, die DIM Variable%() nicht kennen, wird es entsprechend noch mehr ( DIM S1(256) mit je 5 BYTE o.ä. ). D.h. es geht durchaus speicher"effektiver".

{ Die vermutlich interessanteste Variante wären wohl echte BYTEs (d.h. per PEEK/POKE) und darin BCD codierte Ziffern mit je 4 Bit pro Ziffer. Dann könnten immer eine Ziffer von S1% und S2% in einem BYTE liegen. (auf dem 6502 müßte das auch superschnell per Assembler addierbar sein, da es da ja diesen Dezimalmodus gibt). }

.

256 Ziffern sind ganz schön lang ...

Interessanterweise gibt es in der aktuellen c't gerade eine Einführung ins Programmieren und auch Artiekl zu Python / Java / JavaScript - und auch einen kleinen Abschnitt zum Thema Fibonacci Zahlen auf der Commandline. Vielleicht schön als Ergänzung zu hier mal anzusehen.

Schönes Bild gibts auch dazu

( sicher auch ein schöner Hintergrund ; PicDirect )

Weil es eine nette Spielerei war, habe ich auch mal ein BASIC Progrämmchen versucht.

Hier werden 3 BCD Ziffern in ein 16-bit Integer verpackt. 4 Ziffern wären effektiver, aber mühsam, weil die alten BASICs nur Vorzeichen behaftete Zahlen kennen und dann viele Tests und Umrechnungen nötig werden um einen Überlauf zu vermeiden.

Das Programm läuft unter MS-DOS MBASIC, GW-BASIC und QBASIC. Es sollte eigentlich auch unter CP/M MBASIC laufen.

Mit den kurzen ANSI Variablennamen ist es auch an Minimal BASIC Implementierungen anpassbar.

Zeilennummern werden nur für zwei Unterprogramme zur Konvertierung Zahl <-> String (GOSUB xxxx) verwendet, bei moderneren BASICs kann man das natürlich in richtige SUBs und CALLs ändern. Wegen der Unterprogramme ist etwas Umkopiererei der Parameter erforderlich, das Ganze läuft so relativ gemächlich, ist aber viel übersichtlicher als ohne Unterprogramme.

So läuft es aber auch auf älteren Systemen.

Ich habe es nur so weit getrieben, dass die 80 Spalten ausgefüllt werden, prinzipiell kann man aber die Maximalzahl der Ziffern "beliebig" erhöhen.

Interessanterweise lassen sich in GW-BASIC und QBASIC mit "PRINT ... ;" die Zeilen mit exakt 80 Zeichen ausgeben ohne dass ein Zeilenumbruch erfolgt, bei MBASIC erfolgt trotz angehängtem ";" ein Zeilenumbruch. Da müsste man dann ein Leerzeichen weniger ausgeben, damit die Zahlen rechtsbündig ohne Leerzeile ausgegeben werden.

Kannst du das Programm nochmal mit kopierbaren Zeilennummern reinstellen?