Matroids Matheplanet Forum Index
Moderiert von matph
Informatik » Programmieren » Realisierung der Logarithmusfunktion in C
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Realisierung der Logarithmusfunktion in C
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 268
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-04-07


Auf dies Fragestellung stieß ich, als ich herausfinden wollte. ob eine sehr grosse zahl aus N eine glatte Potenz
einer natürlichen $n \in N$ ist.

$Log_{10}(100)$ ist 2, da ist es schön einfach an der Anzahl der Nullen zu sehen.

Und lb(2097152) ist 21. Man kann sicher mit brute force Methoden und scharfen hinsehen einiges lösen.

Wie ist generell die Realisierung der Logarithuns-funktion in C?
Eine ca 10000 Ziffern umfassende Tabelle wäre mit einem "lookup" zu lesen.
Man könnte dann noch interpolieren.

Eine besipielhafte vereinfachte Grundfrage: "ist x = 131072 eine 17te Potenz von einer natürlichen Zahl?"
Hier gebe ich die Basis vor. Benötigt man evtl. gar keinen Logarithmus fuer diese spezielle Problem?
der Windows eigene Rechner liefert  $\sqrt[17]{131072}= 2$.

$\sqrt[17]{131073}= 2,00000089..$ weicht ab. Das erwartet man eben von einem guten Rechner.

Wie genau ist der Algorihmus zum logarithmieren in Maschinensprache umgesetzt? Es gibt keinen $\sqrt[b]{x}$ Befehl.

In gcc unter Ubuntu kann man ja den Assembleroutput generieren.
Ich habe eben leider kein Linux, wo es so ein compilerswitch in gcc gibt,
der mir den generierten Machinencode anzeigt.

Oder wird mit Taylorreihen gearbeitet?

also 2 Fragen:
1. Wie wird überhaupt der Logarithmus in einem Compiler einer beliebigem Zahl aus N zu einer beliebigen Basis implementiert?
Mittels Taylorreihen/entwcklungen? Das würde sich anbieten.
Es reicht ja den natürlichen log(x) zu wissen oder den 10er-Log. Oder irgenéine andere Basis, etwa den lb(x) der sich anbietet wg. der binären Struktur der  digitalen Compiter Welt, und kann immer leicht umrechnen:
$log_b(x)= log_10(x)/log_10(b)$
Manche mögen sich noch an Logarithmen-Bücher erinnern!
4- stellig und dann interpolieren.

2.
Gibt es eine einfachere Art herauszufinden ob eine $x \in N$ eine
glatte b-Potenz ist? b sei beliebig! Ist x=17179869184 eine Potenz zu einer nicht vorgegebenen Basis b?
Was ist in logb(17179869184) das b, so dass es passt.
Gibt es glatte b und n so dass $b^n =x$ aufgeht.

Ich nutze keine FPU s, sonder suche einen Algoritmus.

Ich will wirklich 50 stellige zahlen untersuchen, ob sie Potenz irgendeiner möglichst kleinen Basis sind.  
Ich grenze mal auf maximal 40 als Exponent ein.
Eine Art kleines Rätsel:
Was ist 11920928955078125 für eine Potenz zu welcher Basis hier Vorgabe exponent < 40.

Mit Angabe des Rechenweges 🙂

Edit:
Mir gehts mehr um die Methode d.h. alle in 80x86 gegebenen Befehle sind erlaubt. Oder besser: alles was die gmp-library kann ist erlaubt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2237
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-04-07


Bei bekannter Basis ist der diskrete Logarithmus erst dann ein Problem, wenn modular gerechnet wird.
Ansonsten kann man ihn leicht durch binäre Suche mittels repeated squaring berechnen.

Für kleine Zahlen wie im Beispiel geht auch sowas:

Python
>> discrete_log = lambda n, b: int(log(n)/log(b)) if n == b**int(log(n)/log(b)) else None
 
>> [(11920928955078124+k,discrete_log(11920928955078124+k,5)) for k in range(3)]
 
[(11920928955078124, None), (11920928955078125, 23), (11920928955078126, None)]
 



-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5870
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2020-04-07


Hallo juergenX,

2020-04-07 19:17 - juergenX im Themenstart schreibt:
Es gibt keinen $\sqrt[b]{x}$ Befehl.

In C gibt es den Befehl pow(x, y). (In der math-Library). Allerdings sind hier x und y sowie das Ergebnis double-Werte. Es können also unerwünschte Rundungen auftreten. Um also $y=\sqrt[b]{x}$ zu berechnen, berechnest du zunächst y = pow(x, 1/b) und überprüfst anschließend, ob tatsächlich \(y^b=x\) und vielleicht noch, ob \((y+1)^b=x\).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1083
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-04-07


