1 Тема від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 278
    • Репутація: 2720

Тема: Log(n, base:2) для цілих [ushort]

Маю інтриґуючу задачу: Написати функцію GetLog2, яка приймає число типу System.UInt16, в якому { поставлено 1 біт, решта нулі }, і вертає зміщеня відносно 1, тобто вертає степінь двійки. Приклади даних:

Input                : Output
0b_00000000_00000001 : 0b_0000
0b_00000000_00000010 : 0b_0001
0b_00000000_00000100 : 0b_0010
0b_00000000_00001000 : 0b_0011
0b_00000000_00010000 : 0b_0100
0b_00000000_00100000 : 0b_0101
0b_00000000_01000000 : 0b_0110
0b_00000000_10000000 : 0b_0111
0b_00000001_00000000 : 0b_1000
0b_00000010_00000000 : 0b_1001
0b_00000100_00000000 : 0b_1010
0b_00001000_00000000 : 0b_1011
0b_00010000_00000000 : 0b_1100
0b_00100000_00000000 : 0b_1101
0b_01000000_00000000 : 0b_1110
0b_10000000_00000000 : 0b_1111

Що фунція верне для всіх інших значень - не важливо. Ми будемо ґарантувати шо на вхід буде подано зміщену одиницю (не 0).
І заборонено користувати тип double, тобто кликати System.Math.Log(d) не можна.
Є така заготовка, якою можна перевірити чи реалізація добра:

public static int GetLog2(ushort v) {
    // тут має бути реалізація
    return _something_;
}
public static void PrintLog2Table() {
    const int n = 16;
    for(int i = 0; i < n; ++i) {
        int pow = 1 << i;
        int log = GetLog2((ushort)pow);
        Console.WriteLine(
            "i: {0,2}, Pow2: {1,10}, Log2: {2,2} {3} {0,2};"
            , i, pow, log, log == i ? "==" : "!="
        );
        if(log != i) throw new Exception();
    }
}

Покишо я зробив код, який легко маштабувати для інших типів:

public static int GetLog2(ushort v) {
    return (int)(
        ((v & 0xFF00u) / v) << 3 |
        ((v & 0xF0F0u) / v) << 2 |
        ((v & 0xCCCCu) / v) << 1 |
        ((v & 0xAAAAu) / v)
    );
}

Але в даному випадку треба максимально тиснути на швидкість виконаня і дешеві оператори.
Ходить легенда, шо ці 4 діленя (/) можна замінити на 1 множеня (*). Як?: ще шукаю.

leofun01 вебсайт

2 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 278
    • Репутація: 2720

Re: Log(n, base:2) для цілих [ushort]

Дяка ReAl, знайшов шось дуже подібне на те шо я маю написати: Log2 за час O(log(N)), де N - кількість бітів числа.
Але масиви користувати теж не можна, тому буду пробувати магічні константи (ulong) замість них.

leofun01 вебсайт

3 Відповідь від koala Востаннє редагувалося koala (25.04.2024 23:28:27)

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Log(n, base:2) для цілих [ushort]

А ви не це хочете переписати? https://learn.microsoft.com/uk-ua/dotne … etcore-3.0
Воно, правда, не CLS-compliant... щоб воно не значило.
У будь-якому разі, (v-1) буде складатися з одиничок. А рахувати одинички - дуже проста операція без жодного ділення, якраз O(log(кількість біт)). Але щось мені підказує, що можна ще швидше.

Подякували: leofun011

koala вебсайт

4 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Log(n, base:2) для цілих [ushort]

Є така штука, як ідеальна геш-функція. Якщо чесно, я знайомий лише теоретично із загальною ідеєю, тому, мабуть, це трохи наївний підхід і можна краще з різних боків, але (Python):

def hash(n):
    n1 = n & 0xF
    n2 = (n >> 4) & 0xF
    n3 = (n >> 8) & 0xF
    n4 = (n >> 12) & 0xF
    s = n1 + n2 + n3 + n4
    return (s & 0xF) + (( s>>4 ) << 1)

def int_log_of_pow2(n):
    return [0,1,5,2,6,10,14,3,7,11,15,-1,-1,-1,-1,4,8,9,13][hash(n-1)]

if __name__ == "__main__":
    import math
    for i in range(16):
        p2 = 2**i
        assert int_log_of_pow2(p2) == math.log2(p2)
Подякували: leofun011

koala вебсайт

5 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Log(n, base:2) для цілих [ushort]

Або ж просто робіть щось на кшталт

((v & 0xFF00u) == 0 ? 0 : 1) << 3

Порівняння має бути дешевшим за ділення.

Подякували: leofun011

koala вебсайт

6 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Log(n, base:2) для цілих [ushort]

Глянув вранці - так треба ж

    return (int)(
        ((v & 0xFF00u) == 0 ? 0 : 8) |
        ((v & 0xF0F0u) == 0 ? 0 : 4) |
        ((v & 0xCCCCu) == 0 ? 0 : 2) |
        ((v & 0xAAAAu) == 0 ? 0 : 1)
    );

