Логарифмическая математическая операция в Solidity

Каков наиболее эффективный способ вычисления логарифма в целостности? Есть ли библиотека, которая реализует ее или встроенную функцию?

4 голоса | спросил Doug King 17 AM00000030000001831 2016, 03:46:18

7 ответов


5

Хотя нет текущей реализации (и я не видел ее в dapp-bin либо), вы можете реализовать свои собственные, используя Серия Тейлора , как было предложено Vitalik в этот старый поток Reddit.

Для примера в потоке он эффективно сводится к следующему:

 x = msg.data[0]
 LOG = 0
 while x >= 1500000:
     LOG = LOG + 405465
     x = x * 2 / 3
 x = x - 1000000
 y = x
 i = 1
 while i < 10:
      LOG = LOG + (y / i)
      i = i + 1
      y = y * x / 1000000
      LOG = LOG - (y / i)
      i = i + 1
      y = y * x / 1000000
return(LOG)

Учитывайте количество шагов и связанные с этим расходы на газ ...

ответил Richard Horrocks 17 PM00000080000005731 2016, 20:52:57
7

Вот очень эффективный (<700 газ) способ расчета потолка log_2:

function log2(uint x) returns (uint y){
   assembly {
        let arg := x
        x := sub(x,1)
        x := or(x, div(x, 0x02))
        x := or(x, div(x, 0x04))
        x := or(x, div(x, 0x10))
        x := or(x, div(x, 0x100))
        x := or(x, div(x, 0x10000))
        x := or(x, div(x, 0x100000000))
        x := or(x, div(x, 0x10000000000000000))
        x := or(x, div(x, 0x100000000000000000000000000000000))
        x := add(x, 1)
        let m := mload(0x40)
        mstore(m,           0xf8f9cbfae6cc78fbefe7cdc3a1793dfcf4f0e8bbd8cec470b6a28a7a5a3e1efd)
        mstore(add(m,0x20), 0xf5ecf1b3e9debc68e1d9cfabc5997135bfb7a7a3938b7b606b5b4b3f2f1f0ffe)
        mstore(add(m,0x40), 0xf6e4ed9ff2d6b458eadcdf97bd91692de2d4da8fd2d0ac50c6ae9a8272523616)
        mstore(add(m,0x60), 0xc8c0b887b0a8a4489c948c7f847c6125746c645c544c444038302820181008ff)
        mstore(add(m,0x80), 0xf7cae577eec2a03cf3bad76fb589591debb2dd67e0aa9834bea6925f6a4a2e0e)
        mstore(add(m,0xa0), 0xe39ed557db96902cd38ed14fad815115c786af479b7e83247363534337271707)
        mstore(add(m,0xc0), 0xc976c13bb96e881cb166a933a55e490d9d56952b8d4e801485467d2362422606)
        mstore(add(m,0xe0), 0x753a6d1b65325d0c552a4d1345224105391a310b29122104190a110309020100)
        mstore(0x40, add(m, 0x100))
        let magic := 0x818283848586878898a8b8c8d8e8f929395969799a9b9d9e9faaeb6bedeeff
        let shift := 0x100000000000000000000000000000000000000000000000000000000000000
        let a := div(mul(x, magic), shift)
        y := div(mload(add(m,sub(255,a))), shift)
        y := add(y, mul(256, gt(arg, 0x8000000000000000000000000000000000000000000000000000000000000000)))
    }  
}
ответил Tjaden Hess 8 32017vEurope/Moscow11bEurope/MoscowWed, 08 Nov 2017 09:39:22 +0300 2017, 09:39:22
4

Вот высокоточная реализация ln (x) для 128.128 чисел с фиксированной точкой:

/**
 * 2^127.
 */
uint128 private constant TWO127 = 0x80000000000000000000000000000000;

/**
 * 2^128 - 1.
 */
uint128 private constant TWO128_1 = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF;

/**
 * ln(2) * 2^128.
 */
uint128 private constant LN2 = 0xb17217f7d1cf79abc9e3b39803f2f6af;

/**
 * Return index of most significant non-zero bit in given non-zero 256-bit
 * unsigned integer value.
 *
 * @param x value to get index of most significant non-zero bit in
 * @return index of most significant non-zero bit in given number
 */
function mostSignificantBit (uint256 x) pure internal returns (uint8) {
  require (x > 0);

  uint8 l = 0;
  uint8 h = 255;

  while (h > l) {
    uint8 m = uint8 ((uint16 (l) + uint16 (h)) >> 1);
    uint256 t = x >> m;
    if (t == 0) h = m - 1;
    else if (t > 1) l = m + 1;
    else return m;
  }

  return h;
}