So ein Zufall: genau das mache ich gerade mit der 18004stelligen Zahl
(RNA vom Corona-Virus verschlüsselt für beste Komprimierung).

hier mehr

Für Log brauchst Du das "Rad nicht neu erfinden", da es genau optimierte Funktionen bereits gibt: Log per GMP oder MPFR

Deine Zahl 11920928955078125 ist so winzig, dass ein kleines php Programm die Lösung in ms findet:



Da wird von Basis 2 bis zur maximal vorgebbaren Basis (For Schleife) das kleinste Offset
 (also die Differenz zur passenden Potenz) gesucht:
potenz=gmp_div(log(Input),log(Basis))
Differenz = abs(Input - Basis^potenz)

Du suchst doch bestimmt nicht nur den Sonderfall Offset=0 - oder?

Da die Offsets jedoch ultra-extrem selten klein sind, kann man Brüche mit zur Hilfe nehmen:






Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 268
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-04-08


2020-04-07 22:14 - hyperG in Beitrag No. 3 schreibt:


Für Log brauchst Du das "Rad nicht neu erfinden", da es genau optimierte Funktionen bereits gibt: Log per GMP oder MPFR

Deine Zahl 11920928955078125 ist so winzig, dass ein kleines php Programm die Lösung in ms findet:


Danke für die viele links und tips 5^23 ist  11920928955078125.
Das war zu einfach.
Dank auch für die vielen Tips, ich konnte noch nicht alles zu checken.

Eine generelle gmp_loga(x,b) gibt es nicht , also $\log_b(x)$ gibt es wohl nicht für sehr grosse x.
Aber gechickte Approximationen.
Man nimmt von einer 100 stelligen (x) für feste Basis b die ersten 9 Ziffern y und nullt die restlichen und bildet den gewünschten y0=log_b(y)
und auch den y1=log_b(y+1).
Aus (y1-y0) kann man evtl schliessen ob die Riesenzahl wirklich eine glatte Potenz von b sein kann, denn die suche ich.
Das ist  so grob in die Kladde gedacht..

So etwa wie das, was Strgaltentf vorschlug.




man kann bei sehr vielstellihen



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1083
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-04-08


Fertige Log-Funktion ganz einfach aus DLL holen:
HMODULE  theDll =LoadLibrary(TEXT("libmpfr.dll"));
...
MPFR_LOG mpfr_log = (MPFR_LOG)GetProcAddress(theDll,"mpfr_log");
... init...: mpfr_init2(x, Genauigkeit);
 int err=mpfr_log(y, x, MPFR_RNDN);
...
pchOut=mpfr_get_str (NULL, &e,10, n, y, MPFR_RNDNA);
printf("y = %s Kommaverschiebung=%ld\n",pchOut,e);

Mehrere 100000 Stellen machbar.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
crisp
Junior Letzter Besuch: im letzten Monat
Dabei seit: 15.03.2020
Mitteilungen: 14
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-04-09


Hi Juergen,

willst du nun eigentlich logarithmen berechnen oder Wurzeln ziehen?

ich habe mir etwas aus der gmp lib gebastelt. Da dort Brüche als Datentypen unterstützt werden, geht das fix, und passt auch supergut zur Intervallhalbierung, wenn man nicht nur auf ganzzahlige Lösungen hinaus will. Nach meinen Erfahrungen ist gmp recht effizient, und stellt ja auch schon Funktionen für Potenzen bereit. Das sind also wenige Zeilen in C die man dazu schreiben muss. Wenn du dazu Fragen hast krame ich "die ollen Sachen" mal raus.

Grüße
Carl



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 268
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2020-04-09


2020-04-09 08:57 - crisp in Beitrag No. 6 schreibt:
Hi Juergen,

willst du nun eigentlich logarithmen berechnen oder Wurzeln ziehen?

Grüße
Carl

Es ging mir darum: Ist eine gegebene Sehr grosse Zahl x eine Potenz
d.h ja gibt es $b,x \in N: log_b(x) \in N$ und $b^{log_b(x)}=x,b,x,log_b(x) \in N$.
Also ist x eine glatte Potenz, Basis und Exponent beliebig aus N.
Wahrscheinlich geht das auch ohne Logarithmus..
Schick mal was du hast als PM das waere nett:)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1083
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2020-04-10


Natürlich kann man Log auch iterativ bestimmen, aber das wird bei großen Zahlen langsam.

Hier eine Zahl zum Testen, die ein kleinen Offset zu einer Potenzzahl hat und noch nicht so im Internet zu finden war:
a^b+c mit c < 5000
56191779941199568261718534306894018908396678623777478504315980789486786568011594584548956655395926010106375918646401469633245745563665854904711355867220707990646817

