Re: Berechnen von Zahlen mit Hilfe großer int-Arrays

[Helmut Schellong]

On 04/07/2023 20:51, Walter H. wrote:
> Hallo,
>
> gibt ja die eine od. andere lange Zahl, welche so berechnet wird;
> die bekannteste ist Pi, bereits auf Mrd. von Stellen
>
> ich würd geren eine andere Zahl berechnen: die Basis des nat. Logarithmus
> e = 2.71828182...
>
> gibt es hier etwas besseres (schnelleres) als das
>
> e = 1 + 1/1! + 1/2! + ...
>

Ich meine, schneller geht es generell bei Reihen nur durch vorherige Berechnung von Konstanten - Teilresultate.
Die Vorberechnung von Fakultäten! geht auch fortlaufend, indem mit 2 3 4 5 ... multipliziert wird.


--
Mit freundlichen Grüßen
Helmut Schellong v...@schellong.biz
http://www.schellong.de/c.htm http://www.schellong.de/c2x.htm http://www.schellong.de/c_padding_bits.htm
http://www.schellong.de/htm/bishmnk.htm http://www.schellong.de/htm/rpar.bish.html http://www.schellong.de/htm/sieger.bish.html
http://www.schellong.de/htm/audio_proj.htm http://www.schellong.de/htm/audio_unsinn.htm http://www.schellong.de/htm/tuner.htm
http://www.schellong.de/htm/string.htm http://www.schellong.de/htm/string.c.html http://www.schellong.de/htm/deutsche_bahn.htm
http://www.schellong.de/htm/schaltungen.htm http://www.schellong.de/htm/math87.htm http://www.schellong.de/htm/dragon.c.html

[Thomas Koenig]

Walter H. <Walter...@mathemainzel.info> schrieb:

> Hallo,
>
> gibt ja die eine od. andere lange Zahl, welche so berechnet wird;
> die bekannteste ist Pi, bereits auf Mrd. von Stellen
>
> ich würd geren eine andere Zahl berechnen: die Basis des nat. Logarithmus
> e = 2.71828182...

Ich vermute mal, du meinst Floating-Point-Zahlen mit gegenüber den
Standardtypen von C erhöhten Genauigkeit (sonst könntest du einfach
M_E aus math.h verwenden.

mpfr hat das als Konstante gleich mit dabei, schneller kriegst du das
vermutlich nur mit großem Aufwand hin.

> gibt es hier etwas besseres (schnelleres) als das

> e = 1 + 1/1! + 1/2! + ...

Die Formel konvergiert schon ziemlich schnell.
Kettenbrüche könnten eine Alternative sein, siehe
https://mathepedia.de/Kettenbrueche.html .

[Helmut Schellong]

On 04/08/2023 06:36, Walter H. wrote:

> On 07.04.2023 21:44, Helmut Schellong wrote:
>> On 04/07/2023 20:51, Walter H. wrote:
>>> Hallo,
>>>
>>> gibt ja die eine od. andere lange Zahl, welche so berechnet wird;
>>> die bekannteste ist Pi, bereits auf Mrd. von Stellen
>>>
>>> ich würd geren eine andere Zahl berechnen: die Basis des nat. Logarithmus
>>> e = 2.71828182...
>>>
>>> gibt es hier etwas besseres (schnelleres) als das
>>>
>>> e = 1 + 1/1! + 1/2! + ...
>>>
>>
>> Ich meine, schneller geht es generell  bei Reihen nur durch vorherige Berechnung von Konstanten - Teilresultate.
>

> wie soll das schneller gehen ...
>
> ob man vorher sich der Reihe nach die 1/n! bestimmt und diese dann alle aufsummiert, oder ob man jeder Addition von 1/n! das nächste 1/(n+1)! [mit Hilfe von 1/n!] bestimmt macht ja keinen Unterschied;

Ich berechne alle n! _einmal_ im voraus und packe sie in ein const-Array.
Dieses Array kann für viele Reihen benutzt werden, ohne n! jemals wieder berechnen zu müssen.
Das ist doch primitiv und ewig bekannt.

[Helmut Schellong]

On 04/08/2023 19:37, Walter H. wrote:

> On 08.04.2023 17:41, Helmut Schellong wrote:
>> On 04/08/2023 06:36, Walter H. wrote:
>>>
>>> ob man vorher sich der Reihe nach die 1/n! bestimmt und diese dann alle aufsummiert, oder ob man jeder Addition von 1/n! das nächste 1/(n+1)! [mit Hilfe von 1/n!] bestimmt macht ja keinen Unterschied;
>>
>> Ich berechne alle n! _einmal_ im voraus und packe sie in ein const-Array.
>

> das kann man machen, wenn es sich um 'wenige' Stellen handelt;
> hier gehts nebenbei um 1/n!, da sieht die Welt etwas anders aus, weil da brauchst dann die Werte mit sovielen Dezimalstellen [entspr. Array je 1/n!-Wert] wie in meinem Fall ich e berechnen will; das kann dann den vorhanden Speicher etwas gröber übersteigen;
> bei nur 1 Mio Stellen würde dies bedeuten,
> du brauchst 207 500 mal rund 55 kBytes - is a bissi viel ;-)

