функция разбора действительных чисел на чистом C++
От: Дядюшка Че Россия  
Дата: 07.01.06 08:35
Оценка: 17 (4) +1
Предлагаю вашему вниманию функцию преобразования строки в вещественное число, которой пользуюсь уже достаточно долго.

Достоинства:

Недостатки:

На входе строка для разбора (string) и ссылка на принимающую переменную (var). Если разбор прошел успешно, функция возвращает true, а в var помещается число. В противном случае возвращается false, а переменная var сохраняет свое изначальное состояние.
Таким образом можно
// Допустим, a, b и c - переменные, причем a и b должны быть
// введены обязательно, а c - опционально (по умолчанию, скажем, будет -1).
// pszA, pszB, pszC - соответствующие строки.

    c = -1;
    if (!Parse(pszA, a) || !Parser(pszB, b)) { /*error*/ }
    Parse(pszC, c);


Итак, сама функция!.. Прошу извинить за язык комментариев

// (с)2004, Den Chetverikov

bool Parse(const char* string, long double& var) throw()
{
    bool minus(false);                // true if number is negative
    bool eminus(false);                // true if exponent is negative
    bool sign_awaited(true);
    int f = -1;                       // A number of digits after floating point.
                // When f < 0 we are still parsing an integer part of a number.
    int exp = 0;
    int dig = 0;                            // A number of decimal digits
    int edig = 0;                            // A number of decimal digits in exponent (after 'E')
    long double x = 0;
    char c;                                        // A current character 

    while ((c = *string++),(c != 0))
    {
        if (c == ' ' || c == '\t') continue;

        if (sign_awaited && (c == '+' || c == '-')) 
        {
            minus = (c != '+');
            sign_awaited = false;
            continue;
        }
        if (f < 0 && (c == '.' || c == ',')) 
        {
            f = 0;
            sign_awaited = false;
            continue; 
        }
        if (c == 'e' || c == 'E') 
        {
            sign_awaited = true;
            while ((c = *string++),(c != 0))
            {
                if (c == ' ' || c == '\t') continue;
                if (sign_awaited && (c == '+' || c == '-')) 
                {
                    eminus = (c != '+');
                    sign_awaited = false;
                    continue;
                }
                if (c < '0' || c > '9') return false;
                exp = exp*10 + (c - '0');
                ++edig;
            }
            if (edig == 0) return false;
            if (eminus) exp = -exp;
            break;
        }

        if (c < '0' || c > '9') return false;
        sign_awaited = false;
        ++dig;
        if (f >= 0)
        {
            ++f;
            if (dig >= 25) continue; 
                // All digits after 25th are not significant.
        }
        x = x*10 + (c - '0');
    }

    if (dig == 0) return false;
    f = (f < 0) ? -exp : f-exp;
    while (f < 0) 
    {
        x *= 10;
        ++f; 
    }
    while (f > 0)
    {
        x /= 10;
        --f;
    }
    var = minus ? -x : x;
    return true;
}


Суть алгоритма проста. Число "собирается" из десятичных разрядов в переменной x, как обычное целое. Позиция плавающей точки (или запятой) запоминается отдельно.
Если число записано в экспоненциальной форме (например, 0.499e-2), то считывается еще и экспонента — обычное целое число со знаком. После этого, исходя из позиции запятой и экспоненты, элементарно определяется, на сколько десятичных разрядов необходимо сдвинуть запятую влево (умножением на 10) или вправо (делением на 10). Для наглядности приведу примеры:

  string          |       "целая часть"       |     десятичная экспонента
---------------------------------------------------------------------------
1053.625          |          1053625          |              3
-0,0124           |              124          |             -4
100000            |           100000          |              0
1e20              |                1          |             20
-.25e-4           |               25          |        -2 + (-4) = -6



Функция получилась абсолютно платформенно-независимой, так как использует исключительно манипуляции со встроенными типами C++. Тип результирующей переменной long double выбран, как обеспечивающий максимальную точность.
Переходники для иных типов можно оформить так:


bool Parse(const char* number, double& var)
{
    long double t;
    if(!Parse(number, t)) return false;
    var = static_cast<double>(t);
    return true;
}

