JavaScript Warum Math.log ?

[Hendoul]

Hi

Ich versuche grad diese Lösung zu verstehen:
https://www.codingame.com/ide/puzzle/factorial-vs-exponential

Ziel:
For each of the given numbers A, find the smallest integer N, such that A^N < N! , where N! = 1 * 2 * ... * N
The numbers given can have up to 2 digits after decimal point.

Mehr details siehe link.

readline().split(' ').map(Number)
     .map((n) => {
         let sum = 0; let i = 0; let logA = Math.log(n);
         console.error('log = ' + logA)
         do {
             sum+=Math.log(++i);
         } while (sum <= i*logA);
         return i;
     })

Ich verstehe nicht, warum man das hier mit einem Math.log lösen kann. Das letzte Mal hatte ich vor 20 Jahren mit Logarithmen zu tun. Habe dann gestern versucht das ein bisschen aufzufrischen. Aber vermutlich ist es mir immer noch gut genug gelungen um zu verstehen, warum hier ein log zum Zuge kommt.

Und das mit dem N! sehe ich hier auch nicht wirklich, das muss sich ja hinter dem i*logA verstecken.

Langer Schwede kurzer Finn - ich versteh nur Bahnhof

 

[tollertyp]

Was ist denn ein Logarithmus in deinen Worten bzw. die Funktion?

Spoiler

Aus meiner Sicht ist es eben die Umkehrung vom Potenzieren. Und A^N ist eben potenzieren. Und die Umkehrung dient halt der Vereinfach des Problems.

D.h. anstatt das N! berechnet wird, wird einfach immer der Logarithmus der nächsten Zahl addiert. Und dann verglichen, ob das dann kleiner ist als das Produkt.

 

[Hendoul]

Irgendwie eine andere Darstellungsmöglichkeiten von Exponenten und um grosse Zahlen 'menschlich verständlicher' darzustellen.

In meinem Verständnis kann man A^N dann auch so darstellen -> logBasisA(x)=N , so dass A^N = x

Aber die Lösung nimmt den Log mit der Basis e.

 

[Nilson]

Ich finde die Variabel ungünstig gewählt, damit ist es wohl passender zur Aufgabenstellung:

readline().split(' ').map(Number)
     .map((A) => {
         let sum = 0; let N = 0; let logA = Math.log(A);
         console.error('log = ' + logA)
         do {
             sum+=Math.log(++N);
         } while (sum <= i*logA);
         return N;
     })

Und das Beispiel für Math.log zeigt gut, warum man den natürlichen Logarithmus verwenden kann:

function getBaseLog(x, y) {
  return Math.log(y) / Math.log(x);
}

// 2 x 2 x 2 = 8
console.log(getBaseLog(2, 8));
// Expected output: 3

 

[tollertyp]

Dann ohne Edit:
Geht wenn man versteht, was log(a*b) ist - nämlich log a + log b

D.h. wir haben
A^N < N!
log(A^N) < log(N!)
N * log A < log(1 * 2 * 3 * 4 * 5 * ... * N)
N * log A < log(1) + log(2) + log(3) + log(4) + log(5) + ... + log(N)

Das links kann man einfach berechnen, indem man einmal den log A berechnet. Und das rechts kann man einfach durch weiteres Aufsummieren der nächsten Logarithmusses berechnen.

Das Problem kann man halt vereinfachen, indem man beidseitig logarithmiert - die Voraussetzungen, dass das geht, sind ja gegeben. Es hat also rein gar nichts mit JavaScript zu tun, sondern einfach mit Mathematik/Algorithmen.

Ob das aber wirklich schneller/effizienter ist, ganz ehrlich: Keine Ahnung. Mich würden Benchmarks interessieren. Weil auf der rechten Seite haben wir ja immer eine Ganzzahlmulitipliikation, die sicher weniger Rechenzeit als ein Logarithmus braucht. Und von A^N zu A^(N+1) ist wohl kaum teurer als "i*logA", beides ist Ganzzahl mal Gleitkommazahl.

@Nilson: Ja, die Benamung ist wirklich bescheiden im Code.

 

[BeBur]

Ob das aber wirklich schneller/effizienter ist, ganz ehrlich: Keine Ahnung. Mich würden Benchmarks interessieren. Weil auf der rechten Seite haben wir ja immer eine Ganzzahlmulitipliikation, die sicher weniger Rechenzeit als ein Logarithmus braucht. Und von A^N zu A^(N+1) ist wohl kaum teurer als "i*logA", beides ist Ganzzahl mal Gleitkommazahl.

Ich gehe davon aus, das es was damit zu tun hat, allzu große Zahlen zu vermeiden. Entweder Vermeidung von Overflows (wahrscheinlich) oder die Vermeidung von zu starken Rundungsfehlern bei sehr großen Fließkommazahlen (weniger wahrscheinlich).

 