>
>> Dieses Array kann für viele Reihen benutzt werden, ohne n! jemals wieder berechnen zu müssen.
>

> ja wenn dabei der Speicher nicht explodiert;
>
> 100 000 Stellen ist etwas f. gut 2 Sekunden;
> interessant wird es ab 25 Mio. od. mehr Stellen;
>

Ich verstehe Dich überhaupt nicht!
long double const fak_array[1750]= { ... };
Wo ist das Problem?

[Claus Reibenstein]

Helmut Schellong schrieb am 08.04.2023 um 22:19:

> On 04/08/2023 19:37, Walter H. wrote:
>
>> interessant wird es ab 25 Mio. od. mehr Stellen;
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

> Ich verstehe Dich überhaupt nicht!
> long double const fak_array[1750]= { ... };
> Wo ist das Problem?

Ich hab's Dir oben unterstrichen.

Gruß
Claus

[Claus Reibenstein]

Walter H. schrieb am 09.04.2023 um 09:50:

> While trying to retrieve the URL: https://www.mpfr.org/*
>
> [...]
>
> SSL Certificate expired on: Apr 7 23:59:59 2023 GMT

Diesen Fehler solltest Du dem Betreiber mitteilen. Wahrscheinlich hat
der einfach nur vergessen, sein Zertifikat rechtzeitig zu aktualisieren.

Gruß
Claus

[Bonita Montero]

Am 08.04.2023 um 22:19 schrieb Helmut Schellong:

> Ich verstehe Dich überhaupt nicht!
>     long double const fak_array[1750]= { ... };
> Wo ist das Problem?

Da einen FP-Wert zu nehmen ist unsinnig, denn die Zahl ist eh ganz-
zahlig. Da könnte man auch direkt einen uint64_t nehmen. Aber das
Problem an der Stelle ist, dass man dazu sicher nicht 1750 Werte
bräuchte, sondern genau 21 bzw. darüber hinaus passt der Wert nicht
mehr in das Array; d.h. für so ein Problem bräuchte man eine Big-
num-Libary die derart große Werte exakt speichern kann, aber ich
bezweifel, dass 1750 verschiedene Fakultäten in den Arbeitsspeicher
irgendeines heutigen Rechners passen würden.

[Bonita Montero]

Am 07.04.2023 um 20:51 schrieb Walter H.:

> ich würd geren eine andere Zahl berechnen: die Basis des nat. Logarithmus
> e = 2.71828182...
> gibt es hier etwas besseres (schnelleres) als das
> e = 1 + 1/1! + 1/2! + ...

Ich nehm mal an, dass 1 / n! so schnell so klein wird, dass es
repräsentierbar Null ergibt ehe deine Fakultät explodiert, dass
die einen FP-Überlauf ergibt.
Aber solltest Du FP-Zahlen verwenden, dann müsstest Du um mög-
lichst exakt zu bleiben für die 1/N! ein Array bilden dass vor
0.0 endet und vom kleinsten Wert ausgehend fortlaufend addiert,
dass Du die maximale Präzision hast.
Ich hab das mal in C++20 geschrieben; in C ginge es dann analog:

#include <iostream>
#include <vector>
#include <numeric>
#include <numbers>

using namespace std;

int main()
{
cout << "C++'s e:" << hexfloat << numbers::e_v<double> << endl;
for( int reverse = 1; reverse >= 0; --reverse )
{
vector<double> recFacts;
recFacts.reserve( 200 );
double f = 1.0;
for( int i = 1; 1.0 / (f *= i); ++i )
recFacts.emplace_back( 1.0 / f );
double e;
if( reverse )
e = accumulate( recFacts.crbegin(), recFacts.crend(), 0.0 ) + 1.0;
else
e = 1.0 + accumulate( recFacts.cbegin(), recFacts.cend(), 0.0 );
cout << (reverse ? "reverse: " : "forward: ") << e << endl;
}
}

