Archiv der Kategorie: Mathematik

Restklassenrundung

Veröffentlicht am von
2

English

Das Konzept der Rundung kennt man grundsätzlich. Aber versuchen wir es etwas systematischer zu erfassen.

Man hat eine Menge M von Zahlen und eine Teilmenge N \subseteq M davon, deren Elemente in der verwendeten Programmierumgebung dargestellt werden. Dazu hat man noch eine Metrik d : M \times M \rightarrow \Bbb R_+, (x, y) \mapsto r=d(x,y)>=0. Man verlangt normalerweise noch gewisse Eigenschaften von d:

  • Positive Definitheit: d(x,y) = 0 \iff x = y
  • Symmetrie: d(x,y)=d(y,x)
  • Dreiecksungleichung: d(x,z) \le d(x,y) + d(y,z)

Typischerweise sind die Zahlen, mit denen wir uns meistens beschäftigen, in der Welt der reellen und komplexen Zahlen gedacht, man kann also fast immer sicher sein, dass M \subseteq \Bbb C ist, meistens sogar M \subseteq \Bbb R oder wenn wir ehrlich sind sogar M \subseteq \Bbb Q. Dann ist normalerweise d(x,y) = |x-y|. Wer die komplexen Zahlen noch nicht kennt, denke einfach an reelle und rationale Zahlen, das ist das, womit wir normalerweise bewusst zu tun haben. Dabei sind natürlich Konzepte wie Rundung speziell in p-adischen Zahlen hochinteressant, aber dafür muss ich die erstmal erklären und das lasse ich heute…

Was stellen wir uns nun unter einer Rundung vor?
Vielleicht eine Abbildung
r: M \rightarrow N, x \mapsto r(x),
die mit gewissen Nebenbedingungen für jedes x jeweils so gewählt wird, dass d(x, r(x)) minimal ist.
Die Nebenbedingungen brauchen wir einerseits, um es eindeutig zu machen, wenn mehrere Werte y\in N existieren, für die d(x,y) minimal ist. Der klassische Fall ist das Runden auf ganzzahlige Werte und die Frage mit der 0.5. Wenn N eine Teilmenge der reellen Zahlen ist, was ja „meistens“ der Fall ist, hat man eine Anordung. Da kommen dann die folgenden Constraints zum Tragen (Beispiel immer mit Rundung auf ganze Zahlen):

ROUND_UP
|r(x)|\ge |x| Z.B. r(0.4)=1 und r(0.5)=1 und r(-0.5)=-1
ROUND_DOWN
|r(x)|\le |x| Z.B. r(0.6)=0 und r(0.5)=0 und r(-0.5)=0
ROUND_CEILING
r(x) \ge x Z.B. r(0.4)=1 und r(0.5)=1 und r(-0.5)=0
ROUND_FLOOR
r(x) \le x Z.B. r(0.6)=0 und r(0.5)=0 und r(-0.5)=-1
ROUND_HALF_UP
Minimiere d(r(x),x), aber wenn es mehrere optimale Werte für r(x) gibt, wähle den am weitesten von 0 entfernten, z.B. r(0.4)=0 und r(0.6)=1 und r(0.5)=1 und r(-0.5)=-1
ROUND_HALF_DOWN
Minimiere d(r(x),x), aber wenn es mehrere optimale Werte für r(x) gibt, wähle den am nächsten an 0, z.B. r(0.4)=0 und r(0.6)=1 und r(0.5)=0 und r(-0.5)=0
ROUND_HALF_CEILING
Minimiere d(r(x),x), aber wenn es mehrere optimale Werte für r(x) gibt, wähle den größten, z.B. r(0.4)=0 und r(0.6)=1 und r(0.5)=1 und r(-0.5)=0
ROUND_HALF_FLOOR
Minimiere d(r(x),x), aber wenn es mehrere optimale Werte für r(x) gibt, wähle den kleinesten, z.B. r(0.4)=0 und r(0.6)=1 und r(0.5)=0 und r(-0.5)=-1
ROUND_HALF_EVEN
Minimiere d(r(x),x), aber wenn es mehrere optimale Werte für r(x) gibt, wähle den mit gerader Endziffer. Achtung, dieser Constraint ist im „klassischen“ Fall anwendbar, aber nicht allgemeingültig. Z.B.: r(0.4)=0 und r(0.6)=1 und r(0.5)=0 und r(-0.5)=0 und (1.5)=2
ROUND_UNNECESSARY
Dieser Constraint ist im mathematischen Sinne nicht geeignet (oder nur mit hässlichen Verrenkungen), aber programmatisch können wir das: Wir nehmen r(x)=x und schmeißen eine Exception wenn nicht x\in N schon gilt.

