Laufzeit Haltonsequenz

[quatschmitsosse]

Gegeben sei ein Bruch $\frac{q}{p^n}$, wobei $1 \leq n \in \mathbb{N}$, $0 < q < p^n$ und $p \in \mathbb{P}$ gölten. Gibt es einen Algorithmus zur Bestimmung des nächsten Elements in der entsprechenden Halton-Sequenz in $\mathcal{O}(1)$? Wenn ja, wie? Habe auf Google nichts Entsprechendes gefunden.

LG

[quatschmitsosse]

Ich meinte die Van-der-Corput-Folge, die die Grundlage der Halton-Folge bildet. Mein Fehler, sorry.

Das Problem hat sich inzwischen gelöst. Ich habe nun einen knackigen Algorithmus implementiert, der, obwohl er in $\mathcal{O}(\log x)$ ist, in der Praxis gute Laufzeiten hat.

LG