/**
 * Calculate log_2 (x / 2^128) * 2^128.
 *
 * @param x parameter value
 * @return log_2 (x / 2^128) * 2^128
 */
function log_2 (uint256 x) pure internal returns (int256) {
  require (x > 0);

  uint8 msb = mostSignificantBit (x);

  if (msb > 128) x >>= msb - 128;
  else if (msb < 128) x <<= 128 - msb;

  x &= TWO128_1;

  int256 result = (int256 (msb) - 128) << 128; // Integer part of log_2

  int256 bit = TWO127;
  for (uint8 i = 0; i < 128 && x > 0; i++) {
    x = (x << 1) + ((x * x + TWO127) >> 128);
    if (x > TWO128_1) {
      result |= bit;
      x = (x >> 1) - TWO127;
    }
    bit >>= 1;
  }

  return result;
}

/**
 * Calculate ln (x / 2^128) * 2^128.
 *
 * @param x parameter value
 * @return ln (x / 2^128) * 2^128
 */
function ln (uint256 x) pure internal returns (int256) {
  require (x > 0);

  int256 l2 = log_2 (x);
  if (l2 == 0) return 0;
  else {
    uint256 al2 = uint256 (l2 > 0 ? l2 : -l2);
    uint8 msb = mostSignificantBit (al2);
    if (msb > 127) al2 >>= msb - 127;
    al2 = (al2 * LN2 + TWO127) >> 128;
    if (msb > 127) al2 <<= msb - 127;

    return int256 (l2 >= 0 ? al2 : -al2);
  }
}
ответил Mikhail Vladimirov 9 SatEurope/Moscow2017-12-09T10:40:11+03:00Europe/Moscow12bEurope/MoscowSat, 09 Dec 2017 10:40:11 +0300 2017, 10:40:11
0

Меня интересовал 2log: Итак, первая делает практически то же самое, что и выше. Но другой выполняет двоичный поиск в логарифмическом значении в [0,256]. Стоимость газа последнего очень постоянна. Стоимость газа первого кажется довольно линейной по сравнению с выходом. Лучше всего было бы выполнять бинарный поиск с определенной точностью, а затем, возможно, заканчивая простым поиском.

    function findLogSimple(uint b) returns (uint){
        for(uint i=0;2**i<=b;i++){}
        return i-1;
    }
    function findLogBinarySearch(uint b) returns (uint){
        uint up = 256;
        uint down = 0;
        uint attempt = (up+down)/2;
        while (up>down+1){
            if(b>=(2**attempt)){
                down=attempt;
            }else{
                up=attempt;
            }
            attempt=(up+down)/2;
        }
        return attempt;
    }

И даже немного лучше - это смесь двух:

function findLogMix(uint b) returns (uint){
    //if(b==0){return 0;}
    uint up = 256;
    uint down = 0;
    uint attempt = (up+down)/2;
    while (up>down+4){
        if(b>=(2**attempt)){
            down=attempt;
        }else{
            up=attempt;
        }
        attempt=(up+down)/2;
    }
uint temp = 2**down;
while(temp<=b){
    down++;
    temp=temp*2;
}
return down;
}
ответил Harm Campmans 2 FebruaryEurope/MoscowbThu, 02 Feb 2017 14:34:29 +0300000000pmThu, 02 Feb 2017 14:34:29 +030017 2017, 14:34:29
0

Вычислить наибольшее целое число, меньшее или равное двоичному логарифму заданного ввода:

uint256 constant ONE = 1;

function floorLog(uint256 n) pure returns (uint8) {
    uint8 res = 0;

    if (n < 256) {
        // At most 8 iterations
        while (n > 1) {
            n >>= 1;
            res += 1;
        }
    }
    else {
        // Exactly 8 iterations
        for (uint8 s = 128; s > 0; s >>= 1) {
            if (n >= (ONE << s)) {
                n >>= s;
                res |= s;
            }
        }
    }

    return res;
}

Вычислить двоичный логарифм данного ввода, увеличенный с помощью PRECISION bits:

uint8 constant PRECISION = 127;
uint256 constant FIXED_1 = 0x080000000000000000000000000000000; // (1<<(PRECISION)
uint256 constant FIXED_2 = 0x100000000000000000000000000000000; // (2<<(PRECISION)
uint256 constant MAX_NUM = 0x1ffffffffffffffffffffffffffffffff; // (1<<(256-PRECISION))-1