Typischerweise denken wir im Dezimalsystem und dann wählen wir eine Zehnerpotenz 10^n mit n \in \Bbb N, also n \ge 0. Nun ist einfach
N = \{ x \in M : 10^n x \in \Bbb Z\},
also umgangsprachlich sind in N alle Zahlen aus M mit maximal n Stellen nach dem Komma. Diese Rundung funktioniert ganz gut mit so etwas wie LongDecimal in Ruby oder BigDecimal in Scala oder Java, wobei BigDecimal weniger Rundungsmodi anbietet als LongDecimal für Ruby.

Nun kommen wir zur Restklassenrundung. Wir gehen wieder von dieser Zehnerpotenz 10^n aus. Dann brauchen wir noch eine natürlich Zahl m \ge 2 und eine Menge von Resten R \subseteq \{0,...,m-1\}. Nun ist
N = \{ x \in M : 10^n x \in {\Bbb Z} \wedge \bigvee_{r \in R} 10^n x \equiv r \mod{m}\}.
Das bedeutet, wenn wir mit Nullen auf die angegebene Anzahl von Nachkommastellen auffüllen, das „Komma“ (normalerweise als „.“ geschrieben) weglassen und dann diese Zahl mit Rest durch m teilen, der dabei herauskommende Rest in R liegt.
In diesem Fall wird es mit dem ROUND_HALF_EVEN eventuell schwierig, da es undefiniert oder mehrdeutig werden kann. Aber wir müssen auch den Fall abdecken, dass die 0 nicht in R ist und Regeln angeben, wohin die 0 gerundet werden soll. Die Kandidaten sind hier mit selbsterklärenden Namen versehen:

  • ZERO_ROUND_TO_PLUS
  • ZERO_ROUND_TO_MINUS
  • ZERO_ROUND_TO_CLOSEST_PREFER_PLUS
  • ZERO_ROUND_TO_CLOSEST_PREFER_MINUS
  • ZERO_ROUND_UNNECESSARY

Ein wichtiger Anwendungsfall ist hier m=10 und R=\{0, 5\}. So kann man in der Schweiz Geldbeträge auf Vielfache von 5 Rappen (0.05 CHF) runden. Dies wurde in Rundung bei Geldbeträgen bereits genauer beschrieben.

Share Button

Quadrat- und Kubikwurzeln berechnen vor 30 Jahren und heute ;-)

Veröffentlicht am von
Antworten

