Округление по длине мантиссы

[mserg]

У меня есть вещественное число. Я хочу «урезать» мантиссу до заданного числа бит. Как это сделать? Требуется такое округление вверх и вниз. Есть подозрение, что нужно прямо колдовать над битами… Может, кто-нибудь проделывал такой фокус на С++?

Столь «странная» проблема возникла в задаче подбора аппроксимирующей функции минимальной длины. Двойное вещественное (64 бит) – слишком длинное; даже одинарное (32 бит) – тоже чрезмерно для данной задачи, и длина формулы получается неоправданно большой. Поэтому и возникла эта проблема…

[ewert]

mserg в сообщении #200769 писал(а):

аппроксимирующей функции минимальной длины.

А что это такое, т.е. в каком смысле она аппроксимирующая и что значит её длина?

Такой "странный" вопрос возник вот почему. Если аппроксимирующая функция -- короткая, то она даёт погрешность, значительно превышающую погрешность округления. Вы вроде как пытаетесь избежать этого, уменьшив разрядность. Но какая разница-то, каким способом получать эту погрешность?

[mserg]

Целевая функция при поиске формулы зависит от среднеквадратической ошибки и длины формулы. Функция растет с увеличением длины формулы и величины ошибки. Т.е. баланс ошибки и длины заложен в самой целевой функции. Не вдаваясь в подробности скажу, по вероятности, что чем короче формула, тем она надежнее.

На входе задачи:
* таблица данных (планирую до десятком миллионов записей); часть столбцов - аргументы функции, часть столбцов - значение(я).
* Набор "элементарных" функций, которые можно использовать для создания искомой формулы
* Форматы констант (целые, вещественные с указанием числа бит под мантиссу и порядок).
* Целевая функция (функционал), отражающая компромисс между точностью аппроксимации и длиной формулы.

Детали долго объяснять. Но вопрос то не в этом. Как округлить то?

[ewert]

да зачем округлять-то?...

Ну есть у Вас модель. И даёт она некоторую гарантированную погрешность. И как ни бейся -- ничего лучшего, чем она даёт, она не даст.

Ну округлите Вы её. Добавится к погрешности метода погрешность округления. Ну и что? В любом ведь случае общая ошибка лимитируется максимумом из погрешности метода и погрешности округления.

Наверное, я совершенно не понимаю, в чём вопрос-то.

[mserg]

Использование ограниченной разрядности для констант, конечно, дает некоторую
дополнительную погрешность. Но критерий использует ДЛИНУ формулы, т.е. размер
формулы в битах. Длина формулы (в том числе и точность представления входящих в нее
констант) находится в противоречии с точностью аппроксимации. Т.е. <округление>
является частью данного способа аппроксимации. Внутренний протест у Вас вызывает тот
факт, что в некоторых ситуациях константы представляются точно, а в других дают
погрешность из-за ограниченной точности представления. Ну что ж с этим можно
поделать? - так устроен мир.

Если Вы хотите использовать другую модель надежности формулы, основанной не на длине
формулы, либо учитывающие константы особым образом, - флаг Вам в руки. Если нет
реально работоспособной программы, реально подтверждающей идеи - то <все в сад>.

Ну, так чо, никто не округлял что ли?

P.S. Вообще, сколько пядей во лбу нужно иметь, чтобы придерживаться темы?

[Serge_BN]

mserg писал(а):

Использование ограниченной разрядности для констант, конечно, дает некоторую
дополнительную погрешность. Но критерий использует ДЛИНУ формулы

А что такое формула и что значит ее длина? И что это за критерий который смотрит не на число а на "длину формулы"

[mserg]

Длина формула - это количество бит, необходимое для ее записи.

Я не могу здесь заниматься восполнением пробелов в образовании. См. например, систему Easy NP и примеры по генетическому программированию к ней.

Если по округлению сказать нечего, просьба, сюда больше не писать.

[ewert]

mserg в сообщении #201078 писал(а):

P.S. Вообще, сколько пядей во лбу нужно иметь, чтобы придерживаться темы?

Трудно сказать. Для начала было бы полезно сформулировать саму тему. Пока же совершенно непонятно, чего Вы добиваетесь. Вот, к примеру, Вы жаловались на то, что, мол, четыре байта -- для Вас многовато. Но ведь это вопрос вовсе не чьего-то желания, а архитектуры процессора. Четыре байта -- это один из трёх или четырёх (точно не помню) стандартных форматов хранения чисел с плавающей точкой, причём минимальный. И ничего с этим не поделаешь.

[Serge_BN]

mserg писал(а):

Длина формула - это количество бит, необходимое для ее записи.

Воспользуйтесь std::set для представления ваших формул и std::map для отображений число - формула или наоборот формула - число.

[tolstopuz]

mserg писал(а):

У меня есть вещественное число. Я хочу «урезать» мантиссу до заданного числа бит. Как это сделать? Требуется такое округление вверх и вниз. Есть подозрение, что нужно прямо колдовать над битами… Может, кто-нибудь проделывал такой фокус на С++?

Есть простой алгоритм перевода числа в двоичную систему, использующий умножение на 2 и взятие целой части. Обычно ему учат либо школьников на кружке, либо младшекурсников.

[ewert]

Обрезать-то мантиссу нетрудно -- надо просто обнулить младшие биты, наложив соответствующую битовую маску. Непонятно лишь, какая от этого может быть практическая польза.

[Pavia]

mserg писал(а):

Столь «странная» проблема возникла в задаче подбора аппроксимирующей функции минимальной длины. Двойное вещественное (64 бит) – слишком длинное; даже одинарное (32 бит) – тоже чрезмерно для данной задачи, и длина формулы получается неоправданно большой. Поэтому и возникла эта проблема…