function log(uint256 numerator, uint256 denominator) pure returns (uint256) {
    uint256 res = 0;

    assert(numerator <= MAX_NUM);
    uint256 x = numerator * FIXED_1 / denominator;

    // If x >= 2, then we compute the integer part of log2(x), which is larger than 0.
    if (x >= FIXED_2) {
        uint8 count = floorLog(x / FIXED_1);
        x >>= count; // now x < 2
        res = count * FIXED_1;
    }

    // If x > 1, then we compute the fraction part of log2(x), which is larger than 0.
    if (x > FIXED_1) {
        for (uint8 i = PRECISION; i > 0; --i) {
            x = (x * x) / FIXED_1; // now 1 < x < 4
            if (x >= FIXED_2) {
                x >>= 1; // now 1 < x < 2
                res += ONE << (i - 1);
            }
        }
    }

    return res;
}

Несколько заметок о функции выше:

  • Он возвращает floor(log(numerator/denominator)*2^PRECISION)
  • Оба входных значения должны находиться между 1 и 2^(256-PRECISION)-1
  • Выходное значение находится между 0 и floor(log(2^(256-PRECISION)-1)*2^PRECISION)
  • Он предполагает numerator >= denominator, потому что результат будет отрицательным в противном случае

Вычислить натуральный логарифм заданного входного сигнала, увеличенный до PRECISION bits:

uint256 private constant LOG_NUMERATOR   = 0x3f80fe03f80fe03f80fe03f80fe03f8;
uint256 private constant LOG_DENOMINATOR = 0x5b9de1d10bf4103d647b0955897ba80;
function ln(uint256 numerator, uint256 denominator) pure returns (uint256) {
    return log(numerator, denominator) * LOG_NUMERATOR / LOG_DENOMINATOR;
}

Обратите внимание, что все приведенные выше значения констант должны вычисляться в соответствии со значением PRECISION.

Если вы произвольно сдвинете результат на биты PRECISION, вы получите приблизительное (целочисленное) приближение.

Если вы разделите его на 2 ^ PRECISION на калькуляторе, вы получите гораздо лучшее приближение.

Максимальное значение PRECISION безопасно для использования 127

ответил goodvibration 2 Jpm1000000pmTue, 02 Jan 2018 17:36:13 +030018 2018, 17:36:13
0

Быстрая и нераспределенная реализация для вычисления потолка log2. Переведено с https://stackoverflow.com/questions/3272424/compute-fast-log- база-2-потолок

pragma solidity ^0.4.23;


library MathUtil {
  function ceilLog2(uint _x) pure internal returns(uint) {
    require(_x > 0);

    uint x = _x;
    uint y = (((x & (x - 1)) == 0) ? 0 : 1);
    uint j = 128;
    uint k = 0;

    k = (((x & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000000000000000000000) == 0) ? 0 : j);
    y += k;
    x >>= k;
    j >>= 1;

    k = (((x & 0xFFFFFFFFFFFFFFFF0000000000000000) == 0) ? 0 : j);
    y += k;
    x >>= k;
    j >>= 1;

    k = (((x & 0xFFFFFFFF00000000) == 0) ? 0 : j);
    y += k;
    x >>= k;
    j >>= 1;

    k = (((x & 0x00000000FFFF0000) == 0) ? 0 : j);
    y += k;
    x >>= k;
    j >>= 1;

    k = (((x & 0x000000000000FF00) == 0) ? 0 : j);
    y += k;
    x >>= k;
    j >>= 1;

    k = (((x & 0x00000000000000F0) == 0) ? 0 : j);
    y += k;
    x >>= k;
    j >>= 1;

    k = (((x & 0x000000000000000C) == 0) ? 0 : j);
    y += k;
    x >>= k;
    j >>= 1;

    k = (((x & 0x0000000000000002) == 0) ? 0 : j);
    y += k;
    x >>= k;
    j >>= 1;

    return y;
  }
}
ответил Saurfang 27 Mayam18 2018, 04:19:54
0

Я начал работать над математической библиотекой с фиксированной точкой для прочности. Это открытый исходный код (apache 2), и вам предлагается использовать и вносить свой вклад. Эта библиотека может решить вашу проблему, предоставив набор основных математических функций, таких как журнал, власть, корень и т. Д., Которые используют десятичные числа с фиксированной точкой, которые обычно используются для токенов ERC20 и автоматических маркет-мейкеров.

Пожалуйста, найдите здесь код: https://github.com/extraterrestrial-tech/fixidity

Сейчас у вас мало документации, поэтому, пожалуйста, свяжитесь со мной, если у вас есть вопросы.

ответил Gadi Guy 5 PM00000090000002331 2018, 21:11:23

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132