suche speziellen Randomgenerator

[mooncast]

Der Algorithmus soll jeder natürlichen Zahl einen Zufallswert zuordnen
so dass die Folge natürlicher Zahlen quasi weisses Rauschen mit reproduzierbarer Sequenz ergibt.

Dabei ausgeschlossen sind rekursive Methoden, Listen und Methoden die auf modulo
durch Sättigung / Overflow basieren, als zB n * m + k ohne explizites Modulo geht nicht,
ein Lookup der Ziffernfolge einer transzendenten Zahl auch nicht.

Der Grund dafür ist dass es
1. plattformunabhängig sein muss und das nicht überall geht
2. maximal 3 Operationen brauchen soll

Die Folge beginnt mit 0, zusätzlicher Offest Seed ist denkbar aber muss ohne gehen,
der Grund ist dass es nacher möglich sein soll per Seed beliebig in die Folge zu springen.

Die Sequenz kann begrenzt sein dh sich wiederholen, sollte aber mindestens 2^16 Werte in Folge haben.

Ich habs mit xor shifts versucht aber das funktioniert damit offenbar nicht so gut,
wenn die Bits nicht gefüllt sind und man das nicht rekursiv anwendet...

Zufällige Binärfolgen gehen auch nicht, bzw nur zur Not.

hat jemand ne Idee?

 

[einseinsnull]

mit reproduzierbarer Sequenz

Dabei ausgeschlossen sind rekursive Methoden

das dürfte einander tatsächlich ausschließen.

wenn es deterministisch sein soll, so wie bei rand() und seinen brüdern, dann ist das bereits mit einer form der rekursion verbunden.


16 bit int geht sicher auf jeder plattform, damit gibt es kein problem.

was spricht denn gegen echten zufall? CPU temperatur oder mausbewegung sind da dankbare lieferanten. jedenfalls für einzelne werte oder kleine gruppen davon.

zum verteilungsraum hast du garnichts gesagt.

 

[mooncast]

Die Anforderungen stehen im Eingangspost.

 

[mooncast]

Das Stichwort ist zählerbasierter Zufallsgenerator.

zB "Squares", kommt dem am nächsten, hat aber zuviele Operationen und basiert auf 64 Bit.

Ich kenn mich in der Materie aber zu wenig aus um zu entscheiden wie man
den am besten auf 32/16 bit runterbricht,
Ich kann natürlich naiv das Schema auf 32 / 16 Bit anwenden.

Aber es sind 25 Operationen pro Wert das ist zuviel, und wie man Overflow sicher verhindert weiss ich nicht, das geht in Faust auf Arm zB offenbar nicht.

 

[Orgel]

Schau mal hier: https://de.wikipedia.org/wiki/Blum-Blum-Shub-Generator

 

[mooncast]

geht in die richtige Richtung, ist halt rekursiv.
Squares kombiniert das ^2 mit xor shifts.

Leider ist es aber so dass man das nicht so lauenhaft wie ich abändern kann,
zb gehen mit 16 Bit nur 3 oder 4 3*Shift Varianten sinnvoll.

Ich werd das aber mal probieren,
n^2 und Shift

 

[mooncast]

er schlägt 4 3er Shift Triplets vor

16-Bit Xorshift Pseudorandom Numbers in Z80 Assembly

Xorshift is a simple, fast pseudorandom number generator developed by George Marsaglia. The generator combines three xorshift operations wh...

www.retroprogramming.com

Der Squares Algorithmus ist hier beschrieben:

[2004.06278] Squares: A Fast Counter-Based RNG

 

[mooncast]

also das funktioniert soweit,

x^2 + 12345
x^= x<<7
x^= x>>8
x^=x<<9

und Bitmaske auf dem Output.
allerdings ist das Problem dass x^2 zu gross wird. dh das geht nur in nem kleinen Bereich.
Dh man braucht noch ein Mod davor.

 

[einseinsnull]

Die Anforderungen stehen im Eingangspost.

einen randomgenerator ohne verteilungsraum gibt es nicht.

und zählen kannst du eigentlich alles, was man auch sonst irgendwie triggern kann, oder nicht? sonst könnte man z.b. kein audio signal daraus machen.