[Hendoul]

Warum sind die Voraussetzungen gegeben?

Kann man immer einfach alles in ein log schreiben?

Also wenn ich sowas habe z.B.
a + b - c < x -y
kann ich einfach nach
log(a+b-c) < log(x-y)
umwandeln?

Ich glaube mit der Ausführung der Logarithmen-Gesetze habe ich es nun verstanden.
Auf so eine Lösung muss man erst mal kommen. Ich habe es mit Math.pow gelöst, aber da gibt es dann anscheinend Probleme mit Dezimalstellen und Rundungsfehlern.

 

[BeBur]

Kann man immer einfach alles in ein log schreiben?

Also wenn ich sowas habe z.B.
a + b - c < x -y
kann ich einfach nach
log(a+b-c) < log(x-y)
umwandeln?

"Immer" nicht, aber der Logarithmus ist eine monotone Funktion und damit bleiben "kleiner gleich / größer gleich" Zusammenhänge erhalten, wenn du ihn auf zwei Ausdrücke anwendest. Selbiges gilt zum Beispiel für die Wurzel. Beide Funktionen haben allerdings das "Problem", dass sie nicht für alle reelle Zahlen definiert sind (soweit wir im Raum der reellen Zahlen bleiben wollen, was in Coding Kontexten meistens der Fall ist).

 

[mibbio]

Entweder Vermeidung von Overflows (wahrscheinlich)

Das dürfte der hautpsächliche Grund sein. Die Fakultät wird ja schon bei relativ kleinen Zahlen ziemlich groß und würde bei den gängigen Datentypen recht schnell den Wertebereich übersteigen. Der Datentyp Number in Javascript ist als "double-precision 64-bit binary format IEEE 754" definiert und geht damit bis maximal 1,8·10^308, was schon mit 171! überschritten wäre.

 

[tollertyp]

Ja, kann durchaus sein, dass es um den Zahlenbereich geht.
Und wenn mit speziellen Datentypen gerechnet wird, die auch größere Zahlenräume erlauben, dann geht auch einiges am Leistungsvorteil verloren.

Kann man immer einfach alles in ein log schreiben?

Also wenn ich sowas habe z.B.
a + b - c < x -y
kann ich einfach nach
log(a+b-c) < log(x-y)
umwandeln?

Naja, da wären die Voraussetzungen dann:
a + b > c
x > y
Mit vorherigem Umstellen:
a + b + y < x + c
wären die Voraussetzungen dafür dann:
a + b + y > 0
x + c > 0

Manchmal "ignoriert" man die Voraussetzungen auch bis zur Lösung und prüft dann, ob das Ergebnis die Voraussetzungen überhaupt noch erfüllt. Z.B. werden (Un)gleichungen häufig durch etwas wie "x + 1" geteilt, das darf man aber nur, wenn x != -1 ist. Weiß man zum Zeitpunkt des Teilens aber nicht. Wenn am Ende dann x = -1 rauskommt, dann weiß man, dass das (evtl) keine gültige Lösung ist - mal ganz vereinfacht gesagt. Kommt halt immer auf den konkreten Kontext an.

Gut, auf die ursprüngliche Aufgabe bezogen: Da reicht die Beschreibung alleine nicht.
Aber das:
1 ≤ K ≤ 100
1 < A_i < 10000

Und naja, ein negatives A ergibt für die Frage halt auch keinen so großen Sinn, weil dann jede zweite Potenz sowieso immer kleiner ist und es für die Fragestellung schlicht keinen "Mehrwert" bietet.

 

[BeBur]

Also noch mal etwas konkreter zur Einordnung: Die Aufgabe ist absichtlich so gebaut, dass die hier genannten zwei Aspekte aus den Grundlagen der Informatik (Mathematik Grundlagen, rechnen mit Logarithmus und Verarbeitung von Fließkommazahlen) zur Anwendung kommen müssen um sie zu lösen. Es ist eher unüblich, dass man eine (Un-)Gleichung umformen muss, um zu einer hinreichend performanten und korrekten Lösung zu kommen.

Bereiche wo man über solche Dinge öfters mal nachdenken muss ist z.B., wenn man grundlegende Operationen/Funktionen auf Datentypen selber implementieren muss. Simples Beispiel ist die Summe aller natürlichen Zahlen bis n. Link. Wendet man nur die Formel an, dann gibt es früher als nötig einen Overflow, weil man zuerst n*(n+1) rechnet und dann erst durch 2 teilt. Sprich, das Ergebnis wäre klein genug, aber ein Zwischenergebnis ist zu groß, um noch in den Datentyp (welcher auch immer) zu passen.