Unsere Rechner können sehr viele Rechenoperationen schon auf der CPU erledigen, wenn es darum geht, mit den Standardtypen (z.b. double, dem gängigen 8-Byte-Fließkommaformat) zu rechnen. Das war gegen Anfang der 80er Jahre noch nicht so, da konnten typische CPUs nur gerade mit 8-Bit-Ganzzahlen addieren, subtrahieren und ein paar Bit-Operationen ausführen und doch ließ sich daraus alles aufbauen. Langzahladdition und -subtraktion waren trivial, Multiplikation und Division etwas schwieriger, aber noch gut machbar. Aber für die Quadratwurzeln musste man schon etwas genauer überlegen. Das mitgelieferte Basic konnte das für 5-Byte-Fließkommazahlen, aber das Verfahren war einfach nur dumm und langsam, den es wurde der Logarithmus genommen, halbiert und dann die Exponentialfuntion. Mathematisch völlig richtig, aber eben langsam und mit unnötigen Rundungsfehlern behaftet. Wer sich ein bisschen mit dem Thema auskennt, landet recht schnell bei dem Newton-Verfahren. Man schätzt die Quadratwurzel, z.B. von 2, dividiert 2 durch den Schätzwert und nimmt dann den Mittelwert von Schätzung und Quotient für die nächste Iteration. Zu offensichtlich, um es nicht so zu machen und in der Praxis auch ganz brauchbar. Es gibt aber ein Verfahren, wie man früher ähnlich wie die Division auch die Quadratwurzeln „handschriftlich“ berechnen konnte und dieses Verfahren lässt sich sehr gut verwenden, um eine Quadratwurzelberechnung zu schreiben. Hier ist eine Ruby-Implementierung, die von Ganzzahlen ausgeht:
Zu einer ganzen Zahl x \ge 0 werden ganze Zahlen r \ge 0 und s \ge 0 gesucht so dass x = r + s^2 und (s+1)^2 > x gilt.

  def check_is_int(x, name="x")
    raise TypeError, "#{name}=#{x.inspect} must be Integer" unless x.kind_of? Integer
  end

  #
  # helper method for internal use: checks if word_len is a reasonable
  # size for splitting a number into parts
  #
  def check_word_len(word_len, name="word_len")
    raise TypeError, "#{name} must be a positive number <= 1024" unless (word_len.kind_of? Fixnum) && word_len > 0 && word_len <= 1024
    word_len
  end

  #
  # split number (Integer) x into parts of word_len bits each such
  # that the concatenation of these parts as bit patterns is x
  # (the opposite of merge_from_words)
  #
  def split_to_words(x, word_len = 32)
    check_word_len(word_len)
    check_is_int(x, "x")
    m = x.abs
    s = (x <=> 0)
    bit_pattern = (1 << word_len) - 1
    words = []
    while (m != 0 || words.length == 0) do
      w = m & bit_pattern
      m = m >> word_len
      words.unshift(w)
    end
    if (s < 0) then
      words[0] = -words[0]
    end
    words
  end


  #
  # calculate the an integer s >= 0 and a remainder r >= 0 such that
  # x = s**2 + r and s**2 <= x < (s+1)**2
  # the wordwise algorithm is used, which works well for relatively
  # large values of x.  n defines the word size to be used for the
  # algorithm.  It is good to use half of the machine word, but the
  # algorithm would also work for other values.
  #
  def sqrtw_with_remainder(x, n = 16)
    check_is_int(x, "x")
    check_is_int(n, "n")

    n2 = n<<1
    n1 = n+1
    check_word_len(n2, "2*n")

    s = (x <=> 0)
    if (s == 0) then
      return [0, 0]
    elsif (s < 0)
      a = sqrtw_with_remainder(-x)
      return [ Complex(0, a[0]), a[1]]
    end

    xwords = split_to_words(x, n2)
    if (xwords.length == 1) then
      return sqrtb_with_remainder(xwords[0])
    end

    xi = (xwords[0] << n2) + xwords[1]
    a  = sqrtb_with_remainder(xi)
    yi = a[0]
    if (xwords.length <= 2) then
      return a
    end

    xi -= yi*yi
    2.upto(xwords.length-1) do |i|
      xi = (xi << n2) + xwords[i]
      d0 = (yi << n1)
      q  = (xi / d0).to_i
      q0 = q
      j  = 0
      was_negative = false
      while (true) do
        d = d0 + q
        r = xi - (q * d)
        break if (0 <= r && (r < d || was_negative))
        if (r < 0) then
          was_negative = true
          q = q-1
        else
          q = q+1
        end
        j += 1
        if (j > 10) then
          break
        end
      end
      xi = r
      yi = (yi << n) + q
    end
    return [ yi, xi ]
  end

  #
  # calculate an integer s >= 0 and a remainder r >= 0 such that
  # x = s**2 + r and s**2 <= x < (s+1)**2
  # the bitwise algorithm is used, which works well for relatively
  # small values of x.
  #
  def sqrtb_with_remainder(x)
    check_is_int(x, "x")

    s = (x <=> 0)
    if (s == 0) then
      return [0, 0]
    elsif (s < 0)
      a = sqrtb_with_remainder(-x)
      return [ Complex(0, a[0]), a[1]]
    end

    xwords = split_to_words(x, 2)
    xi = xwords[0] - 1
    yi = 1

    1.upto(xwords.length-1) do |i|
      xi = (xi << 2) + xwords[i]
      d0 = (yi << 2) + 1
      r  = xi - d0
      b  = 0
      if (r >= 0) then
        b  = 1
        xi = r
      end
      yi = (yi << 1) + b
    end
    return [yi, xi]
  end