Ich kenn mich in der Materie aber zu wenig aus um zu entscheiden wie man
den am besten auf 32/16 bit runterbricht

wenn das zielformat int und dann auch noch signed ist, kannst du es vermutlich vergessen algos zu übersetzen, die tiefere float oder fixed bereiche benötigen. ich meine man könnte ja einfach die benutzen und dann runden, aber das führt natürlich dann zu fehlern in der verteilung, weil sich im schmlimmsten fall dann zwei gleiche werte direkt hintereinander befinden.

deine sonstigen anforderungen, z.b. unbedingt auf modulo oder clipping verzichten zu wollen, erscheinen merkwürdig.

mehr davon verstehen als du tu ich leider auch nicht, aber wenn ich raten müsste, dann würde ich wohl eher versuchen das irgendwie auf basis von irgendeinem random() zu machen, weil das dann bereits natürliche zahlen sind.

das ist halt leider so, wenn man irgendwas selbst erfindet, dann muss man auch sehen wie man es gebaut bekommt.

 

[2bit]

Die Sequenz kann begrenzt sein dh sich wiederholen, sollte aber mindestens 2^16 Werte in Folge haben.

Spricht was dagegen, ein entsprechend langes wav-File von weißem (rosa / braunem) Rauschen abzusamplen?

Audacity: Erzeugen -> Rauschen... -> Dauer (Samples auswählen: 2^16 = 65.536 oder mehr) -> Ok

Das resultierende File ist kleiner als 150 Kb.

 

[mooncast]

Ja, schrieb ich ja im Eingangspost dass das keine Option ist.
Die Methode oben jetzt ist auch an der Ober- und Unterkante was noch geht.
Memory Lookups sollen keine drin sein ausser lokal ein Sample Delay.
Eine längere Sequenz als 16 Bit wär einerseits wünschenswert, 16 Bit hat allerdings den Vorteil dass man mit 2*8 Bit jede Seed einstellen könnte.
Es sind mir auch noch zu viele Operationen. Aber darunter wird es kaum gehen.
Man könnte das ja mal CPU vergleichen, kann mir vorstellen dass das beides ca gleich schnell wäre, für den Lookup braucht man auch ne Bitmaske mindestens für jeden Wert und Sprünge, Interpolation bleibt gleich.

 

[verstaerker]

Ja, schrieb ich ja im Eingangspost dass das keine Option ist.

ich bin vermutlich zu blöd zu sehen wo das steht

 

[2bit]

Mich dünkt, dass hier ganz elementare Infos fehlen. Programmieren für Arduino Unos mit fast keinem Speicher und minimalster Rechenleistung oder so was.

 

[mooncast]

Doch. Wie ich schrieb funktioniert das Quadrieren mit 3 folgenden geeigneten Shifts tatsächlich für meine Zwecke.
2^16 Werte reichen mir auch.
Die Methode hat mir aber noch zu viele Operationen.
Leider versteh ich aber vieeeeel zu wenig davon um zu wissen wie man aus einer Methode eine maximal lange Periode rausholt.
Ich vermute nämlich dass man mit Qaudrieren und einem Hash schon genügend dekorellieren kann um aus aufeinander folgenden Zahlen Pseudozufall zu machen.

 

[Turing]

Sorry, ich hatte meinen vorigen Post gelöscht, um noch etwas ausführlicher zu schreiben.

Das Squares-Paper habe ich noch nicht gelesen, mir geht es hier erst einmal nur um den
verlinkten Xorshift-Algorithmus.

Dieser ist ja wie folgt definiert:

/* 16-bit xorshift PRNG */

unsigned xs = 1;

unsigned xorshift( )
{
    xs ^= xs << 7;
    xs ^= xs >> 9;
    xs ^= xs << 8;
    return xs;
}