Das gibt bei mir aus:

C++'s e:0x1.5bf0a8b145769p+1
reverse: 0x1.5bf0a8b145769p+1
forward: 0x1.5bf0a8b14576ap+1

Wie man sieht ist die Lösung mit der umgekehrten Reihenfolge Bit
-identisch exakt das was numbers::e_v<double> auch ist. Die Lösung
nach vorne ist ein klein wenig ungenauer.

[Helmut Schellong]

On 04/09/2023 16:45, Bonita Montero wrote:
> Am 08.04.2023 um 22:19 schrieb Helmut Schellong:
>
>> Ich verstehe Dich überhaupt nicht!
>>      long double const fak_array[1750]= { ... };
>> Wo ist das Problem?
>
> Da einen FP-Wert zu nehmen ist unsinnig, denn die Zahl ist eh ganz-
> zahlig. Da könnte man auch direkt einen uint64_t nehmen.

Nein, wenn man mit Hilfe einer Reihe etwas berechnen will, z.B. e,
dann macht man das mit long double.
Hab ich schon ~40-mal gemacht - es funktioniert natürlich.
Die Anzahl der maximal sinnvollen Reihenglieder kann man feststellen.

Mehr als 1754! ist nicht notwendig und ist auch bei 80bit nicht möglich.

[Helmut Schellong]

Das habe ich übersehen, daß er long-integer-stellen machen will.

[Bonita Montero]

Am 09.04.2023 um 19:43 schrieb Helmut Schellong:

> Nein, wenn man mit Hilfe einer Reihe etwas berechnen will,
> z.B. e, dann macht man das mit long double.

Es ging mir darum, dass Du auch mit einem long double niemals so viele
Werte berechnen können wirst ohne, dass Du keinen Überlauf bekommst;
1750 Fakultäts-Were - no way. Und wenn man es halt korrekt macht nimmt
man eine Bignum-Library, dann kommt man dem näher, aber ich glaub dann
explodiert die Wert-Länge so stark, dass man das in keinen Arbeitsspei-
cher der Welt kriegt.
Und die x87-FPU ist tot weil nicht kompatibel zu andren CPUs, Loads
und Stores haben ein Vielfaches höhere Latenz (siehe agner.org) und
viele iterative Operationen wie FDIV, FSQRT etc sind auch langsamer.
Und der CORDIC-Algorithmus ist ein Vielfaches schneller mit SSE als
durch die FSIN.

[Thomas Koenig]

Walter H. <Walter...@mathemainzel.info> schrieb:
> On 09.04.2023 00:48, Thomas Noll wrote:
>> Am Sat, 8 Apr 2023 19:37:08 +0200 schrieb Walter H.:
>>
>>> [Eulersche Zahl]

>>> 100 000 Stellen ist etwas f. gut 2 Sekunden;

>>> interessant wird es ab 25 Mio. od. mehr Stellen;
>>

>> mit mpfr dauern 100 000 Stellen hier 33 Millisekunden.
>> 25 Millionen Stellen dauern hier 21 Sekunden (inklusive Ausgabe ...).
>>
>> Ich weiß nicht, ob es (dafür) noch bessere verfügbare libs gibt,
>> aber du solltest mpfr zumindest als Meßlatte verwenden.
>
> ok kannte ich nicht, die Suche leitete mich zur korrekten Stelle und
> dann das ...

Ist typischerweise bei Linux-Distributionen dabei, bei Ubuntu z.B.
als mpfr-dev (wenn du selber was schreiben willst, um sie zu verwenden).

[Helmut Schellong]

Ich verstehe erneut nicht.

fak(1754)
1.979261890105010055e+4930
fak(1755)
inf

Das ist doch eine ganz normale long-double-Zahl.

[Bonita Montero]

Am 09.04.2023 um 23:55 schrieb Helmut Schellong:

> Ich verstehe erneut nicht.
> fak(1754)
>    1.979261890105010055e+4930
> fak(1755)

> Das ist doch eine ganz normale long-double-Zahl.

Ja, ggü. einer Bignum-Zahl halt ungenau.

