2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Округление по длине мантиссы
Сообщение01.04.2009, 00:32 


17/10/08

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

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

 Профиль  
                  
 
 
Сообщение01.04.2009, 06:56 
Заслуженный участник


11/05/08
32166
mserg в сообщении #200769 писал(а):
аппроксимирующей функции минимальной длины.

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

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

 Профиль  
                  
 
 
Сообщение01.04.2009, 08:30 


17/10/08

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

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

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

 Профиль  
                  
 
 
Сообщение01.04.2009, 17:29 
Заслуженный участник


11/05/08
32166
да зачем округлять-то?...

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

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

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

 Профиль  
                  
 
 
Сообщение02.04.2009, 09:10 


17/10/08

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

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

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

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

 Профиль  
                  
 
 
Сообщение02.04.2009, 09:18 


23/12/08
36
mserg писал(а):
Использование ограниченной разрядности для констант, конечно, дает некоторую
дополнительную погрешность. Но критерий использует ДЛИНУ формулы

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

 Профиль  
                  
 
 
Сообщение02.04.2009, 10:48 


17/10/08

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

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

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

 Профиль  
                  
 
 
Сообщение02.04.2009, 10:54 
Заслуженный участник


11/05/08
32166
mserg в сообщении #201078 писал(а):
P.S. Вообще, сколько пядей во лбу нужно иметь, чтобы придерживаться темы?

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

 Профиль  
                  
 
 
Сообщение02.04.2009, 11:19 


23/12/08
36
mserg писал(а):
Длина формула - это количество бит, необходимое для ее записи.

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

 Профиль  
                  
 
 Re: Округление по длине мантиссы
Сообщение02.04.2009, 11:21 
Заслуженный участник


31/12/05
1480
mserg писал(а):
У меня есть вещественное число. Я хочу «урезать» мантиссу до заданного числа бит. Как это сделать? Требуется такое округление вверх и вниз. Есть подозрение, что нужно прямо колдовать над битами… Может, кто-нибудь проделывал такой фокус на С++?
Есть простой алгоритм перевода числа в двоичную систему, использующий умножение на 2 и взятие целой части. Обычно ему учат либо школьников на кружке, либо младшекурсников.

 Профиль  
                  
 
 
Сообщение02.04.2009, 11:49 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Округление по длине мантиссы
Сообщение02.04.2009, 12:58 
Аватара пользователя


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

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

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

 Профиль  
                  
 
 
Сообщение02.04.2009, 16:13 


17/10/08

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

Я плоховато знаю 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.

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

 Профиль  
                  
 
 
Сообщение02.04.2009, 16:26 


23/12/08
36
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 бита

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

 Профиль  
                  
 
 
Сообщение02.04.2009, 16:38 


17/10/08

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group