Das ist ein typischer rekursiv definierter Pseudozufallszahlen-Generator.
Anders als bei hochwertigeren Algorithmen besteht sein interner Zustand
nicht aus mehreren Zahlenwerten, sondern nur aus der einen Zahl xs.
Die einzige Besonderheit ist, dass der interne Zustand xs hier 1:1 dem
letzten erzeugten Pseudozufalls-Zahlenwert entspricht.
Dies ermöglicht einen deterministischen "Wiedereinstieg" in die
Pseudozufallszahlen-Sequenz, indem man mit dem vorher erzeugten
Wert seedet.
Man setzt den Generator also auf den Zustand, den er hatte, bevor
der gewünschte nächste Wert erzeugt wurde.
Worauf ich hinaus möchte: Dasselbe kannst Du auch mit jedem anderen
Pseudozufallszahlen-Generator machen, wenn Du ihn mit der Möglichkeit
austattest, den internen Zustand abzufragen und für den gewünschten
Wiedereinstieg zu restaurieren (statt ihn nur mit einer einzelnen Zahl zu seeden).
Dann kannst Du den Generator danach aussuchen, dass er eine hinreichend
große Periodenlänge aufweist und effizient zu berechnen ist.
In der Praxis würdest Du bei Einsatz von Xorshift ja vermutlich auch nicht
den berechneten unsigned-Wert im nachfolgenden Programm nutzen,
sondern diesen in einen float umwandeln oder diesen auf einen gewünschten
Integer-Bereich begrenzen. D.h. Du hättest wahrscheinlich eh eine Trennung
in zwei Werte, wobei der zum Wiedereinstieg genutzte Wert der rohe
unsigned-Wert ist. Da können dann genausogut ein oder mehrere
andere Werte vorgehalten werden, die den internen Zustand des
Pseudozufallszahlen-Generators an diesem Punkt darstellen und
einen Wiedereinstieg ermöglichen.

Noch ein Bemerkung:
Eine Periodenlänge von 2^16 = 65536 ist wirklich niedrig.
Wenn Du z.B. bei einer Sample Rate von 48 kHz für jedes Sample
einen Wert ziehst, dann wiederholt sich die exakte Zahlenfolge ja
schon nach weniger als 1,4 Sekunden. Ob das so in Deiner Anwendung
vorkommt oder irrelevant ist, kann ich natürlich nicht beurteilen.
Außerdem: Xorshift oben ist auf "unsigned" definiert, das ist aber nicht
ein Typ fester Größe. xor und shifts könnten bei Werten unterschiedlicher
Bitbreite zu abweichenden Ergebnissen führen. Wenn die Lösung
plattformunabhängig werden soll, würde ich einen Typ mit fester
Bitbreite nehmen.

 

[mooncast]

Also, danke für den Post, aber tatsächlich ist das der Teil den ich weiß.

Ja, der original XOR Shift ist natürlich rekursiv.
Im Squares Paper geht es aber um Erzeugung von Pseudorandom aus einem Counter,
also bin nicht der einzige der das braucht.

Dort ist es auch kein xor shift sondern xor( >> or <<), dh die Bits werden
"in die Mitte geschoben", das ist wohl ein Middle Squares Algorithmus.

15 oder 16 Bit an Sequenzlänge ist wenig und das hört man natürlich,
aber für meinen Zweck ist das egal weil ich nur Ausschnitte habe die kürzer sind.

Eine längere Sequenz wär dennoch besser weil es mehr Stücke zur Auswahl gibt.

Ich hab jetzt experimentell x & 32767 , ^2 + 12345, xor (xor << 7 , xor >>3 ) & 32676


Und ja ich brauch dann Floats so dass die Skalierung noch dazu kommt.

Funktioniert, ist aber ein Zufallstreffer, geht aber auch ohne die Addition sogar.

Ich überleg auch ein paar weiterführende Rechnungen mit den Integern zu machen und erst am Schluss zu skalieren.

Sind jetzt 10 Operationen, die auf modernen CPUs glaub alle gleichschnell sind.
Ist mir immer noch ein bisschen zuviel.

Es geht mir unter anderem darum den Algorithmus möglichst Hardwareunabhängig
zu machen, und ohne Branches und ohne Tables.

Für ein kontinuierliches Noise würde ich auch einen rekursiven Algorithmus nehmen.

 

[Turing]

Inzwischen habe ich das Squares-Paper gelesen.

In der Verwendung eines zustandslosen Random-Number-Generators
mit Counter-Zugriff sehe ich auch ein paar Vorteile.
Man kann z.B. vorwärts in der Sequenz springen und an einer Stelle
neu einsteigen, an der man vorher nicht war.
(Oder: man kann an beliebiger alter Stelle erneut einsteigen, nicht nur bei
bestimmten markierten Stellen, an denen man sich den Zustand des
Random-Generators gemerkt hat).