[Helmut Schellong]

Ja, aber wenn man eine Reihe berechnen will, mit einem Resultat long double,
dann kann auch auf dem Weg dahin überall long double verwendet werden.
Das ist konsistent.

[Bonita Montero]

Am 10.04.2023 um 13:04 schrieb Helmut Schellong:

> Ja, aber wenn man eine Reihe berechnen will, mit einem Resultat long
> double,
> dann kann auch auf dem Weg dahin überall long double verwendet werden.
> Das ist konsistent.

Na eben nicht, weil man ja auch "untewegs" Präzisions-Verlust
hat den man eben am liebsten erst am Ende hätte.

[Helmut Schellong]

Gleitkomma hat grundsätzlich Verluste an Genauigkeit.
Wenn 18 Stellen ganz genau sind, kann man damit i.d.R. leben - ist doch normal.

Auch bei 100000 Stellen liegt Ungenauigkeit vor.
Bei jeder beliebigen Anzahl von Stellen liegt Ungenauigkeit vor.
Man muß wissen, welche Genauigkeit ausreicht.
Es wird schon immer mit Schutzstellen gerechnet.

[Bonita Montero]

Am 10.04.2023 um 14:56 schrieb Helmut Schellong:

> Gleitkomma hat grundsätzlich Verluste an Genauigkeit.

Darum geht's nicht so direkt, sondern darum, dass man die Reihe fort-
laufend ohne Verlust berechnet und jeweils gen double konvertiert und
schaut ab wo die Konvertierung nach dem letzten Schritt keine Änderung
beim Wert mehr ergibt. Ich mein das wär für uns zu aufwendig, aber wenn
man eine Runtime schreibt sollten solche Ermittlungen schon drin sein.
Ich fände das schon erstrebenswert, so Konstanten wie e möglichst genau
zu haben.

> Wenn 18 Stellen ganz genau sind, kann man damit i.d.R. leben -
> ist doch normal.

Das mit den 18 Stellen ist ne Krücke da viele Zahlen aus dem Dezi-
mal-System nicht als endlicher Bruch darstellbar sind, z.B. 0,4.
Bzw. dezimale Zahlen lassen sich oft nicht ohne Verlust darstellen,
binäre Floats aber im Dezimalsystem immer da die 2 als Primfaktor
auch Primfaktor von 10 ist.

[Helmut Schellong]

Seit den 1980ern sind das alles Binsen für mich.
file:///u/hp/de/htm/math87.htm#reihen
Vorstehend habe ich mich wiederholt relativ intensiv mit Potenzreihen befaßt.
Interessiert irgendwie nur mich, wie es scheint.

19-stellige Genauigkeit erreiche ich fast immer.
Falls nötig, kann mit 3 Schutzstellen gearbeitet werden.

[Bonita Montero]

Am 10.04.2023 um 16:32 schrieb Helmut Schellong:

> Seit den 1980ern sind das alles Binsen für mich.

Wenn Du so flapsig von 18 Stellen redest wohl nicht durchgängig.

[Bonita Montero]

Am 09.04.2023 um 20:07 schrieb Bonita Montero:

> Und die x87-FPU ist tot weil nicht kompatibel zu andren CPUs, Loads

> und Stores haben ein Vielfaches höhere Latenz (siehe agner.org) ...

Ich hab das mal auf meiner Zen2-CPU gemessen:

load8: 0.389431
store8: 0.544294
load10/a: 0.668949 (172%)
store10/a: 0.8356 (154%)
load10/u: 1.06397 (159%, 273%)
store10/u: 1.63585 (196%, 301%)

load8 und store8 sind die Timings alignter double Zugriffe. load10/a
und store10/a sind die Timings alignter long double Zugriffe (16).
In den Klammern dahinter sind die Verbesserungen in Prozent ggü. den
Vor -Ergebnis. load10/u und store10/u sind die Timings unalignter (2)
long double Zugriffe; der erste Wert in den Klammern ist die Relation
zum Vor-Ergebnis, der danach die Relation zum Vor-Vor-Ergebnis.
D.h. wenn die long double Zugriffe alignt (16) sind sieht die Sache
gar nicht so katastrophal aus; dementsprechend hat der g++/x64 auch
ein Alignment von 16 für ein long double.
Dennoch ist die Annahme, ein long double wäre 80 Bit breit natürlich
nicht portabel bzw. man kann den Datentyp oft vergesse.