AG von zur Gathen - Algorithmische Mathematik

Maple Tip 1

Im Baby-Riesen-Schritt-Algorithmus legt man eine Tabelle an, in der zu xgj der diskrete Logarithmus j gespeichert ist.  Später möchte man in dieser Tabelle ein Gruppenelement gi2^m in dieser Tabelle finden.  Dazu muß man die Tabelle durchsuchen.  Eine Möglichkeit, das schnell zu tun, ist, die Tabelle zu sortieren und später mit binärer Suche die Einträge zu finden.  Maple gibt uns aber eine noch effizientere Methode, die zudem auf sehr maschinennahe Weise implementiert ist. Das folgende Beispiel nutzt eine besondere Eigenschaft von Maple dazu aus, nämlich die Option remember für Prozeduren.  Eine Prozedur mit dieser Option sieht, wenn sie aufgerufen wird, zuerst nach, ob sie schon einmal mit den gleichen Argumenten aufgerufen wurde.  Falls ja, wird der beim letzten Mal berechnete Wert ausgegeben.  Ansonsten wird die Prozedur ganz gewöhnlich abgearbeitet, allerdings werden danach Argument und Ergebnis notiert (fürs nächste Mal ...). 
beispiel:=

proc(a)
  local t;
  t:=proc(g) option remember; FAIL; end; # Definition
  g:=a;
  for j to 99999 do
    g:=g * g0;
    t(g):=j;                             # Eintrag
  od;
  g1:=g0^100000;
  g:=1;
  for i do
    j:=t(g);                             # Abruf
    if not j=FAIL then break; fi;
    g:=g * g1;
  od;
end;
Hier wird die lokale Variable t verwendet, um die Tabelle zu verwalten.  In der Zeile Definition wird t als eine Prozedur definiert, die immer FAIL antwortet.  In der Zeile Eintrag wird der Funktion künstlich ein Eintrag in ihre remember Tabelle geschrieben.  Wird t danach mit dem Wert g aufgerufen, so antwortet sie nicht mit FAIL, sondern mit dem Eintrag aus der remember Tabelle, also mit j.  Und genau so wird t dann in der Zeile Abruf verwendet.  Wurde der dortige Wert von g vorher eingetragen, so liefert t den Wert j, der zuvor eingetragen wurde.  Ansonsten liefert t den Wert FAIL, was in unserem Fall bedeutet, daß g nicht in der Tabelle steht.
Außer der Maschinennähe gibt es noch einen weiteren Grund, warum das schneller ist als die obige Methode.  Maple verwendet nämlich zusätzlich Hashverfahren.

Author: Michael Nöcker / Michael Nüsken, last change: 1 December 1998