Mit meinen 3 Programmen (php, mathematica & libmpfr.dll aus Beitrag 5)
in weniger als 0,5 s ermittelt.

Test 2, da ja Exponent nicht die 40 übersteigen sollte:
a^b+c mit c < 5000
9980651927275601976003751734997968091183975975462554807367984559752268331758986147614077726258271311367231730336341461186326161187496409621862204514556810641419701

Etwa 1 s unoptimiert.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 268
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2020-04-10


2020-04-10 14:36 - hyperG in Beitrag No. 8 schreibt:
Natürlich kann man Log auch iterativ bestimmen, aber das wird bei großen Zahlen langsam.


Etwa 1 s unoptimiert.


"Natürlch" geht es um den Al Zimmermann programing test d.h. der spornte mich zum Loagrithmus berechnen zu an.

z.B. Rest freie Summen einer potenzsumme  zu finden oder eben mit möglichst geringem rest zu einer glatten Pptenz.
 
Bsp.:
1^7 + 3^7 + 5^7 + 9^7 + 12^7 + 14^7 + 16^7 + 17^7 + 18^7 + 20^7 + 21^7 + 22^7 + 25^7 + 28^7 + 39^7 =40^7

bei Zimmermann soll man exponenten 16-40 nehmen.

Das zu lesen


hilft;)

Ich hatte die Idee, mit brute force und einer festen Basis sagen wir exp = 23 beliebiges $s=a^{23}+b^{23}+c^{23}+ \dots = z^{23}$ aufzusummieren und halt irgendwie die Reste von s zu glatten Potezen zu finden. Idealfall r = x^23-s = 0$
Wenn der Logarithmus zur Basis 23 nahe einer natuerlichen n ist, kann man durch Ruecktests feststellen, ob die Näherung gut war. Kleine Unterschiede zu einer natuerlichen n im Logarithm sagen kleine Reste vorraus.
Beteiligt sich sonst noch jemand?









Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2237
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2020-04-10


Dir ist aber klar, dass die 23 im Beispiel der Exponent ist und nicht die Basis?


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
crisp
Junior Letzter Besuch: im letzten Monat
Dabei seit: 15.03.2020
Mitteilungen: 14
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2020-04-11


2020-04-09 18:36 - juergenX in Beitrag No. 7 schreibt:
Schick mal was du hast als PM das waere nett:)

Es ist ein Contest :)

Frohe Ostern
und nichts für ungut...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 268
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2020-04-12


2020-04-11 11:27 - crisp in Beitrag No. 11 schreibt:
2020-04-09 18:36 - juergenX in Beitrag No. 7 schreibt:
Schick mal was du hast als PM das waere nett:)

Es ist ein Contest :)

Frohe Ostern
und nichts für ungut...
lol
hätte ich das nicht gesagt würdest du gar nicht kennen ;)
Also feste conteste:)
Jetzt musste dich auch einschreiben und ne gute Lösung mit gmp_lib anbieten!
Mit der Loadlibrary check ich nicht sorry.
Mir ging um den prinzipiellen Algorithmus, d.h. wirlich den
Konkreten oder auch nicht diskreten Exponenten zu einer festen Basis sagen wir 29 zu finden.
meinetwegen nimm die Superzahl von oben:
Data
x=56191779941199568261718534306894018908396678623777478504315980789486786568011594584548956655395926010106375918646401469633245745563665854904711355867220707990646817
vereinfacht 
y=56191779900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Man kann sicher auf 10 stellige Doubles zurückgreifen und
$log_{29}(y/10^{155)}$ oder $log_{29}(y)- 155*log_{29}(10)$ berechnen.

Wie nahe ist man dann an einer glatten Potenz von 29?
Der Rest zu einer glatten Potenz soll ja minimieret werden.
Wenn unbefriedigend, teste halt eine andere Basis bis 40 etwa.
und wie das z.B. auch in Java impelemtiert?












Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 155
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2020-04-12


Gemäß [1] ist die Standard-Implementation von log(double) offenbar der Form, dass der Logarithmus der Mantisse via Taylor-Entwicklung bestimmt und dann entsprechende Vielfache von log(2) addiert/subtrahiert werden. (log(2) dürfte als Konstante vorliegen.) Die Autoren von [1] schlagen dagegen vor, für log(Mantisse) einen Lookup-Table zu verwenden.

[1]:

edit: Wahrscheinlich wird man keine Taylor-Entwicklung sondern andere polynomielle Näherungen wählen, die auch schon bei niedrigerem Grad genügend genaue Näherungen liefern, siehe



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
juergenX hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]