// Целые числа получаем путем округления
bool Parse(const char* string, long& var)
{
    long double t;
    if(!Parse(number, t)) return false;
    var = static_cast<long>(t + .5);
    return true;
}

// Для беззнаковых целых разумно будет отказаться от значений < 0.
bool Parse(const char* number, unsigned long& var)
{
    long double t;
    if(!Parse(number, t) || t < 0) return false;
    var = static_cast<unsigned long>(t + .5);
    return true;
}
 
// и так далее...


Буду рад комментариям.
Re: функция разбора действительных чисел на чистом C++
От: korzhik Россия  
Дата: 07.01.06 15:29
Оценка:
Здравствуйте, Дядюшка Че, Вы писали:

ДЧ>Предлагаю вашему вниманию функцию преобразования строки в вещественное число, которой пользуюсь уже достаточно долго.


ДЧ>Достоинства:

ДЧ> насчёт пробелов не согласен. считаю что данная функция не должна учитывать никаких пробелов, ну максимум можно учитывать только пробелы идущие перед числом.

ДЧ>Недостатки:

ДЧ> насчёт извлечения из потока, это не недостаток, она не должна этим заниматься, так что всё нормально.

ДЧ>Итак, сама функция!.. Прошу извинить за язык комментариев

[]
Функцию просмотрел мельком, вот комментарии:
1. строчку
    while ((c = *string++),(c != 0))

можно заменить, на
    while (c = *string++)


2. некорректно работает при переполнении
то есть, например, если подать число у которого експонента больше чем DBL_MAX_10_EXP,
например "1.23e+400" то результатом будет +INF, но функция вернёт true
Хотя это спорный момент, возможно так и надо делать. То есть число соответствует грамматике (значит функция возвращает true),
но на данной платформе такое число не представимо (результат +INF)



ДЧ>Суть алгоритма проста. Число "собирается" из десятичных разрядов в переменной x, как обычное целое. Позиция плавающей точки (или запятой) запоминается отдельно.

ДЧ>Если число записано в экспоненциальной форме (например, 0.499e-2), то считывается еще и экспонента — обычное целое число со знаком. После этого, исходя из позиции запятой и экспоненты, элементарно определяется, на сколько десятичных разрядов необходимо сдвинуть запятую влево (умножением на 10) или вправо (делением на 10).

Меня очень интерисует один вопрос. Скорость работы замеряли? сравнивали со стандартной функцией (strtod)?
Re: функция разбора действительных чисел на чистом C++
От: korzhik Россия  
Дата: 07.01.06 16:02
Оценка: 2 (1)
Здравствуйте, Дядюшка Че, Вы писали:

ДЧ>Предлагаю вашему вниманию функцию преобразования строки в вещественное число, которой пользуюсь уже достаточно долго.

[]
ДЧ>Буду рад комментариям.

вот ещё, неправильно отрабатывает
Parse("0.121212121212121212121212e-23", d)


я так понимаю из-за этого:
            if (dig >= 25) continue; 
                // All digits after 25th are not significant.
Re: функция разбора действительных чисел на чистом C++
От: CreatorCray  
Дата: 07.01.06 16:38
Оценка:
Здравствуйте, Дядюшка Че, Вы писали:

Интересный момент: если заменить x /= 10; на x *= 0.1; то будет потеря точности... почему?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[2]: функция разбора действительных чисел на чистом C++
От: korzhik Россия  
Дата: 07.01.06 17:51
Оценка:
Здравствуйте, korzhik, Вы писали:

K>Меня очень интерисует один вопрос. Скорость работы замеряли? сравнивали со стандартной функцией (strtod)?


