(Semi)Komplexe Formel mit intenger berechnen

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo. Bin jetzt schon zwei Tage am grübeln, also wende ich mich mal an euch.

Ich schreibe zurzeit ein Programm für ein ziemlich limitiertes System. Nativ kann es nur Integerberechnung und keine Floats. Es gibt aber die Möglichkeit doubles zu benutzen.

Die Formel die ich gerne hätte wäre:

a/b^c \quad N/R^N

Zwei von drei sind Konstante … also eigentlich mit Beispielnummern.

64/1.01^x

Die Schwierigkeit bei dieser Formel liegt daran das „x“ von Null bis mehrere Tausend schwanken kann und da das „x“ die Potenz bestimmt schon bei kleinen zahlen auch bei einer ulong schnell der Range überschritten ist.
Als erstes muss natürlich die Reele Zahl in einen integer gewandelt werden z.b: 101. Es gibt keine grossen Genauigkeitsanforderungen.

Zwei Umgangslösungen die ich mir schon überlegt habe.
1: Eine Formel finden die eine ähnliche Kurve liefert aber keine variable Potenz hat. Muss nur von der Form ähneln. Wurde noch nicht fündig.
2: Eine Art float zu emulieren. Wäre aber langsam.

Hat jemand einen Tipp?

#2

Hallo.
ich denke, das Problem hättest du besser im
Mathebrett gepostet.

Die Formel die ich gerne hätte wäre:

a/b^c \quad N/R^N

Zwei von drei sind Konstante … also eigentlich mit
Beispielnummern.

64/1.01^x

Die Schwierigkeit bei dieser Formel liegt daran das „x“ von
Null bis mehrere Tausend schwanken kann und da das „x“ die
Potenz bestimmt schon bei kleinen zahlen auch bei einer ulong
schnell der Range überschritten ist.
Als erstes muss natürlich die Reele Zahl in einen integer
gewandelt werden z.b: 101. Es gibt keine grossen
Genauigkeitsanforderungen.
Zwei Umgangslösungen die ich mir schon überlegt habe.
1: Eine Formel finden die eine ähnliche Kurve liefert aber
keine variable Potenz hat. Muss nur von der Form ähneln. Wurde
noch nicht fündig.
2: Eine Art float zu emulieren. Wäre aber langsam.
Hat jemand einen Tipp?

Wenn ich mit meiner laienhaften Mathekenntnissen
mal spekulieren darf:

Wie wäre es, mit Logarithmen zu rechnen, anstatt
im originalen Zahlenbereich. Das dürfte die Sache
mit der Rechnung deutlich vereinfachen, oder?
Die Umsetzung und Rückübersetzung kannst du z.B.
mit Tabellen und Interpolationen machen.
Gruß Uwi

#3

Hi,

was meinst Du mit „doubles benutzen“?

Was Dir vorschwebt, ist eine Art Fixpunktarithmetik.

Ist x immer ganzzahlig? Dann kannst Du mit der „Bauernmultiplikation“ optimal schnell Potenzen bestimmen.

Auch sonst kannst Du von x Zweierpotenzen abspalten, bis x sehr klein ist, danach eine Taylorentwicklung für die Potenz benutzen und den jeden Faktor Zwei in der Potenz durch einmal Quadrieren ausgleichen.

Gruß, Lutz

#4

was meinst Du mit „doubles benutzen“?

Mein System ist ein Forth System. Es speichert Zahlen in 16 Bit „Zellen“. Nun gibt es die Möglichkeit zwei solcher Zellen hintereinander zu benutzen und somit 32 Bit. Benutzen heisst das man mit doubles auch multiplizieren und dividieren kann.

Ist x immer ganzzahlig? Dann kannst Du mit der
„Bauernmultiplikation“ optimal schnell Potenzen bestimmen.

Wie Ich mit den „R“ und „N“ zeigen wollte ist x tatsächlich nur ganzzahlig und nur positiv.

Auch sonst kannst Du von x Zweierpotenzen abspalten, bis x
sehr klein ist, danach eine Taylorentwicklung für die Potenz
benutzen und den jeden Faktor Zwei in der Potenz durch einmal
Quadrieren ausgleichen.

Ich schau mir mal diese Techniken an. Kenne sie noch nicht. Danke für die Antwort. Werde es in den nächsten Tagen weiterversuchen.

#5

Java in frühen Versionen hatte ähnliche Einschränkungen in der Basisversion. Daraus entstand der folgende Artikel

http://today.java.net/pub/a/today/2007/11/06/creatin…

Sicher noch keine vollständige Lösung, aber mehrere einfache Approximationen.

Gruß, Lutz

#6

Hallo.

Die Formel die ich gerne hätte wäre:

a/b^c \quad N/R^N

So wie du unten schreibst, sind a und b konstant, nur c variabel.

Wenn ich mal von deinem Beispiel ausgehe:
64/1.01^x

Dann würde ich das umformen in
64 * 100^x / 101^x

Also so umwandeln, dass du nur noch natürliche Zahlen hast. Somit hast du nur noch eine Integer-Multiplikation und -Division. Problem ist allerdings wenn 64*100^x zu einem Überlauf führt.
Dazu würde ich dann das größte x bestimmen, das noch zu keinem Überlauf führt. Das nenne ich mal x_max.
Dann kann man die Formel so umstellen:

(64 * 100^x_max / 101^x_max)^(x/x_max) * 100^(x%x_max) / 101^(x%x_max).

Wobei dann / für die ganzzahlige Division steht und % für die Modulo-Operation. x_max ist ebenfalls konstant, ist aber natürlich für jedes Paar (a, b) neu zu berechnen. Du musst natürlich da auch nicht das Maximum nehmen, sondern kannst einen beliebigen kleineren Wert nehmen, z.B. die nächstkleinere 2er Potenz, damit x%x_max und x/x_max schneller zu berechnen sind.

Ich hoffe, der Ansatz hilft dir weiter.

Sebastian.

#7

Nochmal in Java, eine Berechnung von pow(x,y) mit den Einschränkungen von J2ME, also kein Math.pow, Math.exp, Math.log. Die Beispiele in den Links von mir sind leider grausam realisiert.

Voraussetzung ist die Quadratwurzel sqrt für das double-Format, notfalls mit Heron-Formel zu approximieren, oder mit der Integer-Wurzel, falls vorhanden:

Viel Erfolg, Lutz

class SqrtPow{

 static double sqrtpow(double x, double y){
 double pow=1;
 if(y0){
 if(n%2==1) pow\*=xx;
 n/=2; xx\*=xx;
 }
 if(y1e-8){
 x=Math.sqrt(x);
 y\*=2;
 if(y\>1){y-=1; pow\*=x;}
 }
 return pow;
 }

 static public void main(String... args){
 for(double y=-1; y