[Function] GetNumberOfDigits [Архив] - Pro Pawn - Портал о PAWN-скриптинге

Просмотр полной версии : [Function] GetNumberOfDigits

VVWVV

10.12.2016, 08:08

Описание:

Вычисляет длину числа. Данная функция может работать с отрицательными и положительными числами.

Параметры:

number - число

Возвращаемое значение:

Возвращает длину числа.

Плюсы реализации:

Быстрое вычисление длины числа (тесты (http://pro-pawn.ru/showthread.php?15648#post87737)).

Код:
Реализация с использованием __emit (требуется компилятор версии 3.10.6 или новее):

stock GetNumberOfDigits(number)
{ // by Daniel_Cortez \\ pro-pawn.ru
__emit
{
load.s.pri number
zero.alt
jsgeq check1
move.alt
eq.c.pri cellmin
add
neg
check1:
const.alt 1_000_000
jsgeq check2
const.alt 100
jsgeq check1_2
const.alt 10
sgeq
inc.pri
retn
check1_2:
const.alt 10_000
jsgeq check1_3
const.alt 1_000
sgeq
add.c 3
retn
check1_3:
const.alt 100_000
sgeq
add.c 5
retn
check2:
const.alt 100_000_000
jsgeq check3
const.alt 10_000_000
sgeq
add.c 7
retn
check3:
const.alt 1_000_000_000
sgeq
}
return __emit add.c 9;
}

Реализация без __emit (подходит для более старых версий компилятора, но работает медленнее):

stock GetNumberOfDigits(number)
{ // by Daniel_Cortez \\ pro-pawn.ru
if (number < 0)
number = -(number + _:(number == cellmin));
if (number < 100_000)
{
if (number < 100)
return 1 + _:(number >= 10);
if (number < 10_000)
return 3 + _:(number >= 1_000);
return 5;
}
if (number < 10_000_000)
return 6 + _:(number >= 1_000_000);
if (number < 1_000_000_000)
return 8 + _:(number >= 100_000_000);
return 10;
}

Пример использования:

main()
{
// Выведет только 10
printf("%d", GetNumberOfDigits(1000000000));
}

См. также:

[Function] frandom (http://pro-pawn.ru/showthread.php?14124)
[Function] GetNums (http://pro-pawn.ru/showthread.php?14074)

Автор: Daniel_Cortez (http://pro-pawn.ru/member.php?100-Daniel_Cortez)

Исключительно для pro-pawn.ru

Копирование данной статьи на других ресурсах без разрешения автора запрещено.

Daniel_Cortez

10.12.2016, 08:48

VVWVV

10.12.2016, 09:00

ИМХО, было бы корректнее использовать название "GetNumberDecimalDigits" или "GetNumberDecimalPositions". Слово "Size" в названиях обычно используют, когда функция возвращает размер чего-то: массива или активных ячеек в пуле (pool (https://en.wikipedia.org/wiki/Pool_(computer_science))), поэтому название "GetNumberSize" звучит контринтуитивно.

Да, наверное. Дабы не запоминать большие названия можно воспользоваться вариантом "GetNumberOfDigits". Я же опирался на быстроту написания, а также на читаемость в коде.

VVWVV

05.10.2017, 17:17

Обновил реализацию функции.

MassonNN

19.12.2019, 23:20

какой смысл в return 10, если максимальное положительное значение int это 2147483647
(я могу ошибаться и сто процентов ошибаюсь, поэтому и пишу)

DeimoS

20.12.2019, 02:12

какой смысл в return 10, если максимальное положительное значение int это 2147483647
(я могу ошибаться и сто процентов ошибаюсь, поэтому и пишу)

Эмм, ну так посчитай количество символов в числе "2.147.483.647".
Максимальное число, отсекаемое условием:
if (number < 1_000_000_000)
и 2147483647 в него не входит. Тогда и будет возвращено 10.

Daniel_Cortez

21.12.2019, 14:20

Решил немного поэкспериментировать с оператором __emit, получилось следующее:

stock GetNumberOfDigits(number)
{
__emit
{
load.s.pri number
zero.alt
jsgeq check1
move.alt
eq.c.pri cellmin
add
neg
check1:
const.alt 1_000_000
jsgeq check2
const.alt 100
jsgeq check1_2
const.alt 10
sgeq
inc.pri
retn
check1_2:
const.alt 10_000
jsgeq check1_3
const.alt 1_000
sgeq
add.c 3
retn
check1_3:
const.alt 100_000
sgeq
add.c 5
retn
check2:
const.alt 100_000_000
jsgeq check3
const.alt 10_000_000
sgeq
add.c 7
retn
check3:
const.alt 1_000_000_000
sgeq
}
return __emit add.c 9;
}

Если хотите самостоятельно перепроверить корректность функции, то вот тест, который проверяет работу функции на всех возможных в Pawn целочисленных значениях (включая предельные cellmin и cellmax):

Test(min, max, num)
{
static i;
printf("testing %d..%d ...", min, max);
i = min;
do {
if (GetNumberOfDigits(i) != num)
printf("Error: %d -> %d", i, GetNumberOfDigits(i));
if (i == cellmax)
break;
} while (i != cellmax && ++i <= max);
print("... Done!");
}

main()
{
Test(cellmin, -1000000000, 10);
Test(-999999999, -100000000, 9);
Test(-99999999, -10000000, 8);
Test(-9999999, -1000000, 7);
Test(-999999, -100000, 6);
Test(-99999, -10000, 5);
Test(-9999, -1000, 4);
Test(-999, -100, 3);
Test(-99, -10, 2);
Test(-9, 9, 1);
Test(10, 99, 2);
Test(100, 999, 3);
Test(1000, 9999, 4);
Test(10000, 99999, 5);
Test(100000, 999999, 6);
Test(1000000, 9999999, 7);
Test(10000000, 99999999, 8);
Test(100000000, 999999999, 9);
Test(1000000000, cellmax, 10);
}

И тесты производительности (примечание: в варианты от DeimoS'а и VVWVV я добавил проверку на cellmin, чтобы уравнять их в корректности работы):

/*======== Настройки =========================================================*/
#include <float>

const PROFILER_ITERATIONS_MAJOR = 1_000;//100_000;
const PROFILER_ITERATIONS_MINOR = 1_000;//10;

new const code_snippets_names[5][] =
{
{"VVWVV"},
{"DeimoS(1)"},
{"DeimoS(2)"},
{"Daniel_Cortez"},
{"Daniel_Cortez (__emit)"}
};

stock GetNumberOfDigits_VVWVV({Float,_}:number)
{
return number != 0 ? floatround(floatlog(floatabs(number))) + 1 : 1;
}

stock GetCountsOfDigits_DeimoS(number)
{
if (number < 0)
number = -(number + _:(number == cellmin));
if (number < 100_000)
{
if(number < 100)
{
if(number < 10)
return 1;
else
return 2;
}
else
{
if(number < 1_000)
return 3;
else
{
if(number < 10_000)
return 4;
else
return 5;
}
}
}
else
{
if(number < 10_000_000)
{
if(number < 1_000_000)
return 6;
else
return 7;
}
else
{
if(number < 100_000_000)
return 8;
else
{
if(number < 1_000_000_000)
return 9;
else
return 10;
}
}
}
}

stock GetCountsOfDigits_DeimoS2(number)
{
if(number < 0)
{
if (number > -100_000)
{
if (number > -100)
return 1 + _:(number <= -10);
if (number > -10_000)
return 3 + _:(number <= -1_000);
return 5;
}
if (number > -10_000_000)
return 6 + _:(number <= -1_000_000);
if (number > -1_000_000_000)
return 8 + _:(number <= -100_000_000);
return 10;
}
else
{
if (number < 100_000)
{
if (number < 100)
return 1 + _:(number >= 10);
if (number < 10_000)
return 3 + _:(number >= 1_000);
return 5;
}
if (number < 10_000_000)
return 6 + _:(number >= 1_000_000);
if (number < 1_000_000_000)
return 8 + _:(number >= 100_000_000);
return 10;
}
}

stock GetNumberOfDigits_DC(number)
{
if (number < 0)
number = -(number + _:(number == cellmin));
if (number < 100_000)
{
if (number < 100)
return 1 + _:(number >= 10);
if (number < 10_000)
return 3 + _:(number >= 1_000);
return 5;
}
if (number < 10_000_000)
return 6 + _:(number >= 1_000_000);
if (number < 1_000_000_000)
return 8 + _:(number >= 100_000_000);
return 10;
}

stock GetNumberOfDigits_DC__emit(number)
{
__emit
{
load.s.pri number
zero.alt
jsgeq check1
move.alt
eq.c.pri cellmin
add
neg
check1:
const.alt 1_000_000
jsgeq check2
const.alt 100
jsgeq check1_2
const.alt 10
sgeq
inc.pri
retn
check1_2:
const.alt 10_000
jsgeq check1_3
const.alt 1_000
sgeq
add.c 3
retn
check1_3:
const.alt 100_000
sgeq
add.c 5
retn
check2:
const.alt 100_000_000
jsgeq check3
const.alt 10_000_000
sgeq
add.c 7
retn
check3:
const.alt 1_000_000_000
sgeq
}
return __emit add.c 9;
}

// 0, -1, 2, -3, 4, -5, 6, -7, 8, -9, 10, -20, 30, ..., 1_000_000_000, -2_000_000_000
static numbers[9 * 9 + 3];

#define Prerequisites(); \
numbers[0] = 0; \
for (new i = 0, inc = 1, n = 1; i < 9; ++i, inc *= 10) \
for (new j = 1; j < 10; ++j, n += inc) \
numbers[i * 9 + j] = n * (((i * 9 + j) & 1) * -2 + 1); \
numbers[82] = 1_000_000_000; \
numbers[83] = -2_000_000_000; \
static i;

#define CodeSnippet0(); \
for (i = 0; i < sizeof(numbers); ++i) \
GetNumberOfDigits_VVWVV(numbers[i]);

#define CodeSnippet1(); \
for (i = 0; i < sizeof(numbers); ++i) \
GetCountsOfDigits_DeimoS(numbers[i]);

#define CodeSnippet2(); \
for (i = 0; i < sizeof(numbers); ++i) \
GetCountsOfDigits_DeimoS2(numbers[i]);

#define CodeSnippet3(); \
for (i = 0; i < sizeof(numbers); ++i) \
GetNumberOfDigits_DC(numbers[i]);

#define CodeSnippet4(); \
for (i = 0; i < sizeof(numbers); ++i) \
GetNumberOfDigits_DC__emit(numbers[i]);
/*======== Конец настроек ===================================================*/

Тестирование: 5 отрывков кода.
Режим: интерпретируемый, 1000x1000 итераций.
VVWVV: 51195
DeimoS(1): 21594
DeimoS(2): 19095
Daniel_Cortez: 20902
Daniel_Cortez (__emit): 15849

Тестирование: 5 отрывков кода.
Режим: с JIT-компиляцией, 1000x1000 итераций.
VVWVV: 16583
DeimoS(1): 1523
DeimoS(2): 1395
Daniel_Cortez: 1677
Daniel_Cortez (__emit): 1373
Number of vehicle models: 0

MassonNN

21.12.2019, 14:36

Интересно можно ли через emit узнать сколько битов забито числами и просто выдавать результат, или же это не реализуемо?

Daniel_Cortez

21.12.2019, 15:13

Интересно можно ли через emit узнать сколько битов забито числами и просто выдавать результат, или же это не реализуемо?
Кол-во установленных битов != кол-во цифр в числе.

MassonNN

21.12.2019, 16:21

Кол-во установленных битов != кол-во цифр в числе.

Ну подсчитать то можно, наверное?)))

Ещё есть такой вариант:

mov eax,10
cmp ecx,10^9
sbb eax,0
cmp ecx,10^8
sbb eax,0
....
cmp ecx,10^2
sbb eax,0
cmp ecx,10^1
sbb eax,0

ecx - число N, eax - количество цифр в числе.
1

Daniel_Cortez

21.12.2019, 17:48

Ну подсчитать то можно, наверное?)))
Между ними нет прямой связи.

Ещё есть такой вариант:

mov eax,10
cmp ecx,10^9
sbb eax,0
cmp ecx,10^8
sbb eax,0
....
cmp ecx,10^2
sbb eax,0
cmp ecx,10^1
sbb eax,0

ecx - число N, eax - количество цифр в числе.

Вот только виртуальная машина Pawn AMX оперирует... собственно, байткодом Pawn AMX, который не настолько гибок в сравнении с форматом x86. И если идея в том, чтобы повысить производительность кода за счёт избавления от ветвлений, то в AMX это сделать сложнее. Во-первых, нельзя так просто взять и сравнить два числа одной инструкцией: нужно загрузить одно число в регистр PRI, другое в регистр ALT, и только тогда сравнить их, что занимает в сумме 3 инструкции (единственное исключение здесь - инструкция "eq.c.pri/alt N"; ей можно сравнить предварительно загруженное в PRI число со значением "N", но так можно только проверить на равенство/неравенство, нам же нужно проверить на "больше или равно" или "меньше или равно"). Во-вторых, у виртуальной машины всего 2 регистра (PRI и ALT). После сравнения двух чисел свободных регистров не останется и поэтому перед следующим сравнением придётся заново загружать в PRI значение из переменной number, а перед этим ещё куда-то сохранить результат от предыдущих сравнений ("накопленное" количество цифр в числе). Всё это сводит на нет пользу от такой "оптимизации".

MassonNN

30.12.2019, 20:54

error 010: invalid function or declaration

кидает именно на
check1: