Lossless to_string transformation of very large absolute integers

steve02081504 0
Viewed 48

I have a to_string function that transforms the integer part like this

template<typename T>
inline string to_string_num_base_integer(T num)const noexcept{
    string aret;
    do{//do while, also has a return value when num is 0
        const auto first_char_index = mod(num,_radix);
        num /= (T)_radix;
        aret.push_front(_radix_table[(size_t)first_char_index]);
    }while(num>=T{1});
    return aret;
}

And for getting a number from a string, its integer part looks like this

template<typename T>
inline T from_string_get_num_base_integer(string str) const noexcept {
    T aret{};
    for(size_t i = 0; i < str.size(); i++) {
        const size_t index = _radix_table.find(str[i]);
        if(index == string::npos)
            return T();
        aret *= (T)_radix;
        aret += (T)index;
    }
    return aret;
}

To avoid misunderstandings caused by the ambiguity of my narrative, here is a link to the specific definition of to_string

I was confident a while back that my to_string and from_string_get could convert any arithmetic type to string and back again without any loss, so I wrote a brenchmark that looked something like this

template<class T>
T rand() {
    using namespace elc::defs;//data_view
    T            aret;
    data_view<T> ret_data_view{&aret};
    for(auto& i: ret_data_view)
        i = byte(::std::rand() % 256);
    return aret;
}
static void ELC_to_string(benchmark::State& state){
    elc::string str;
    for(auto _ : state){
        auto num=rand<double>();
        str=elc::to_string(num);
        //check
        state.PauseTiming();
        auto check_num = elc::from_string_get<double>(str);
        if(num != check_num) {
            auto debug_view = str.c_str();
            __debugbreak();
        }
        state.ResumeTiming();
    }
}
BENCHMARK(ELC_to_string);

However, once the program was up and running, I found that I was so wrong that basically my program passed at most one benchmaek iteration, or failed check on the first try Here's the data from a few random errors, it looks like it's a little off for very large absolute values

num         -2.4036764711757781e+254    double
check_num   -2.4036764711757750e+254    double
debug_view  0x000001754b13c490 U"-240367647117577728022446624802680682422824428288020260400400084004424482080208820222020204062260868842284288622624422042822844260426280602884262806220668240682804604406006206026884268064026880864280662062262284000686220022420882642600280488082246242286202"  const char32_t *
//
num         8.6154366127603682e+286 double
check_num   8.6154366127603513e+286 double
debug_view  0x00000223c6639580 U"86154366127603626606660082262640004866628468864688428288602262664666266684028042888846648644004400062268644624004624288622444666422464206066220046268260080844820628642240264646022846802064206462084048028268042804280644268088820448646800866008206646204206808086622826046822408866088646226"   const char32_t *

I would like to know how I can fix this problem?

c++
1 Answers

I think I did what I call a lossless conversion in a really stupid way, and even though it wasn't the way I wanted it to be, it did it

I let my computer run a random double test for an hour and it looked fine

First of all: my first reaction when I encountered this problem was to upgrade my algorithm to make the conversion less lossy, but whatever my friends and I did to improve the accuracy of the algorithm over the course of a few hours, we always can find some random double data that convert back just a little bit short of what it should have been.

While racking my brains to improve the algorithm I thought: if only there was a way to just stuff the underlying byte representation of the darn data into a string!

Well, so, why not?

I swear I'd really like to have some purely simple numerical computation to smoothly and concisely turn a double value into a string and back without loss, but it doesn't look like my friends and I can do it, at least for now, maybe in the future after humans make a pact with the void demons? I don't know.

So I made this commit, which does a simple job: it provides a function that transforms the underlying byte representation of any trivial type into a string under the current numeric representation rules, and allows you to convert back The code is as follows:

inline size_t get_info_tail_size_per_byte()const noexcept{
    constexpr auto info_threshold_base = pow(BIT_POSSIBILITY, bitnumof<byte>);
    auto           info_threshold      = to_size_t(ceil(log(info_threshold_base, _radix)));
    return info_threshold;
}
template<typename T>
inline size_t get_info_tail_size()const noexcept{
    return get_info_tail_size_per_byte()*sizeof(T);
}
template<typename T>
inline string get_info_tail(T x)const noexcept{
    auto info_tail_size_per_byte = get_info_tail_size_per_byte();
    string aret;
    data_view<const T> view{&x};
    for(const byte c: view) {
        auto s= to_string_rough((unsigned char)c);
        aret+=string{info_tail_size_per_byte-s.size(),_radix_table[0]}+s;
    }
    return aret;
}
template<typename T>
inline T get_from_info_tail(string str)const noexcept{
    auto info_tail_size_per_byte = get_info_tail_size_per_byte();
    T   aret{};
    data_view<T> view{&aret};
    for(byte&c: view) {
        auto s=str.substr(0,info_tail_size_per_byte);
        c=(byte)from_string_get<unsigned char>(s);
        str=str.substr(info_tail_size_per_byte);
    }
    return aret;
}

Then everything is much simpler!

All you need to do is to check if the number can be converted back after converting it to a string, and if not, append the string to the end of the string

You'll only add a few more digits to what is already a long string, and it won't even affect the results of the other string to arithmetic functions

if(from_string_get<T>(aret) != num) {
    string info_tail=get_info_tail(num);
    if(dot_pos==string::npos){
        if(aret.ends_with(string{info_tail.size(),_radix_table[0]}))
            aret.pop_back(info_tail.size());
        else
            aret.push_back(_fractional_sign);
    }
    aret+=info_tail;
    return aret;
}

And when you read the string and convert it to an arithmetic type, you only need to check that the contents of the string appended to the end of the string are converted to an arithmetic type and then converted to a string that matches the contents of the previous string

if constexpr(::std::is_floating_point_v<T>){
    auto info_tail_size=get_info_tail_size<T>();
    if(str.size()>info_tail_size){
        auto tail_pos=str.size()-info_tail_size;
        auto info_tail=str.substr(tail_pos);
        auto str_with_out_tail=str.substr(0,tail_pos);
        if(str_with_out_tail.back()==_fractional_sign)
            str_with_out_tail.pop_back();
        auto num=get_from_info_tail<T>(info_tail);
        if(to_string_rough(num)==str_with_out_tail)
            return num;
        str_with_out_tail+=string{info_tail.size(),_radix_table[0]};
        if(to_string_rough(num)==str_with_out_tail)
            return num;
    }
}

Overall, I passed the lossless conversion check in benchmark, and although this makes my library's to_string 21 times slower than the std version (considering I'm using my own string library, which might be faster if someone implemented the same thing with the standard library), my library is completely lossless, not a single bit off, which is something std can't do! benchmark! I'm so happy, although it would be nice if there was a cleaner way to do it

steve020815040
Related