Insofern tatsächlich ein interessanter neuer Ansatz.

Ein Problem sehe ich aber noch:
Auch bei Squares kommt es natürlich bei den Multiplikationen und
Additionen zu Überläufen.
Du schreibst aber eingangs, dass Überläufe im Algorithmus nicht
auftreten dürfen.
Kannst Du diese Einschränkung näher erläutern?
Wie kannst Du dann Squares verwenden?

Außerdem: Nicht nur die Plattform ändert sich ja evtl. (wenn ich an den
Einsatz eines Softsynths denke), sondern auch die Sample Rate.
Wenn Du bei einem Patch auf eine feste reproduzierbare Sequenz
von Zufallswerten setzt - inwiefern ist das Ergebnis dann noch
reproduzierbar oder auch nur ähnlich, wenn Du zu einer anderen
Sample Rate wechselst?

 

[Turing]

OK ich sehe noch einen immensen praktischen Vorteil des
Counter-basierten, zustandslosen Ansatzes
(das wird ja auch im Squares-Paper hervorgehoben):
Man kann die Zufallszahlen blockweise parallel berechnen,
ohne dabei (wie bei einer rekursiven Definition) davon
abzuhängen, die Vorgänger schon zu kennen.
Coole Sache!

 

[mooncast]

Ich hab Anfangs einen RNG in der Form x*gosse Zahl + Konstante verwendet und der ging nicht auf dem Tablet, (Snapdragon CPU).
ich hab angenommen dass das mit dem Überlauf zu tun hatte, kann aber auch andere Gründe gehabt haben.

Ich benutz ja grad nicht wirklich Squares sondern nur das x^2 davon und beschränke x mit Bitmaske auf 15 Bit. Gerechnet wird aber mit 32 Bit ( oder 64, weiss es gar nicht)

Deswegen geht das im Moment.

Ich mach das in Faust, und was ich u.a. mache ist bandlimitiertes gesynchtes Noise.
Für die Bandlimitierung brauch ich ja einzelne Werte, und nicht einen per Sample Stream aus Random.

Und für den Sync brauch ich auch den nächsten nach dem letzten und ersten Wert gleichzeitig.

In Faust ist sowas ziemlich schwierig, schwieriger als es aussieht wenn man sich das nur kurz anschaut.
Am einfachsten ist es tatsächlich den Randomwert von einem Counter/Index aus zu berechnen, und das dauernd, auch wenn er sich nicht ändert.
Dafür kommt das dann ohne Branches aus was für SIMD Vorteile hat,
Ist im Prinzip wie der Vorschlag mit Table oben, nur ohne Table.


Bandlimitierung mach ich auch etwas krude, ich blende mit ner S-Kurve zwischen Folgewerten, die ich dann beliebig oversamplet machen kann.
Ob das am Ende effektiver ist als mit 4 Werten und Interpolation hab ich noch nicht überprüft, je aufwändiger das Random desto eher ist es sinnvoll das so zu machen.
Die SKurve ist aber auch nicht umsonst, und es ist auch nicht Oberton und Aliasing frei.
Ich nehm im Moment nur ne Parabel. Ne etwas bessere Kurve wär auch nicht viel aufwändiger.
Den Übergang letztes und erstes Sample hab ich auch noch nicht sauber drin,
zur Not leg ich auf die Transition und kleines Fade Window das die Stelle auf 0 setzt.

 

[einseinsnull]

Spricht was dagegen, ein entsprechend langes wav-File von weißem (rosa / braunem) Rauschen abzusamplen?

wen du etwas benutzt, was jemand anderes gemacht hat, dann kennst du den algorithmus nicht. rosa rauschen basiert in einem system einem random(), möglicherwiese sogar auf dem eines processors, aber es gibt auch hundert andere random algorithmen.

In der Verwendung eines zustandslosen Random-Number-Generators
mit Counter-Zugriff sehe ich auch ein paar Vorteile.
Man kann z.B. vorwärts in der Sequenz springen und an einer Stelle
neu einsteigen, an der man vorher nicht war.

ich sehe den widerspruch zwischen "counter" und "lookup" - letzteres will er ja nicht verwenden - überhaupt nicht.

