Binäre Multiplikation - Stellensprung

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 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.

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

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

1

#include <stdio.h>

2

#include <stdint.h>

3

4

uint8_t g(uint32_t x) {

5

  uint64_t x2 = (uint64_t)x * x;

6

  uint8_t y = 0;

7

  while(x2 > 1) {

8

    y++;

9

    x2 >>= 1;

10

  }

11

  return y;

12

}

13

14

uint32_t f(uint8_t x) {

15

  static const uint32_t sqrt2 = 3037000499; // 2**31 * sqrt(2)

16

  return x & 1

17

    // falls x ungerade: 2**int(x/2) * sqrt(2), aufgerundet, damit

18

    // kompatibel zu f, wo das Ergebnis abgerundet wird

19

    ? (sqrt2 >> (31 - x/2)) + 1

20

    // x gerade: 2**int(x/2), exakt

21

    : 1 << (x / 2);

22

}

23

24

25

int main(void) {

26

  for(int i=0; i<64; i++)

27

    printf("f(%2d)=%10u g(f(%2d))=%2d\n", i, f(i), i, g(f(i)));

28

  return 0;

29

}

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

1

f( 0)=         1 g(f( 0))= 0

2

f( 1)=         2 g(f( 1))= 2

3

f( 2)=         2 g(f( 2))= 2

4

f( 3)=         3 g(f( 3))= 3

5

f( 4)=         4 g(f( 4))= 4

6

f( 5)=         6 g(f( 5))= 5

7

f( 6)=         8 g(f( 6))= 6

8

f( 7)=        12 g(f( 7))= 7

9

   ⋮                  ⋮

10

f(56)= 268435456 g(f(56))=56

11

f(57)= 379625063 g(f(57))=57

12

f(58)= 536870912 g(f(58))=58

13

f(59)= 759250125 g(f(59))=59

14

f(60)=1073741824 g(f(60))=60

15

f(61)=1518500250 g(f(61))=61

16

f(62)=2147483648 g(f(62))=62

17

f(63)=3037000500 g(f(63))=63

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

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.