Binäre Multiplikation - Stellensprung

[Walter T. (nicolas)]

Hallo zusammen,

ich brauche mal wieder etwas Nachhilfe in Integer-Binär-Mathematik. Eine 
Empfehlung passender Literatur wäre mir fast noch lieber als eine 
direkte Antwort auf meine Frage:

Ich will eine Tabelle logarithmisch gestufter Werte erzeugen. Um das 
Ganze nicht zu einfach machen mit zwei Stützstellen pro Binär-Potenz, 
also so:

$$f(i) = [ \sqrt{2}^0, \sqrt{2}^1, \sqrt{2}^2, , \sqrt{2}^3 ... ]$$

Um genau zu sein, sollte die Umkehrfunktion eine lineare Folge ergeben, 
also
 so:

$$log_\sqrt{2}(f(i)) = [0, 1, 2, 3 ... ] = i$$

(Formeln siehe Bildanhang, falls hier nicht korrekt dargestellt).
Dabei ist die Folge des 2er-Logarithmus für mich der springende Punkt: 
Ich will eine Folge von Integer-Ziffern haben, deren Logarithmus die 
entsprechdene Folge 0 ... n erzeugt.

Den Logarithmus zu sqrt(2) kann ich ja relativ einfach berechnen:

    int f = 123456;
    f*=f;
    uint_fast8_t log = 0;
    while(f) {
        log++;
        f>>=1;
    }

An der "Umkehrfunktion" in Integer knobel ich jetzt eine Weile. Für 
gerade Indizes ist das einfach. Es sind die Werte 1<<i/2. Für ungerade 
Indizes fällt das auf die Frage zurück: Bei welchem Integer macht die 
Anzahl der Binärstellen seines Quadrates einen Sprung, also wann gilt: 
log2(x*x) > log2((x-1)*(x-1)) ?

Viele Grüße
W.T.

[Possetitjel (Gast)]

Walter T. schrieb:

> Für gerade Indizes ist das einfach. Es sind die Werte
> 1<<i/2.

Das sind Wurzeln.

> Für ungerade Indizes fällt das auf die Frage zurück: Bei
> welchem Integer macht die Anzahl der Binärstellen seines
> Quadrates einen Sprung, also wann gilt:
> log2(x*x) > log2((x-1)*(x-1)) ?

Nun ja, ich würde raten, dass es auch Wurzeln sind :)

31*31 passt noch in 9 bit; 32*32 nicht mehr. 32 ist aber
gerade die Wurzel von 1024.

"Halbe" Bits sind immer gerade das sqrt(2)-fache der
nächstniedrigeren.

Oder habe ich die Frage missverstanden?

[Walter T. (nicolas)]

Possetitjel schrieb:
> Oder habe ich die Frage missverstanden?

Nein, Du hast die Frage anders formuliert wiederholt.

Im kontinuierlichen Fall sind das die Wurzeln. Im Integer-Fall sind die 
Wurzeln aber immer kleiner als der Wert, an denen die 
Logarithmus-"Funktion" ihren Sprung hat.

(Praktisch könnte ich so mittelmäßig effizient nach den Stützstellen 
suchen: Da sie immer wenige Werte oberhalb der Wurzeln liegen, kann ich 
die Prüfung auf log2(x*x) > log2((x-1)*(x-1)) dann auf wenige Werte 
beschränken. Über Integer-Mathematik habe ich dann aber immer noch 
nichts gelernt.)

[Possetitjel (Gast)]

Walter T. schrieb:

> Possetitjel schrieb:
>> Oder habe ich die Frage missverstanden?
>
> Nein, Du hast die Frage wiederholt.
>
> Im kontinuierlichen Fall sind das die Wurzeln. Im Integer-Fall
> sind die Wurzeln aber immer kleiner als der Wert, an denen die
> Logarithmus-"Funktion" ihren Sprung hat.

Dann verstehe ich die Frage wahrscheinlich gar nicht.

Für Quadratzahlen findet der Sprung zwischen (wurzel(n)-1) und
wurzel(n) statt.

Für Nicht-Quadratzahlen finder er zwischen floor(wurzel(n)) und
ceil(wurzel(n)) statt.

[Possetitjel (Gast)]

Nachtrag wegen Änderung.

Walter T. schrieb:
> (Praktisch könnte ich so mittelmäßig effizient nach den
> Stützstellen suchen:

Was suchst Du?

Du suchst alle diejenigen ganzen Zahlen, deren Quadrat mit
einer binären Stelle weniger darstellbar ist als das
Quadrat des Nachfolgers?

Falls ja: Ganzen Teil der Wurzel verwenden.

[Walter T. (nicolas)]

Possetitjel schrieb:
> Für Quadratzahlen findet der Sprung zwischen (wurzel(n)-1) und
> wurzel(n) statt.
>
> Für Nicht-Quadratzahlen finder er zwischen floor(wurzel(n)) und
> ceil(wurzel(n)) statt.

Hmm...stimmt. Zumindest bis 2^32 passend die Werte mit meiner 
Brute-Force-gerechneten Tabelle zusammen.

Schade. Problem zwar gelöst, aber nix über Integer-Mathematik gelernt.

[Yalu X. (yalu) (Moderator)]

Walter T. schrieb:
> Ich will eine Tabelle logarithmisch gestufter Werte erzeugen. Um das
> Ganze nicht zu einfach machen mit zwei Stützstellen pro Binär-Potenz,
> also so:

Ich weiß nicht, ob ich das Problem richtig verstanden habe, aber es ist
doch

$$f(i)={\sqrt 2}^{\,i}=\begin{cases} 2^{\lfloor i/2\rfloor} & \quad\text{falls i gerade}\\ 2^{\lfloor i/2\rfloor}\sqrt 2 & \quad\text{falls i ungerade} \end{cases}$$

√2 kann man als Konstante mit geeigneter Genauigkeit festlegen, die
Zweierpotenz lässt sich durch eine Schiebeoperation realisieren:

#include <stdio.h>
#include <stdint.h>

uint8_t g(uint32_t x) {
  uint64_t x2 = (uint64_t)x * x;
  uint8_t y = 0;
  while(x2 > 1) {
    y++;
    x2 >>= 1;
  }
  return y;
}

uint32_t f(uint8_t x) {
  static const uint32_t sqrt2 = 3037000499; // 2**31 * sqrt(2)
  return x & 1
    // falls x ungerade: 2**int(x/2) * sqrt(2), aufgerundet, damit
    // kompatibel zu f, wo das Ergebnis abgerundet wird
    ? (sqrt2 >> (31 - x/2)) + 1
    // x gerade: 2**int(x/2), exakt
    : 1 << (x / 2);
}


int main(void) {
  for(int i=0; i<64; i++)
    printf("f(%2d)=%10u g(f(%2d))=%2d\n", i, f(i), i, g(f(i)));
  return 0;
}

Die Funktion g berechnet dabei den ganzzahlige Logarithmus zur Basis √2.
Wie man sieht, ist g die Umkehrfunktion von f:

f( 0)=         1 g(f( 0))= 0
f( 1)=         2 g(f( 1))= 2
f( 2)=         2 g(f( 2))= 2
f( 3)=         3 g(f( 3))= 3
f( 4)=         4 g(f( 4))= 4
f( 5)=         6 g(f( 5))= 5
f( 6)=         8 g(f( 6))= 6
f( 7)=        12 g(f( 7))= 7
   ⋮                  ⋮
f(56)= 268435456 g(f(56))=56
f(57)= 379625063 g(f(57))=57
f(58)= 536870912 g(f(58))=58
f(59)= 759250125 g(f(59))=59
f(60)=1073741824 g(f(60))=60
f(61)=1518500250 g(f(61))=61
f(62)=2147483648 g(f(62))=62
f(63)=3037000500 g(f(63))=63

Der umgekehrte Fall gilt nicht, da g nicht injektiv ist, und damit keine
Umkehrfunktion hat.

[Walter T. (nicolas)]

Hallo Yalu,

Du hast gerade aus einem Wust einen flotten Einzeiler gemacht. Ich weiß 
gerade nicht, ob ich mich

a) freuen soll, weil ich meinen Lookuptable jetzt gemütlich zur Laufzeit 
berechnen kann, ohne irgendwelche Codeschnipsel zur Erzeugnung neben dem 
Quelltext aufbewahren zu müssen oder

b) mich ärgern sollte, die ganze Zeit ein Brett vorm Kopf gehabt zu 
haben.

Ich entscheide mich für Option a). Vielen Dank!

Viele Grüße
W.T.