вот, сам измерил:
//-----------------------------------------------------------------------------
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include "boost/timer.hpp"
#include "boost/spirit/core.hpp"
//-----------------------------------------------------------------------------
std::string generator()
{
    using namespace std;

    char buf[500]; 
    long double d = rand() / (long double)RAND_MAX; d *= rand();

    sprintf(buf, "%g", d);

    return buf;
}
//-----------------------------------------------------------------------------
struct custom_function_call
{
    void operator()(const std::string& s) const
    {
        long double result;
        Parse(s.c_str(), result);
    }
};
//-----------------------------------------------------------------------------
struct standard_function_call
{
    void operator()(const std::string& s) const
    {
        char* p;
        long double result = strtod(s.c_str(), &p);
    }
};
//-----------------------------------------------------------------------------
struct stl_function_call
{
    void operator()(const std::string& s) const
    {
        std::istringstream stream(s);
        double result;
        stream >> result;
    }
};
//-----------------------------------------------------------------------------
struct boost_spirit_call
{
    void operator()(const std::string& s) const
    {
        using namespace boost::spirit;

        double result;

        (void)parse(s.begin(), s.end(), real_p[assign_a(result)], nothing_p);
    }
};
//-----------------------------------------------------------------------------
template <class F>
double test_function_time(const std::vector<std::string>& array, F f)
{
    boost::timer tm;

    std::for_each(array.begin(), array.end(), f);

    return tm.elapsed();
}
//-----------------------------------------------------------------------------
int main()
{
    enum {array_size = 1000000};
    std::vector<std::string> array(array_size);

    srand((unsigned)time(0));

    std::generate(array.begin(), array.end(), &generator);

    //std::copy(array.begin(), array.end(), 
    //          std::ostream_iterator<std::string>(std::cout, "\n"));

    std::cout << "Parse function time:  " 
              << test_function_time(array, custom_function_call())   << "s\n";
    
    std::cout << "strtod function time: " 
              << test_function_time(array, standard_function_call()) << "s\n";

    std::cout << "stringstream time:    " 
              << test_function_time(array, stl_function_call()) << "s\n";    
    
    std::cout << "boost::spirit time:   " 
              << test_function_time(array, boost_spirit_call()) << "s\n";
}

Parse function time:  0.016s
strtod function time: 1.484s
stringstream time:    5.218s
boost::spirit time:   0.766s
Re[2]: функция разбора действительных чисел на чистом C++
От: Дядюшка Че Россия  
Дата: 07.01.06 21:49
Оценка:
Здравствуйте, CreatorCray, Вы писали:

CC>... если заменить x /= 10; на x *= 0.1; то будет потеря точности... почему?


Так происходит из-за того, что 0.1 может быть представлена в двоичном виде только с приблизительной точностью (что-то вроде 0.099999999999999... Количество девяток — в зависимости от разрядности мантиссы). А деление на 10 — это просто деление на 10, и ничего больше
Re[2]: функция разбора действительных чисел на чистом C++
От: Дядюшка Че Россия  
Дата: 07.01.06 22:16
Оценка:
Здравствуйте, korzhik, Вы писали:

K>насчёт пробелов не согласен. считаю что данная функция не должна учитывать никаких пробелов, ну максимум можно учитывать только пробелы идущие перед числом.


<skipped>

K>насчёт извлечения из потока, это не недостаток, она не должна этим заниматься, так что всё нормально.


Да! Я просто хотел предупредить, что такой функциональности ждать не надо. Рад, что это получилось сделать доступным языком. Здесь же ответ на вопрос о допустимости пробелов внутри числа:
Если у Вас есть строка "1 234 567,89", то Вам самим решать, три это числа или одно. Функция съест то, что ей подали. Это добавляет гибкости и не создает лишних хлопот.

K>Функцию просмотрел мельком, вот комментарии:

K>1. строчку
K>
K>    while ((c = *string++),(c != 0))
K>

K>можно заменить, на
K>
K>    while (c = *string++)
K>


Согласен, что можно, но выражение справа от запятой написана осознанно. Многие (умные) компиляторы будут кидать предупреждения о том, что = скорее всего надо заменить на ==. (И эти ругательства оправданы: ошибка часто попадается даже у матерых девелоперов.) Поэтому надо дать компилятору знать, что мы ответственны за свои действия.
Левая от запятой часть делает свое дело, а правая представляет собой условие продолжения цикла. Оптимизируется компилятором без шума и пыли.

K>2. некорректно работает при переполнении

K>то есть, например, если подать число у которого експонента больше чем DBL_MAX_10_EXP,
K>например "1.23e+400" то результатом будет +INF, но функция вернёт true
K>Хотя это спорный момент, возможно так и надо делать. То есть число соответствует грамматике (значит функция возвращает true),
K>но на данной платформе такое число не представимо (результат +INF)