Ну, чи через if-и

int result = 0;
if(v & 0xFF00u != 0) result |= 8;
...

   
Хоча, звісно, це треба тестувати. Оптимізація без бенчмарка - гроші на вітер.

Подякували: leofun011

koala вебсайт

7 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 278
    • Репутація: 2720

Re: Log(n, base:2) для цілих [ushort]

Досліджую геш-функції, бо щось подібне потім теж маю писати.

koala написав:
def int_log_of_pow2(n):
    return [0,1,5,2,6,10,14,3,7,11,15,-1,-1,-1,-1,4,8,9,13][hash(n-1)]

Тут автор коду загубив 12. Або автор коду хотів показати саму ідею, без реалізації, тоді ок, тоді про -1,-1,-1,-1 теж питань не буде. Ідею вловив.

koala написав:

А ви не це хочете переписати? https://learn.microsoft.com/uk-ua/dotne … etcore-3.0
Воно, правда, не CLS-compliant... щоб воно не значило.

Так, здається це воно. Тільки тип числа в мене трохи менший, через що я майже впевнений, шо це можна зробити ше швидше.
А CLS-compliant це сумісність між мовами. В цьому топіку не важливо чи буде воно CLS-compliant, розглядаємо всі варіанти. Все одно тип ushort сам є не CLS-compliant.

koala написав:

У будь-якому разі, (v-1) буде складатися з одиничок. А рахувати одинички - дуже проста операція без жодного ділення, якраз O(log(кількість біт)). Але щось мені підказує, що можна ще швидше.

Ага, мене теж мучить ця ідея. А ше коли хтось в колективі ляпне про можливість O(log(log(N))) або O(1), то потім весь тиждень пропадає.

leofun01 вебсайт

8 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Log(n, base:2) для цілих [ushort]

Автор коду зрозумів, що не розуміє, як працюють Pythonівські assertи.

Подякували: leofun011

koala вебсайт

9 Відповідь від koala Востаннє редагувалося koala (26.04.2024 10:00:19)

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Log(n, base:2) для цілих [ushort]

leofun01 написав:

Так, здається це воно. Тільки тип числа в мене трохи менший, через що я майже впевнений, шо це можна зробити ше швидше.

Треба тестувати. Бо воно, напевно, на якихось специфічних інструкціях процесора зроблено. BSR/CLZ/щось таке. А комбінацією інструкцій ви одну навряд чи переженете.

Подякували: leofun01, Tarpan872

koala вебсайт

10 Відповідь від leofun01 Востаннє редагувалося leofun01 (26.04.2024 13:19:46)

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 278
    • Репутація: 2720

Re: Log(n, base:2) для цілих [ushort]

Нова інфо: Щоб підняти перформанс, можна на функцію додати атрибут MethodImplAttribute.

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int GetLog2(ushort v) { ... }

Це добре працює для однорядкових функцій, але не всюди і не завжди, тоді можна давати опцію AggressiveOptimization

[MethodImpl(MethodImplOptions.AggressiveOptimization)]
public static int GetLog2(ushort v) { ... }
koala написав:

Треба тестувати. Бо воно, напевно, на якихось специфічних інструкціях процесора зроблено. BSR/CLZ/щось таке.

Знайшов їхню реалізацію System/Numerics/BitOperations.cs (гілка:main, дата:2024-04-26, стрічка: 380), зробити швидше шанси є, хоть і примарні. Пробую, тестую.

(стрічку попутав, оновив номер)

leofun01 вебсайт

11 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 278
    • Репутація: 2720

Re: Log(n, base:2) для цілих [ushort]

А, ні, шансів не є. Див.рядок #277 :

public static int Log2(uint value)
{
    // ...
    if (Lzcnt.IsSupported)
    {
        return 31 ^ (int)Lzcnt.LeadingZeroCount(value);
    }
    // ...
}

На цьому кінець. Можна вважати питаня закритим.

leofun01 вебсайт

12 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Log(n, base:2) для цілих [ushort]

Зверніть там увагу ще на Log2SoftwareFallback.

Подякували: leofun011

koala вебсайт

13 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 278
    • Репутація: 2720

Re: Log(n, base:2) для цілих [ushort]

koala написав:

Зверніть там увагу ще на Log2SoftwareFallback.

Звернув, гарно.

dotnetfoundation.org написав:
private static int Log2SoftwareFallback(uint value)
{
    // No AggressiveInlining due to large method size
    // Has conventional contract 0->0 (Log(0) is undefined)

    // Fill trailing zeros with ones, eg 00010010 becomes 00011111
    value |= value >> 01;
    value |= value >> 02;
    value |= value >> 04;
    value |= value >> 08;
    value |= value >> 16;

    // uint.MaxValue >> 27 is always in range [0 - 31] so we use Unsafe.AddByteOffset to avoid bounds check
    return Unsafe.AddByteOffset(
        // Using deBruijn sequence, k=2, n=5 (2^5=32) : 0b_0000_0111_1100_0100_1010_1100_1101_1101u
        ref MemoryMarshal.GetReference(Log2DeBruijn),
        // uint|long -> IntPtr cast on 32-bit platforms does expensive overflow checks not needed here
        (IntPtr)(int)((value * 0x07C4ACDDu) >> 27));
}

