Bitové operace ve vyšších jazycích

[Kit]

Btw by me fakt zajimalo, jestli se toto jeste na SS/VS uci, tj. dvojkovy doplnek, proc funguje, jak funguje atd. My to pocitali na papire, byla to docela sranda a navic v podstate dobre znamky za "nic".

Na SŠ se učí nejen dvojkový doplněk, ale i IEEE 754.

[Reklama]

[Kit]

protoze dvojkovy doplnek, ale to uz taky asi neni zapotrebi dneska znat

tak samozřejmě, na to jsou dneska optimalizované frameworky, zalez kam geologicky patříš dinosaure

Dnes je trendy pure, pure css (bez js), pure javascript (bez jquery), ...

Zapomněl jsi na pure PHP, které používám.

[Tuxik]

kokoti uz tady nespamujte. delejte neco uzitecnyho. co kdyby jsme zalozili vlastni forum, ktere by bylo na urovni?

Ne, fórum se nezakládá, ale musí se naprogramovat. Vše co bylo v minulosti uděláno je špatně a bylo by dobré si to udělat po svém a dokonale. Kdo do toho jde? By mě zajímalo, na čem by to ztroskotalo, ale předpokládám, že už na výběru jazyka

[franto]

+1

[balki]

Btw by me fakt zajimalo, jestli se toto jeste na SS/VS uci, tj. dvojkovy doplnek, proc funguje, jak funguje atd. My to pocitali na papire, byla to docela sranda a navic v podstate dobre znamky za "nic".

Na SŠ se učí nejen dvojkový doplněk, ale i IEEE 754.

Aj my sme sa to ucili na vysokej. Boli to znamky za nic, ale pravdu povediac vzdy mi to vyleti z hlavy a musim si to zopakovat, ked to potrebujem. Uz to nepouzivam denne.

O.T. Zaujimava zbierka low level hackov z casov PDP-11 je v tejto knizke http://www.hackersdelight.org/

[Reklama]

[gl]

Samozřejmě pokud umocňuješ a posouváš celým číslem. Pro reálný exponent to nemá smysl porovnávat.

Takže podle tebe je tohle ekvivalentní? V klidu by jsi vyměnil foo za bar?

Kód: [Vybrat]

def foo(x):
    return x << 2
def bar(x):
    return x * 4


Na blbce jako ty už nebudu reagovat. Kde jsem psal něco o násobení?

[gamer]

Na blbce jako ty už nebudu reagovat. Kde jsem psal něco o násobení?

Argumenty ti už došly, že? Takže speciálně pro tebe:

Kód: [Vybrat]

def foo(x):
    return 1 << x
def bar(x):
    return 2 ** x
Je to ekvivalentní? Můžeš vyměnit foo za bar, jak tady celou dobu tvrdíš?

[Tuxik]

Je to ekvivalentní? Můžeš vyměnit foo za bar, jak tady celou dobu tvrdíš?

Může. Stejně jako může každej vyměnit cokoliv za cokoliv jinýho. Programátor má tu moc udělat z 1+1 třeba 3 a nikdo mu v tom nezabrání. Otázkou spíš je, jestli je to tak správně a jestli to k něčemu bude.

[gl]

A ke zpracování signálů na jednom řádku - mezi zpracování signálů se dá započítat třeba FIR filtr 1. řádu u ADC na potlačení šumu.

Třeba derivační článek x_n+1 = 7/8*x_n + 1/8*a se napíše v C v přerušení 12b ADC takto:

Kód: [Vybrat]


volatile uint16_t x = 0;

void ADC_ISR(void) {
  x = ((x << 3) - x + ADC_VALUE) >> 3;
}

Třeba u ARMu s barrel shifterem je to velice efektivní metoda. Jenom vědět, jak na to bez násobení a floatů.

Python nedělám, ale pokud by chtěl stejně filtrovat data, tak princip bude pořád stejný. A taky se to asi vejde na jednu lajnu...

v Pythonu na běžném procesoru je IMHO

Kód: [Vybrat]

x = (x*7 + ADC_VALUE)//8

stejně rychlé a je to přesnější přepis toho vzorce. Snáz se to čte.

