Integer-Mathematik

Okay, gegeben seien die Funktionen $\lceil \log_2{x} \rceil$ und $\lfloor \log_2{x} \rfloor$ (x ist eine natürliche Zahl)

Fällt euch auf Anhieb ein, wie man mit ihnen und reiner Integer-Arithmetik $\lceil \log_2({a*x/b}) \rceil$ bzw. $\lfloor log_2({a*x/b}) \rfloor$ ausrechnen kann? Also a und b sind auch natürliche Zahlen.

Okay, also irgendwie bin ich mir jetzt ziemlich sicher, dass ich den inneren Term aufrunden bzw. abrunden darf (bzw. in meinem Fall muss), ohne am Ergebnis etwas zu verändern.

Jester

Ich würde mal tippen, dass für hinreichend großes x, so ab x >= 1 gilt,
dass

$\lfloor \log(x) \rfloor \le \log(\lfloor x \rfloor)$
und
$\log( \lceil x \rceil) \le \lceil \log(x) \rceil$

Andererseits unterscheiden sich offensichtlich $\lfloor \log(x) \rfloor$ und $\lceil \log(x) \rceil$ um höchstens 1. Das heißt, Du liegst nie weit daneben. Bestimmt reicht ein einzelner Test um rauszufinden welches der beiden Ergebnisse nun korrekt ist.

Jodocus

Wenn ich mich nicht irre, kannst du mit der Einschränkung $b = 2^k, k \in \mathbb{N}$ das machen:
Allgemein gilt ja $\log\_n{ab}=\log\_n{a}+\log_n{b}$ und $\log\_n{\frac{a}{b}}=\log\_n{a}-\log_n{b}$ .

Dann ergibt sich für jedes $x \in \mathbb{N}$ z.B.:
$\lfloor \log\_2{(a\frac{x}{b})} \rfloor = \lfloor \log\_2{a} + \log\_2{x} -\log\_2{b}\rfloor \ge \lfloor \log\_2{a} \rfloor + \lfloor \log\_2{x} \rfloor - \lfloor \log_2{b} \rfloor$ , wobei nur letzteres berechnet werden kann.

Wenn $ax \mid b$ gilt, ist das Problem allerdings trivial gelöst. Bleibt noch der Fall $ax \nmid b$ , dann ist $ax = mb + r$ mit $r \lt b$ , und damit insbesondere $\log\_2{(a\frac{x}{b})} = \log\_2{(\frac{mb + r}{b})} = \log\_2{(mb+r)} - \log\_2{b} = \log\_2{a} + \log\_2{x} -\log_2{b}$ , also damit $\lfloor \log\_2{a} + \log\_2{x} \rfloor = \lfloor \log_2{(mb+r)} \rfloor$ , wobei du die rechte Seite wieder leicht auswerten kannst.
Wenn $k \in \mathbb{N}$ , dann ist $\lfloor x + k \rfloor = \lfloor x \rfloor + k$ , also gilt $\lfloor \log\_2{(a\frac{x}{b})} \rfloor = \lfloor \log\_2{(mb+r)} - \log_2 b \rfloor$ = $\lfloor \log\_2{(mb+r)} \rfloor - \lfloor \log\_2 b \rfloor = \lfloor \log_2{(mb+r)} \rfloor - k$ , wenn es $k \in \mathbb{N}$ gibt, sodass $b = 2^k$ gilt.

Whoah danke, hatte nicht mit der Ausführlichkeit gerechnet. Hoffentlich hattet ihr wenigstens etwas Freude an der Problemstellung!