Daraus lässt sich dann relativ einfach eine Quadratwurzelfunktion mit entsprechender Nachkommstellenberechnung bilden.

Witzerweise lässt sich das Verfahren auch für Kubikwurzeln sinngemäß anwenden.

Hier ein kleiner Test:

irb(main):138:0> sqrtw_with_remainder(2)
=> [1, 1]
irb(main):139:0> sqrtw_with_remainder(200)
=> [14, 4]
irb(main):140:0> sqrtw_with_remainder(20000)
=> [141, 119]
irb(main):141:0> sqrtw_with_remainder(2000000)
=> [1414, 604]
irb(main):142:0> sqrtw_with_remainder(200000000000000000000000000000000000000000000000000000000000)
=> [447213595499957939281834733746, 228299936041363866321288807484]
irb(main):143:0> sqrtw_with_remainder(2000000000000000000000000000000000000000000000000000000000000)
=> [1414213562373095048801688724209, 1974464361663955412145937324319]
irb(main):144:0> sqrtw_with_remainder(3000000000000000000000000000000000000000000000000000000000000)
=> [1732050807568877293527446341505, 3021967735564464902990914334975]
irb(main):145:0> sqrtw_with_remainder(3)
=> [1, 2]
irb(main):146:0> sqrtw_with_remainder(300)
=> [17, 11]
irb(main):147:0> sqrtw_with_remainder(30000)
=> [173, 71]
irb(main):148:0> sqrtw_with_remainder(3000000)
=> [1732, 176]
Share Button

Fließkommazahlen als Ersatz für Ganzzahlen

Veröffentlicht am von
Antworten

Wie ärgerlich ist eigentlich die Tatsache, dass Lua und JavaScript keine „int“s kennen und man stattdessen Fließkommazahlen („double“) verwenden muss?

Natürlich fühlt es sich völlig falsch an und ich möchte die Entscheidung, nur diese 8-byte-Fließkomma-Zahlen als numerischen Typ zu unterstützen, nicht gutheißen.

Aber was bedeutet das nun genau? Bekommen wir nun plötzlich irgendwo 7.999999999 statt 8?

Die Fließkommazahlen sind heute zum Glück standardisiert und fast jede Implementierung hält sich einigermaßen an diesen Standard. Es gibt eine 4-Byte-Variante und eine 8-Byte-Variante. Die 4-Byte-Variante ist nur dann sinnvoll, wenn man dem Entwickler die Wahl lässt, und fast jeder Entwickler nimmt „zur Sicherheit“ lieber die 8-Byte-Variante. Diese Fließkommazahl sieht nun ungefähr so aus:
1 Bit ist das Vorzeichen
11 Bits drücken den 2er-Exponenten aus
52 Bits drücken die Mantisse aus, dazu kommt als 53stes eine führende 1, die man nicht speichern muss, weil sie ja immer da ist.
Damit kann man die ganzen Zahlen von -2^{53} bis 2^{53} exakt ausdrücken und hat damit etwas, was etwa 54-Bit-Ganzzahlen entsprechen würde. Rein informationsmäßig ist das eine zusätzliche Bit im Vorzeichen und das andere im 2-er-Exponenten codiert. Wenn man also nur addiert, subtrahiert und multipliziert und dabei immer im Bereich von -2^{53} bis 2^{53} bleibt, kann man exakte Ergebnisse erwarten. Natürlich ist es langsamer, aber auch das ist bei heutigen CPUs, die schnelle Fließkommaoperationen seit etwa 20 Jahren standardmäßig (und vorher gegen Aufpreis) in der Hardware eingebaut haben, nicht so tragisch. Wie ist es mit den ungenutzten Bits? Normalerweise stören die nicht, aber wenn man Applikationen entwickelt, die sehr speicherintensiv sind, kann auch so etwa ausnahmsweise mal relevant werden.

Ärgerlicher ist da schon die Division. Hat man bei ints so etwas wie „/“ für die Division mit Abrundung und „%“ für den Rest, wird bei Fließkommazahlen mit „/“ wirklich dividiert und eine neue Fließkommazahl berechnet. Wie rundet man hier ab, um das „int-/“ und das „int-%“ zu bekommen? Es sollte dabei ja trotzdem noch das 6.9999999999999 zu 7 gerundet werden.

Ungefähr so etwas könnte funktionieren:

