Laufzeit Haltonsequenz



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

    LG



  • 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 O(logx)\mathcal{O}(\log x) ist, in der Praxis gute Laufzeiten hat.

    LG


Log in to reply