Да, налицо переполнение. Из курса математики известно, что 1.23+400 != (+INF). Нужно возвращать false, однозначно!
Re[2]: функция разбора действительных чисел на чистом C++
От: Дядюшка Че Россия  
Дата: 07.01.06 22:40
Оценка:
Здравствуйте, korzhik, Вы писали:

K>вот ещё, неправильно отрабатывает

K>
K>Parse("0.121212121212121212121212e-23", d)
K>


K>я так понимаю из-за этого:

K>
K>            if (dig >= 25) continue; 
K>                // All digits after 25th are not significant.
K>


Да, мне это место самому не нравится. Во-первых, волшебное число 25, добытое где-то из глубин стандартной библиотеки — частный случай. Например, под MSVC sizeof(long double) == sizeof(double), а под BCC sizeof(long double) > sizeof(double). Во-вторых, еще и проблемы...
Все! Завтра же с утра за компилятор!

Я вот еще думал: нужно ли "понимать" +INF и -INF ?
Пришел к выводу, что нет.
Во-первых, этого не делают аналоги (да и что такое INF? где сказано, что бесконечность надо обозначать именно так?)
Во-вторых, это редко требуется. Если требуется ввод числа в TextBox, то для бесконечностей лучше создать отдельно набор радиокнопок. Согласитесь, редкий пользователь сообразит, что надо писать -INF.
В-третьих, есть еще разновидности NAN("не число"): QNAN и SNAN. Лучше не забивать голову себе и пользователям


За измерения отдельное спасибо!

K>Parse function time: 0.016s

K>strtod function time: 1.484s
K>stringstream time: 5.218s
K>boost::spirit time: 0.766s

Re[3]: функция разбора действительных чисел на чистом C++
От: korzhik Россия  
Дата: 08.01.06 18:34
Оценка:
Здравствуйте, Дядюшка Че, Вы писали:

ДЧ>Я вот еще думал: нужно ли "понимать" +INF и -INF ?

ДЧ>Пришел к выводу, что нет.
ДЧ>Во-первых, этого не делают аналоги (да и что такое INF? где сказано, что бесконечность надо обозначать именно так?)
ДЧ>Во-вторых, это редко требуется. Если требуется ввод числа в TextBox, то для бесконечностей лучше создать отдельно набор радиокнопок. Согласитесь, редкий пользователь сообразит, что надо писать -INF.
ДЧ>В-третьих, есть еще разновидности NAN("не число"): QNAN и SNAN. Лучше не забивать голову себе и пользователям

Я думаю не надо. Если такое понадобится, то распознование "INF" и тд. можно сделать отдельно
Re: функция разбора действительных чисел на чистом C++
От: Дядюшка Че Россия  
Дата: 09.01.06 10:16
Оценка: 29 (4)
Функция исправлена. Слишком большие по модулю числа на входе приводят к возврату false, а слишком маленькие по модулю приводятся к нулю. Отлажена работа с числами, близкими по модулю к LDBL_MAX. Пришлось также воспользоваться константами из CRT и включить <float.h>.

Долгое время провел, не понимая отчего функция падает, если на вход подавать числа, близкие к нулю и содержащие более 5191 символа после "0,". Приводить пример не буду, слишком уж длинный получится. И случай очень специфический.

Оказалось, проблема вовсе не в моей функции, а в ее соседке из VCL: FloatToStr, которую я вызвал с тем же аргументом для сравнения результатов. Что-то страшное она делает с регистрами FPU, после чего первая же операция с плавающей точкой (уже в моей невинной функции) с треском проваливается. В общем, большущий камень в огород VCLи компилятора BCBuilder .

Знаний для объяснения подобного феномена, увы, не хватает. В голову пришло лишь воспоминание о том, что очень-очень-очень маленькие числа (то есть почти 0) по стандарту IEEE хранятся в особом формате ("денормированные числа", если не ошибаюсь). CPU использует это представление, однако Borland'овская функция на него не рассчитана. Но ковыряться во FloatToStr нет никакого желания.

Parse со своими обязанностями вполне справляется. Жду оценок.

#include <float.h>