def divmodf(x, y)
xf = x.to_f
yf = y.to_f
df = if (yf < 0) then
-0.2
else
0.2
end
qf = (xf + df) / yf;
q = qf.floor
r = (yf*(qf-q)).round(0)
return q,r
end

Das ist jetzt in Ruby geschrieben, aber es würde natürlich ähnlich in Lua oder JavaScript funktionieren.

Share Button

Carry-Bit: Wie funktioniert das?

Veröffentlicht am von
4

English

Alle, die in der Grundschule noch das handschriftliche Addieren gelernt haben, kennen das Verfahren eigentlich. Es ist nichts anderes als das, nur nicht im Zehnersystem, auch nicht im Zweiersystem, sondern im 256er-System (8 Bit), 65536er-System (16 Bit), 4294967296er-System (32 Bit), 18446744073709551616er-System (64 Bit) oder was auch immer die Wortbreite der CPU ist. Dass man immer mit Zweierpotenzen arbeitet, ist heute üblich, aber es kann durchaus sein, dass man von unseren zweiwertigen Bits einmal auf dreiwertige „Trits“ wechselt, wenn sich die Hardware-Technologie weiterentwickelt. Wir werde es sehen.

Ich finde es zwar nicht sinnvoll, dass man sich bei der Applikationsentwicklung mit solchen Details auf Bit-Ebene herumschlagen muss, aber da man ja mit Java, C, C++, C# und ähnlichen Sprachen heute einen großen Teil der Applikationsentwicklung durchführt, kommt man daran nicht vorbei. Diese Sprachen zwingen den Entwickler, sich mit diesen Fragen zu einem gewissen Maße auseinanderzusetzen, um deren Darstellungen ganzer Zahlen zu verstehen. Aber das „Carry“-Bit sieht man leider in diesen Sprachen nicht, obwohl es für das Verständnis wichtig ist.

Ich habe mich seit etwa Anfang der 80er Jahre damit beschäftigt, Software zu erstellen. Die damals für mich zugänglichen Rechner waren 8-Bit-Rechner mit 6502 oder 6510 als CPU und 1 MHz Taktfrequenz. Man konnte sie in einem Basic-Dialekt programmieren, aber das war für viele Zwecke unbrauchbar, weil es zu langsam war. So kam Assemblersprache zum Einsatz. Ich habe dann später noch 680×0-Assembler und 80×86-Assembler verwendet, aber ab Mitte der 90er Jahre kam das eigentlich nicht mehr vor. Eine 8-Bit-CPU kann zwei 8-Bit-Zahlen miteinander addieren und dabei ein 8-Bit-Ergebnis liefern. Dabei gibt es zwei Varianten zu unterschieden, nämlich signierte Ganzzahlen, die meistens im Zweierkomplement dargestellt werden. Das bedeutet, dass das erste Bit das Vorzeichen codiert. Somit sind die Werte von 0 bis 127 postive Ganzzahlen, wie man es erwartet. Die 127 hat das Bit-Muster 01111111. Nun könnte man meinen, dass das Bitmuster 10000000 die direkt darauffolgende Zahl, also 128 ist, aber in Wirklichkeit ist das die -128, weil ja das erste Bit das Vorzeichen codiert und die „1“ für negatives Vorzeichen steht. Erhöht man die -128 weiter, erhöht sich der Zahlwert, weiter, wird also weniger negativ. Man hat dann am Schluss 11111111, um die -1 auszudrücken. Dieses etwas obskure Verhalten ist plausibel, wenn man sich vorstellt, nicht mit ganzen Zahlen zu rechnen, sondern mit Restklassen modulo 256. Dabei werden zwei Zahlen also kongruent, also zusammengehörig, angesehen, wenn sie sich nur um ein Vielfaches von 256 unterscheiden. Um alle 256 möglichen Restklassen abzudecken, kann man als Vertreter die Zahlen von 0 bis 255 (unsigned byte) oder von -128 bis 127 (signed byte, Zweierkomplement) verwenden. Beides kommt in unseren heutigen Programmiersprachen vor.