A to, že je to stejně rychlý, jsi vzal kde? Na (8x-x) potřebuješ jeden shift o tři bity (u ARMu barrel shifter) a jeden rozdíl. To jsou dvě instrukce a stačí ti dva registry CPU. Pro násobení sedmi potřebuješ 3x shift o 1b a 3x součet a pravděpodobně si to vezme i jeden registr procesoru navíc. Takže samotná operace, pokud to kompilátor nepřevede na 8x-x, je 3x pomalejší. A pokud to vezme jako obecný násobení 16x16->32 bez HW násobičky, tak je to dokonce 16x pomalejší. Ve zpracování v časově kritickým přerušení nebo na větším objemu dat je to sakra poznat.

Kolega jednou dělal něco v C# na x86_64 a použil knihovní funkce. Přechrchlání dat za cca 2,5 minuty.
Vyhodil knihovní funkce, použil vnitřek (s floatama) přímo. Stáhl to na 80s.
Přešel na integer, byl na 20s.
Po úpravě konstant tak, aby to byly mocniny dvojky nebo maximálně dvě jedničky v konstantě (kompilátor mohl používat shifty) se dostal na 3,5s.

Kód: [Vybrat]

>>> timeit("""x=0\nfor i in range(10000):x = ((x << 3) - x + 1) >> 3""", number=10000)
21.526970521983458

>>> timeit("""x=0\nfor i in range(10000):x = (x*7 + 1)//8""", number=10000)
13.707707367982948

za ADC_VALUE jsem dosadil 1. Asi to není moc vypovídající, ale verze s posuny mi vyšla dvakrát pomalejší.

[gl]

Na blbce jako ty už nebudu reagovat. Kde jsem psal něco o násobení?

Argumenty ti už došly, že? Takže speciálně pro tebe:

Kód: [Vybrat]

def foo(x):
    return 1 << x
def bar(x):
    return 2 ** x
Je to ekvivalentní? Můžeš vyměnit foo za bar, jak tady celou dobu tvrdíš?

Ano můžu. Pro celočíselné x to vrací vždy stejný výsledek.

[Tuxik]

No jo, to je mi ale překvapení... já se tedy k těm bechmarkům taky přidám a zkusíme použít posun v takovém případě, aby měl opravdu smysl a nemusel kvůli tomu dělat dvě operace místo jedné, ju?

Kód: [Vybrat]

>>> timeit("""x=0\nfor i in range(10000):x = ((x << 3) + 1) >> 3""", number=10000)
15.1547691822052
>>> timeit("""x=0\nfor i in range(10000):x = ((x * 8) + 1)//8""", number=10000)
20.367625951766968
Týýý jo, to jsem nečekal :O

[gl]

Kód: [Vybrat]

>>> timeit('2 ** 10',number=10**9)
22.888786771014566
>>> timeit('1 << 10',number=10**9)
22.891730467992602


[Tuxik]

Kód: [Vybrat]

>>> timeit('2 ** 10',number=10**9)
22.888786771014566
>>> timeit('1 << 10',number=10**9)
22.891730467992602


nečekáš, že to něco opravdu počítá, že ne?

[Tuxik]

Kód: [Vybrat]

>>> timeit('x=2;x ** 10',number=10**8)
55.42527198791504
>>> timeit('x=1;x << 10',number=10**8)
15.809034824371338

edit, omlouvám se, server něco v té době dělal, toto je přiměřenější výsledek:

Kód: [Vybrat]

>>> timeit('x=2;x ** 10',number=10**8)
18.263038873672485
>>> timeit('x=1;x << 10',number=10**8)
8.662003993988037


[gamer]

Ano můžu. Pro celočíselné x to vrací vždy stejný výsledek.

Ne nemůžeš, protože nevíš, jakého je x typu. Stejnou chybu jsi udělal už tady a bohužel jsi to pořád nepochopil:
http://forum.root.cz/index.php?topic=13803.msg177901#msg177901
chtěl jsi nahradit

Kód: [Vybrat]

x = np.arange(0, N * (1 << J), dtype=float) / (1 << J)
tímto:

Kód: [Vybrat]

x = np.arange(0, N * 2 ** J, dtype=float) / (2 ** J)

ale to NESMÍŠ, protože ten kód ROZBIJEŠ. Z funkčního kódu jsi udělal kód nefunkční. To J tam chodí zvenku:
https://github.com/scipy/scipy/blob/master/scipy/signal/wavelets.py#L96
a MUSÍ to být integer. Tady nejde o žádné optimalizace rychlosti, tady jde o to, že operátory << a ** NELZE jen tak zaměňovat. Zkus se nad tím prosím zamyslet. Je smutné, když programátor rozbije fukční kód jen proto, že něco nepochopil.