wie ich schon sagte, wenn es vom grunde her determistisch ist, ist es immer deterministisch.

und man kann die angelegenheit mit dem counter doch, wenn ja eh immer das gleiche rauskommt, ganz prima durch tables erreichen, und dann kann man noch ganz primaeeer ganz furchtbar viel rechenleistung sparen, weil da bloße mapping von 2 werten mit an sicherheit grenzender wahrscheinlichkeit weniger rechenleistung braucht, als jeden wert alle 13 millisekunden neu auszurechnen.


nur mal so als beispiel für dieses verfahren in der praxis... wenn du in max/msp regular expressions benutzt, dann speichert das regexp einfach alles, was jemals mit der instanz umgeformt wurde ab, und wenn du später nochmal das gleiche reinschickst, wird das ergebnis nicht mehr berechnet und formartiert, sondern nur noch gemappt, ergo aus einer hautspeicheradresse gelesen.

nicht anders macht man das bei filter funktionen, IIR, FIR, coeeffizienten ausrechnen... das macht man einmal, entscheidet sich für eine ausreichende auflösung des wertebereichs, und dann kann man es später von dort aus mappen wie man lustig ist, egal ob man hochzählt, auf der 17325 bleibt oder das teil wie auch immer ausliest.

auch rechnen die meisten prozessoren und programme nicht 3/5 live aus, wenn 5 eine konstante ist, sondern sie rechnen immer erst mal 1/5 aus, behalten sich das irgendwo, und multiplizieren damit später die 3, die dividert werden soll.


meines erachtens ist das daher eh der einzige weg, mit dem man eine reihe von zufalls- oder wasauchimmerfür-werten mit nur 3 cycles generieren kann, denn arithmetik und formatkonvertierungen sind logischweise viel teurer.

eine simple normalverteilung braucht ja schon je 1x cos, log und sqrt. das macht man nur a la minute wenn es nicht anders geht.

 

[mooncast]

"man" macht das keineswegs pauschal so.
Ich hab zwei Bitmasken - brauchst Du beim Speicherzugriff auch.
Zwei Bitshifts und drei XOR.
Die Shifts gehen möglicherweise in einem Takt, die xor vermutlich in 3.
Die Speicheradresse muss man auch erstmal zusammenbauen, dann holen.
usw.
Speicherzugriffe und Sprünge sind die Nadelöhren auf modernen Prozessoren.
Nicht Rechnungen usw von denen die einfachen inkl. Mult in 3 Takten gehen
und die zusätzlich per SIMD vektorisiert werden können.

Der Speicherzugtiff bremst das aus. Man kann nicht 4 fach gleichzeitig den Speicher anspringen, und Du kannst die Adresse auch nicht preemptiv berechnen.

Und auf ganz anderen Plattformen wie FPGAs profitiert man auch davon wenn
der Code ausgerollt abgearbeitet werdrn kann.

 

[einseinsnull]

also speicheradressen erst berechnen zu müssen ist ein verfahren, das nicht kenne. eigentlich ist der witz an speicheradressen ja, dass man sie kennt.

aber dass das ganze grenzen hat ist schon klar. deswegen sage ich ja auch "wenn es nicht anders geht".

um rauszufinden, was effektiver ist, würdest du es natürlich für jeden einzelfall ausprobieren müssen.

Man kann nicht 4 fach gleichzeitig den Speicher anspringen

naja, das macht jede datenbank und auch jeder echo effekt. aber ich unterschätze vermutlich wie klein deine bausteine sind, dass du es umgekehrt priorisierst und speicherzugriff erst mal vermeiden willst wo es geht.

 

[Cyclotron]

Speicherzugriffe und Sprünge sind die Nadelöhren auf modernen Prozessoren.
Nicht Rechnungen usw von denen die einfachen inkl. Mult in 3 Takten gehen
und die zusätzlich per SIMD vektorisiert werden können.

Der Speicherzugtiff bremst das aus. Man kann nicht 4 fach gleichzeitig den Speicher anspringen, und Du kannst die Adresse auch nicht preemptiv berechnen.

naja, das macht jede datenbank und auch jeder echo effekt.