// (c) Den Chetverikov
bool Parse(const char* string, long double& var)
{
    bool minus(false);
    bool sign_awaited(true);
    int fpt = -1;     // A number of digits after floating point or (-1).
    int exp = 0;
    int dig = 0;      // A number of decimal digits
    long double x = 0;
    char c;           // A current character

    while ((c = *string++),(c != 0))
    {
        if (c == ' ') continue;

        if (sign_awaited && (c == '+' || c == '-'))
        {
            minus = (c != '+');
            sign_awaited = false;
            continue;
        }
        if (fpt < 0 && (c == '.' || c == ','))
        {
            fpt = 0;
            sign_awaited = false;
            continue;
        }
        if (dig > 0 && (c == 'e' || c == 'E'))
        {
            int e = 0;     // An exponent
            int edig = 0;  // A number of decimal digits in exponent
            bool eminus = false;
            sign_awaited = true;
            while ((c = *string++),(c != 0))
            {
                if (c == ' ') continue;
                if (sign_awaited && (c == '+' || c == '-'))
                {
                    eminus = (c != '+');
                    sign_awaited = false;
                    continue;
                }
                if (c < '0' || c > '9') return false;
                e = e * 10 + (c - '0');
                ++edig;
            }
            if (edig == 0) return false;
            exp += (eminus) ? -e : e;
            break;
        }

        if (c < '0' || c > '9') return false;
        sign_awaited = false;
        if (x != 0 || dig == 0) ++dig;

        if (dig >= LDBL_DIG)
        {
            if (fpt < 0) ++exp;
        }
        else
        {
            x = x * 10 + (c - '0');
            if (fpt >= 0) ++fpt;
        }
    }

    if (dig == 0) return false;

    if (fpt >= 0) exp = exp - fpt;
    while (exp > 0)
    {
        if (x > LDBL_MAX / 10) return false;
        x *= 10;
        --exp;
    }
    while (exp < 0)
    {
        x /= 10;
        ++exp;
    }
    var = minus ? -x : x;
    return true;
}
Re[2]: функция разбора действительных чисел на чистом C++
От: korzhik Россия  
Дата: 10.01.06 09:06
Оценка:
Здравствуйте, Дядюшка Че, Вы писали:

ДЧ>Parse со своими обязанностями вполне справляется. Жду оценок.

[]

Мне вот всё таки интересно почему strtod работает медленнее чем твоя функция. Жалко исходников нет.
Но я думаю что strtod обрабатывает какие то хитрые случаи. куча проверок и тд.

Ну вообще грустная ситуация, вроде есть библиотечная функция, причём не одна,
но людям всё равно приходится писать свои велосипеды.
Я думаю главная причина в том, что если есть какие то специфические требования к парсингу то приходится писать что-то своё.
В этом плане мне очень нравится как реализован boost::spirit::real_parser на основе стратегий. Очень гибко.

Если интересно смотри файлы:
boost/spirit/core/primitives/numerics.hpp
boost/spirit/core/primitives/impl/numerics.ipp
Re: функция разбора действительных чисел на чистом C++
От: Блудов Павел Россия  
Дата: 10.01.06 10:48
Оценка: :)
Здравствуйте, Дядюшка Че, Вы писали:

ДЧ>Достоинства:

ДЧ>
Имейте ввиду, что в некоторых странах запятую (или точку) используют в качестве разделителя тысяч.
Там, где русскому хорошо — немцу смерть. И американцу, и датчанину и вообще всем кроме русских, французов и их друзей.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[2]: функция разбора действительных чисел на чистом C++
От: Дядюшка Че Россия  
Дата: 11.01.06 13:14
Оценка:
Здравствуйте, Блудов Павел, Вы писали:

БП>Имейте ввиду, что в некоторых странах запятую (или точку) используют в качестве разделителя тысяч.


Да, используют; есть и другие каверзные случаи, если заглянуть в Панель управления. Однако функции, которыми мы пользуемся для преобразования числа в строку (ftoa, itoa, sprintf, wsprintf, FloatToStr, VarBstrFromR8 и пр.) выдают строки без "художественных излишеств", независимо от большинства региональных настроек.

С другой стороны, если мы прилагаем усилия для форматирования числа с учетом локали, то полученное представление используются исключительно для вывода каких-либо данных. Оно не подразумевает обратного преобразования "строка->число".
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.