Für das Carry-Bit nehme ich zunächst der Einfachheit einmal an, dass wir nur mit nicht-negativen Zahlen rechnen. Die möglichen Werte eines Speicherworts sind also von 0 bis 2^n-1, wobei n die Wortbreite ist, also in unserem Beispiel 8. Heutige CPUs haben normalerweise 64bit Wortbreite, was nichts an der prinzipiellen Funktionisweise ändert, aber mit 8Bit ist das Beispiel übersichtlicher. Jeder kann sich vorstellen, wie sich das Prinzip auf 32 oder 64 oder 36 oder auch 96 Bit übertragen ließe.

Es steht also die Bitfolge 11111111 für 255. Nun kann man mit einem Assemblerbefehl, der oft ADD oder so ähnlich heißt, zwei solche Zahlen addieren. Das heißt, dass die Addition innerhalb der CPU als eine einzige Operation innerhalb von einem oder einigen wenigen Taktzyklen durchgeführt werden kann. Nun ergibt die Addition von zwei unsignierten 8-Bit-Zahlen eine Zahl zwischen 0 und 510 (111111110 binär), leider zu viel für ein Byte. Mit einem Bit mehr ließe sich das aber ausdrücken. So behilft man sich, indem man die niedrigen 8 Bit des Ergebnisses als Resultat akzeptiert, aber das neunte, oberste Bit, das nun 0 oder 1 sein kann, in einem sogenannten Carry-Bit oder Carry-Flag oder Übertragsbit in der CPU speichert. Dieses kann man nun abfragen und davon abhängig einen anderen Pfad einschlagen, zum Beispiel eine Fehlerbehandlung wegen eines Überlaufs auslösen, wenn die weiteren Verarbeitungsschritte nicht in der Lage sind, mehr als 8-Bit zu verwenden. Aber es gibt auch eine sehr elegante Lösung, die zum Zuge kommt, wenn man Zahlen addiert, die mehrere Bytes (oder CPU-Worte) breit sind. Ab der zweiten Addition verwendet man so etwas wie ADC („Add with Carry“). Dabei wird das Carrybit, das 0 oder 1 ist, als dritter Summand einbezogen. Damit ist das Ergebnis diesmal sogar zwischen 0 und 511 (111111111 binär). Wieder erhält man ein Carry-Bit. Man kann diese Addition nun fortfahren, bis man alle Bytes der Summanden verarbeitet hat. Wenn sie verschieden lang sind, kann man die oberen Bytes des kürzeren Summanden durch 0 ersetzen, solange das Carry-Bit noch 1 ist, oder ansonsten die Bytes des längeren Summanden einfach übernehmen. Um das Gesamtergebnis auszudrücken braucht man in diesem Fall eventuell ein Byte (oder CPU-Wort) mehr als der längere der beiden Summanden hat.

So lässt sich relativ einfach eine Langzahladdition in Assemblersprache schreiben. Es ist einer der größten Design-Fehler vieler heutiger Programmiersprachen, insbesondere von C, dass sie einerseits mit Low-Level-Ganzzahltypen ausgestattet sind, aber andererseits uns das Carry-Bit vorenthalten, so dass man dieses mit viel Gebastel ermitteln muss.

Die Subtraktion von Langzahlen funktioniert sehr ähnlich, dafür gibt es meist ein SBC („subtract with carry“) oder SBB („subtract with borrow“), je nachdem, wie das Carry-Bit bei der Subtraktion interpretiert wird.

Für die vorzeichenbehafteten Ganzzahlen muss man beim jeweils höchsten Byte der beiden Summanden aufpassen und hier das Vorzeichenbit berücksichtigen. Häufig gibt es ein sogenanntes Overflow-Bit, das in diesem Fall zumindest erkennen lässt, wann man ein weiteres Speicherwort benötigt.

Die 64-Bit-Addition heutiger CPUs könnte prinzipiell so funktionieren, dass sie bitweise nacheinander oder byteweise nacheinander mit Carry addiert. Mir sind die Implementierungsdetails von ARM, Intel und AMD zwar nicht bekannt, aber ich gehe davon aus, dass man dort eine größere Parallelisierung der Operation verwendet. Es gibt Algorithmen, die es so ermöglichen, eine Langzahladdition unter Verwendung von Parallelisierung wesentlich schneller auszuführen als mit dem hier beschriebenen Verfahren. Vielleicht schreibe ich dazu auch irgendwann einmal etwas, wenn es jemanden interessiert.