Сразу видно не правильный подход. 4 бата это не длинно вот килобайт или мегабайт это да. Но зачем это для аппроксимации ? А аппроксимация как раз и применяется для уменьшения данных. Но дело тут не в числе битов, а в числе множителей, элементов. Так как в практике редко когда используется выше 3 порядка. А если у вас сложная функция то можно использовать кусочное представление - сплайн.
Так что не понятно. Зачем нужно сокращать размер чисел. Скорость обработки при этом точно снизится причем на порядок, да и ошибка возрастет. Причем число бит связанно порой квадратично с числом элементов. Так что нарваться на ошибки вычисления становится проще.

Так как в погрешность в носиться на каждой операции вычисления то чем меньше этих вычислений тем лучше.
Но не стоит снижать разрядность чисел. Нужно снижать число операций.
Да число байт нужно снижать, но не зачет числа бит в числе, а за счет самого числа операндов. Просто порой обетом не говорят, а подразумевают.

[mserg]

Дааа... Мало того, что оффтопик, так еще и полная чушь. Но, не суть.

Я плоховато знаю C++, но получилось следующее:

#include <stdio.h>
#include <float.h>

__int64 mask[53];
double BiasEta;

void initrnd()
{
mask[52] = 0;
mask[51] = 1;
for (int i = 51; i--; i>0)
mask[i] = 2*mask[i+1];
for (int i = 52; i--; i>0)
mask[i] += mask[i+1];

double Current = 1+DBL_EPSILON;

do {
BiasEta = Current;
Current /= 2.0;
} while (Current > 0.0);

}

double predval (double x)
{
volatile double r;

_controlfp( _RC_DOWN, _MCW_RC );
r = x - BiasEta;
_controlfp( _RC_NEAR, _MCW_RC );
return r;
}

double round2down(double x, int p)
{
p--;
__int64* x_ = (__int64*)&x;
volatile double y;
__int64* y_ = (__int64*)&y;
if (x >= 0)
*y_ = *x_ & ~mask[p];
else
if (*x_ & mask[p])
{
*y_ = *x_ | mask[p];
y = predval(y);
}
else y = x;
return y;
}

double round2up(double x, int p)
{
return -round2down(-x,p);
}

int main()
{
initrnd();
double x = 2*7/3.0;
int p = 5;
printf("x=%.18g, p=%d, down(x)=%.18g, up(x)=%.18g\n", x, p, round2down(x,p),
round2up(x,p));
return 0;
}

Есть тут какой-нибудь изъян? Если есть, дайте плз. данные. Все на свете форматы меня не интересуют, хватит одного double из Microsoft Visual Studio.

Если вопрос создания математической модели по данным интересен, то можно создать отдельную тему. Но только для тех, кто хочет реально этим заниматься, а не "имеет мнение".

[Serge_BN]

mserg писал(а):

...полная чушь. Но, не суть.

#include <stdio.h>
#include <float.h>

__int64 mask[53];

void initmask()
{
mask[52] = 0;
mask[51] = 1;
for (int i = 51; i--; i>0)
mask[i] = 2*mask[i+1];
for (int i = 52; i--; i>0)
mask[i] += mask[i+1];
}

double succval (double x)
{
volatile double r;

_controlfp( _RC_UP, _MCW_RC );
r = x + DBL_EPSILON;
_controlfp( _RC_NEAR, _MCW_RC );
return r;
}

double round2down(double x, int p)
{
p--;
__int64* x_ = (__int64*)&x;
volatile double y;
__int64* y_ = (__int64*)&y;
if (x >= 0)
*y_ = *x_ & ~mask[p];
else
if (*x_ & mask[p])
{
*y_ = *x_ | mask[p];
y = succval(y);
}
else y = x;
return y;
}

double round2up(double x, int p)
{
return -round2down(-x,p);
}

int main()
{
initmask();
double x = 2*7/3.0;
int p = 1;
printf("x=%f, p=%d, down(x)=%f, up(x)=%f\n", x, p, round2down(x,p), round2up(x,p));
return 0;
}

Есть тут какой-нибудь изъян?

void initmask()
{
  mask[52] = 0;
  mask[51] = 1;
  for (int i = 51; i--; i>0)
    mask[i] = 2*mask[i+1];

постольку поскольку в 52-й ячейке массива 0, то весь массив будет заполен 0, кроме нулевой ячейки

  for (int i = 52; i--; i>0)
    mask[i] += mask[i+1];

берем то, что лежит за пределами массива и заполняем этим тот же массив????? опять таки кроме нулевой ячейки, что, впрочем сильно не отличается от того что в других ячейках

}

Я в генетическом программировании не понимаю, но какой великий смысл этой функции?
Далее

double round2down(double x, int p)
{
  p--;
  __int64* x_ = (__int64*)&x;
  volatile double y;
  __int64* y_ = (__int64*)&y;
  if (x >= 0) 

если указателю присвоен некий адрес, то указатель всегда будет больше нуля

*y_ = *x_ & ~mask[p];

в ячейке mask[0] лежит полная чушь,
и в далее мы вообще никогда не попадем.

  else 
    if (*x_ & mask[p])
    {
      *y_ = *x_ | mask[p];
      y = succval(y);
    }
    else y = x;
  return y;}

получим полную чушь с typesize = 64 бита

Это называется генетическим программированием???? Что-то я отстал от всех этих новшеств.

[mserg]

Serge_BN, большое спасибо. Но должен Вас разочаровать, я немного подправил свое последнее сообщение. Можете запустить (VS2005) и убедиться, что все работает правильно.

Всем спасибо, толку от вас никакого.