Mit einem einzigen SIMD Befehl geht das nur, wenn die Daten direkt aufeinander folgen. Wenn dem nicht so ist und man die Daten auch nicht entsprechend sortiert speichern kann, musst Du SIMD verlassen und das ganze in einer Loop machen. D.h. aus dem Register in ein Array speichern und dann das Array abarbeiten. Das bremst ungemein. Bei umfangreicheren Algorithmen kann das alles immer noch um den Faktor ~2 schneller sein, wenn man alles bis zum Lookup in SIMD macht. Aber im aktuellen Fall würde der Overhead das ganze wohl eher langsamer machen als die skalare Version, schätze ich mal.

 

[einseinsnull]

meine idee dabei ist einfach, dass man im regelfall bei der bearbeitung von audiosignalen eher an die leistungsgrenzen seiner CPU kommt als an die seines hauptspeichers. dass letzterer insgesamt langsamer ist steht da auf einem anderen blatt.

seinen konkreten anwendungsfall habe ich weder 100% verstanden noch hätte ich irgendwelche erfahrung mit seiner plattform. aber wenn ich in max oder c++ bei dingen wie biquad coeffs oder equal power panning die live ausgerechnete version gegen die bufferbasierte vergleiche, gewinnt die RAM fraktion haushoch.
und wie oben schon diskutiert, lesen dann natürlich alle 100 filter gleichzeitig aus ein und dem selben buffer. d.h. es wird genau 1 namespace / adresse dafür erzeugt und hundertausende von werten passen in einen einstelligen megabyte bereich.


aber zugegeben, bei rauschen hat man noch ein paar andere probleme.

zum ersten will man gar nicht, dass die alle identisch sind(!, und zum anderen bräuchte man ja wenn es seeds gibt mindestens mal zwei buffer, unter umständen sogar einen für jeden seed. dann ist natürlich schicht im schacht.

die wichtigste frage wäre wohl wieviele seiner randomgeneratoren er laufen lassen möchte und was währenddessen sonst noch von prozessor mit und ohne speichergeschichten geleistet werden soll.

aber dazu müsste man das ziel kennen. beim thema "bandlimited" fällt mir z.b. sofort der random walk ein, der man gerne mit einer markov chain baut. state/transition ist dann auch wieder ein buffer im speicher... bzw. im falle von signalen auch mal 3 oder 4.


die ideale implementation für so etwas würde nebenbei bemerkt einfach beide modi bieten, und sich anhand der systemauslastung oder der architektur automatisch anpassen.

das thema ist mir bei envelopes schon begegnet, wo ich es sogar dem user überlasse ob er die komplexe berechung von allen punkten aus live in signalrate modulieren will - und wenn nicht, dann wird die hüllkurve in den speicher geschrieben, von dor nur noch ausgelesen und der ganze andere quatsch ausgeschaltet.

diese wie-mache-ich-was-und-warum ebene sollte beim design nicht unterschätzt werden und ist manchmal ganz gut dazu geignet, mathematik-probleme einfach zu umgehen, die man mal wieder nicht hinbekommt weil einem dazu das mathestudium fehlt.

 

[2bit]

wen du etwas benutzt, was jemand anderes gemacht hat, dann kennst du den algorithmus nicht.

Dann schaut man halt nach? Audacity ist quelloffen:

audacity/Noise.h at master · audacity/audacity

Audio Editor . Contribute to audacity/audacity development by creating an account on GitHub.

github.com

audacity/Noise.cpp at master · audacity/audacity

Audio Editor . Contribute to audacity/audacity development by creating an account on GitHub.

github.com

 

[Turing]

ich sehe den widerspruch zwischen "counter" und "lookup" - letzteres will er ja nicht verwenden - überhaupt nicht.

Ein Lookup ist natürlich auch counter-basiert, benötigt aber
ausreichend viel Speicher für das Array der vorberechneten
Werte.
Bei 16 Bit Wortbreite mit nur 65536 Werten sollte das kein Problem
darstellen.
Aber will man bei 32 Bit Wortbreite wirklich die 4,294,967,296
Werte vorberechnen, um einen rekursiv definierten RNG
counter-basiert nutzen zu können?
Bei 64 Bit wird das dann komplett aussichtslos.
Ob man den counter-basierten Zugriff für eine Anwendung
überhaupt braucht, ist eine andere Frage.

 

[Turing]

und man kann die angelegenheit mit dem counter doch, wenn ja eh immer das gleiche rauskommt, ganz prima durch tables erreichen, und dann kann man noch ganz primaeeer ganz furchtbar viel rechenleistung sparen, weil da bloße mapping von 2 werten mit an sicherheit grenzender wahrscheinlichkeit weniger rechenleistung braucht, als jeden wert alle 13 millisekunden neu auszurechnen.

Wo kommen die 13 ms her?
Im Squared-Paper wurden 741 Mio Werte/Sekunde berechnet.
Der Zeitaufaufwand, um mit dem Squared-Algorithmus z.B. 44100 Pseudozufalls-Samples
(als float) zu berechnen, beträgt somit 0,06 ms, das wirkt auf mich tolerabel.
Aber grundsätzlich hast Du natürlich recht, Dinge wie cos, log, oder atan
würde man immer aus vorberechneten Tables interpolieren und nie in
Echtzeit berechnen wollen.

 

[mooncast]

Für Sin und Cos nutze ich Bhaskara I.
Dh Cos, aus dem ich Sin mache, Cos ist dann plus Offset.
Das ganze läuft auf glaube ich 3 oder 4 Mults und Add raus.
Damit kann man noch keine Tabelle linear interpoliert auslesen und es läuft komplett in SIMD.
Und der Rauschabstand ist glaub so - 80 in dB wobei alle Fehler Harmonisch sind.
Das muss man mit Table erstmal erreichen.
Der Range ist normalisiert auf 2Pi =1, damit kann man die Phase mit 1 Add, 1 Cast oder Floor(+0.5) realisieren.
Das geht bei Table Lookup auch nicht gut weil man mit der Tablegröße multiplizieren muss, bei zB 65k Werten wird das zu ungenau. Dh auch hier ist die Berechnung deutlich schneller als eine Tabelle.

 

[Turing]

Ja mag sein, dass es für die Standard-Funktionen auch gute polynomiale
oder gebrochenrationale Approximationen gibt.
Lookup Tables sind eben universell nutzbar, können eine beliebige Genauigkeit
erreichen und müssen ja auch nicht zwingend linear interpolieren.
Für mich überwiegen daher die praktischen Vorteile der Nutzung von
Lookup Tables, da ich mich eh mit Wavetables rumschlage und gut
implementierte Lookup Tables brauche.
Die Bhaskara-Approximation wäre mir zu ungenau.
Ich nutze JUCE und könnte stattdessen die dort bereitgestellte schnelle
sin-Approximation nutzen.
Deinen Post nehme ich zum Anlass, hier mal tatsächlich einen
Genauigkeitsvergleich zu machen, um zu sehen, ab welcher
Table-Größe sich der Aufwand von der Genauigkeit her überhaupt
lohnt.

 

[mooncast]

also speicheradressen erst berechnen zu müssen ist ein verfahren, das nicht kenne.

Also das glaube ich sofort. Das merkt man an Deinen Posts...

Ich versuch es hier aber nochmal:
Der Wert für zB den Sinus liegt irgendwo im Speicher. Und zwar in mindestens zwei Werten die interpoliert werden müssen.
Um den zu lesen, musst Du erstmal einen relativen Pointer zum ersten Wert berechnen, das ist schon mal aufwändiger als die normalisierte Phase.
Dann muss der Pointer zum Tabellenanfang geholt werden, addiert werden, und inkrementiert werden für den zweiten Wert (mindestens).
Dann musst Du mindestens eine Bitmaske drauflegen um nicht ausserhalb zu lesen.
Dann musst Du den ersten Wert lesen.
Blöd, wenn eine andere Stimme das auch grad will, was bei SIMD bis zu dem Punkt ja die Regel ist. Geht dann halt nicht sofort. Dann musst Du den zweiten Wert holen. Dann den Wert für die Interpolation bestimmen (bzw vorher). Dann interpolieren.
Die lineare Interpolation alleine kostet mindestens 3 zusätzliche Rechenschritte, ohne den Interpolationswert, der ebenfalls ein paar braucht.
Dh Du hast an zusätzlichem Aufwand den Pointer, den Interpolationswert, den Speicherzugriff und die Interpolation.