Interessant ist es auch, Multiplikation, Division, Quadratwurzel, Kubikwurzel und ähnliches zu berechnen. Auch damit habe ich Erfahrung, kann das also bei Interesse gerne beschreiben. Kurz gesagt sind diese Operationen auf heutigen CPUs sehr einfach in Assemblersprache zu implementieren, weil dort Multiplikation und Division bereits vorhanden sind, aber es geht auch mit 8-Bit-CPUs ohne Multiplikationsbefehl, falls das jemanden aus Nostalgiegründen interessieren sollte. Gerade für die Multiplikation gibt es aber wesentlich bessere Algorithmen, wenn die Faktoren sehr lang sind.

Ich möchte einen Artikel über die mögliche Ermittlung des Carrybits in C verfassen. Dieser wird auf Englisch erscheinen und unter der englischen Übersetzung dieses Artikels als Ping-Back verlinkt sein.

Share Button

Mathematische Formeln in WordPress

Veröffentlicht am von
1

English

In diesem Blog ist nun das Plugin WP QuickLaTeX installiert, das das \LaTeX-Rendering bei QuickLaTeX durchführen lässt.

Wenn eine Seite nur mit [{\sf latexpage}] beginnt, kann man Formeln mittels \backslash(\ldots\backslash) oder \backslash[\ldots\backslash] einbetten und in LaTeX-Notation formulieren.

Nun ist es möglich, in diesem Blog mathematische Formeln zu verwenden, z.B.:

    \[ \bigwedge_{z\in\Bbb C}\, \sin z = \sum_{k=0}^\infty \frac{(-1)^k z^{2k+1}}{(2k+1)!}=z-\frac{z^3}{6}+\frac{z^5}{120}-\frac{z^7}{5040}+\ldots \]

    \[ \bigwedge_{z\in\Bbb C}\, \cos z = \sum_{k=0}^\infty {\frac{(-1)^k z^{2k}}{(2k)!}}=1-\frac{z^2}{2}+\frac{z^4}{24}-\frac{z^6}{720}+\ldots \\ \]

    \[ {\bigwedge_\stackrel{z\in\Bbb C}{\cos z \ne 0}} \tan z = \frac{\sin z}{\cos z} \\ \]

    \[ {\bigwedge_\stackrel{z\in\Bbb C}{\sin z \ne 0}} \cot z = \frac{\cos z}{\sin z} \\ \]

    \[ {\bigwedge_\stackrel{z\in\Bbb C}{\cos z \ne 0}} \sec z = \frac{1}{\cos z} \\ \]

    \[ {\bigwedge_\stackrel{z\in\Bbb C}{\sin z \ne 0}} \csc z = \frac{1}{\sin z} \\ \end{align} \]

    \[ \sec(z) = 4\pi \, \sum_{k=0}^{\infty} \frac{(-1)^k(2k+1)} {(2k+1)^2 \pi^2 - 4 z^2 } \]

    \[ \csc(z) = \frac{1}{z} - 2z \, \sum_{k=1}^{\infty}\frac{(-1)^k} {k^2\pi^2-z^2} = \sum_{k=-\infty}^\infty \frac{(-1)^k \, z}{z^2-k^2\pi^2} \]

Ich werde also, wenn es sinnvoll ist, entsprechende mathematische Formeln damit schreiben und nicht mehr irgendwelches unübersichtliches ASCII-Gebastel dafür benutzen.

Warum benutzt man sowas nicht für Entwicklungsumgebungen von Programmiersprachen? Wenn eine Formel „steht“, könnte man sie viel schöner anzeigen als mit diesem Zeichensalat im Editor. Nun ja, ich glaube, Donald Knuth hat das vor einigen Jahrzehnten auch mal gemeint und dann das sogenannte „literate programming“ erfunden. Der Quelltext ist also eine Datei, aus der man mit weave und tangle (oder fweave und ftangle oder cweave und ctangle) einerseits eine .tex-Datei und andererseits eine kompilierbare nicht-literarische Quelltext-Datei generieren kann. So läßt sich für den Leser ein wunderschöner Ausdruck erzeugen und der Compiler baut das auführbare Programm. Eine kleine Spur dieser Ideen ist ja mit javadoc und rubydoc und perldoc verwirklicht worden, aber das mit den Formeln fehlt natürlich noch.

Share Button