leofun01 вебсайт

14 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 278
    • Репутація: 2720

Re: Log(n, base:2) для цілих [ushort]

Це шо, я лишив топік без рішеня .. *NO* Виправляйемо цю ганебну ситуацію.

Власну версію таки довелось писати, бо замовник не буде зносити систему і ставити іншу тільки для того шоб чиясь програма працювала. А там фреймворк трохи старіший, бібліотеки класу System.Numerics.BitOperations просто не є. І я радий шо замовник не прогнувся під контору і чітко описав в яких середовищах маємо тестувати програму.

Перша версія була достаньо робоча щоб пройти тести для unsigned

public static int GetLog2(ushort v) {
    return (int)(0xCD7EA84FB6935210uL >> (((0x09AF * v) >> 10) & 0x3C)) & 0x0F;
}

, але для signed там була проблема. Треба було зняти старший біт з довгої константи.
То я зробив другу версію

public static int GetLog2(ushort v) {
    return (int)(0x45697DAF38CE2B10L >> (((0x0F65 * v) >> 10) & 0x3C)) & 0x0F;
}

, там все файно працює, і код легко переносити для short.

Якщо на вхід йде значеня будь-яке (більше ніж 1 біт), то можна робити приведеня до 1 біт

public static ushort GetHighestBitOr1(ushort v) {
    v |= (ushort)(v >> 1);
    v |= (ushort)(v >> 2);
    v |= (ushort)(v >> 4);
    v |= (ushort)(v >> 8);
    return (ushort)((v >> 1) + 1u);
}
public static int GetLog2(ushort v) {
    v = GetHighestBitOr1(v);
    return (int)(0x45697DAF38CE2B10L >> (((0x0F65 * v) >> 10) & 0x3C)) & 0x0F;
}

leofun01 вебсайт

15 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 278
    • Репутація: 2720

Re: Log(n, base:2) для цілих [ushort]

Я зґенерив всі послідовності для швидкого Log2 (для UInt16). Берете будь-який з цих рядків і отримуйете правильний результат

public static int GetLog2_16(ushort v) {
        v = GetHighestBit(v);
    //  return (int)(0xCD7EA84FB6935210uL >> (((0x09AF * v) >> 10) & 0x3C)) & 0x0F;
    //  return (int)(0x789ECA4F6DB35210L  >> (((0x09EB * v) >> 10) & 0x3C)) & 0x0F;
    //  return (int)(0xCD9EA46FB8357210uL >> (((0x0A6F * v) >> 10) & 0x3C)) & 0x0F;
    //  return (int)(0x9ABEC46F8D357210uL >> (((0x0A7B * v) >> 10) & 0x3C)) & 0x0F;
    //  return (int)(0xABC64D7F953E8210uL >> (((0x0B3D * v) >> 10) & 0x3C)) & 0x0F;
    //  return (int)(0xCD6E479FB538A210uL >> (((0x0B4F * v) >> 10) & 0x3C)) & 0x0F;
    //  return (int)(0x67C84D9F5B3EA210L  >> (((0x0BCD * v) >> 10) & 0x3C)) & 0x0F;
    //  return (int)(0x678E49BF5D3AC210L  >> (((0x0BD3 * v) >> 10) & 0x3C)) & 0x0F;
    //  return (int)(0xABC48D5F937E2610uL >> (((0x0CBD * v) >> 10) & 0x3C)) & 0x0F;
    //  return (int)(0xCD4EA57FB3962810uL >> (((0x0D2F * v) >> 10) & 0x3C)) & 0x0F;
    //  return (int)(0x9A4B75CF836E2D10uL >> (((0x0D79 * v) >> 10) & 0x3C)) & 0x0F;
    //  return (int)(0x78495DAF63CE2B10L  >> (((0x0DE5 * v) >> 10) & 0x3C)) & 0x0F;
    //  return (int)(0x45C6AD7F3B9E2810L  >> (((0x0F2D * v) >> 10) & 0x3C)) & 0x0F;
    //  return (int)(0x456EC79F3DB82A10L  >> (((0x0F4B * v) >> 10) & 0x3C)) & 0x0F;
    //  return (int)(0x456B97CF3A8E2D10L  >> (((0x0F59 * v) >> 10) & 0x3C)) & 0x0F;
        return (int)(0x45697DAF38CE2B10L  >> (((0x0F65 * v) >> 10) & 0x3C)) & 0x0F;
}
public static ushort GetHighestBit(ushort v) {
        v |= (ushort)(v >> 1);
        v |= (ushort)(v >> 2);
        v |= (ushort)(v >> 4);
        v |= (ushort)(v >> 8);
        return (ushort)((v >> 1) ^ v);
    //  return (ushort)(v - (v >> 1));
}

Всі версії тут конвенційні, тобто "in: 0 -> out: 0" ґарантований.

leofun01 вебсайт